Thuật toán giải sudoku bằng quay lui backtracking

Thuật toán giải Sudoku được biết tới là một trong những yếu tố được rất nhiều game thủ quan tâm khi tham gia vào các sân chơi Sudoku. Vậy thuật toán này được sử dụng như thế nào? Tất cả những nội dung mà anh em cần nắm được sẽ có trong các nội dung dưới đây được chia sẻ bởi doithuong86.club.

Giới thiệu luật chơi và cách giải Sudoku

Có thể hiểu sân chơi này đơn giản là một trò chơi giải đố hoặc một trò chơi câu đố cần sắp xếp các chữ số dựa theo tính logic cũng như quy luật được hệ thống đưa ra. Theo đó mục tiêu cuối cùng của nó là điền các chữ số trong khoảng từ 1 đến 9 vào từng ô vuông trong bảng lưới Sudoku sao cho mỗi cột, hàng hay khối đều có thể đứa đầy đủ các chữ số từ 1 cho đến 9.

Hầu như tất cả các sân chơi đều sẽ chỉ cho trước một vài ô số đã điền để gợi ý cho người chơi. Nhiệm vụ của người chơi là phải áp dụng tất cả các quy tắc để có thể giải tiếp các ô vuông còn lại. Người chơi sẽ chỉ giành phần thắng khi đã giải được tất cả các ô số và đảm bảo đúng thời gian quy định.

Cách chơi Sudoku được đánh giá là không quá khó nhưng đòi hỏi người chơi sẽ phải có tính kiên nhẫn và kiên trì lâu dài. Bên cạnh đó khả năng phán đoán, phân thích cũng là những yếu tố vô cùng quan trọng mà anh em không thể bỏ qua khi tham gia vào các sân chơi này.

Cách giải Sudoku đòi hỏi người chơi cần phải lần lượt điền vào các ô số từ 1 đến 9 để sao cho mỗi con số đó đều phải đảm bảo giữ vị trí duy nhất trong hàng, cột hay một khối vuông 3×3. Nhiệm vụ của anh em lúc này là cần phải tìm ra đúng quy luật của các con số trước đó, sau đó mới có thể điền tiếp những con số còn lại.

READ  Những con lô gan nhất trong lịch sử – Lô gan nhất là bao nhiêu ngày
thuật toán giải sudoku
thuật toán giải sudoku

Cách dùng thuật toán giải Sudoku

Thuật toán giải Sudoku phổ biến nhất hiện nay mà chúng ta được biết chính là thuật toán Quay lui hay backtracking. Theo đó ngôn ngữ mà thuật toán này đang sử dụng để lập trình là ngôn ngữ Python với các bước tiến hành lần lượt như sau:

Bước 1: Viết hàm in của câu giải đố Sudoku ra trực tiếp màn hình.

Bước 2: Thuật toán sẽ tìm kiếm những ô trống chưa được điền trong bảng Sudoku.

Bước 3: Với mỗi vị trí chưa được điền thì người chơi sẽ phải lần lượt đặt các con số từ 1 đến 9. Sau đó kiểm tra nó có hợp lệ hay không? Nếu hợp lệ thì sẽ tiếp tục tìm kiếm các ô trống cần điền tiếp theo. Nếu không thì anh em nên sử dụng với các con số tiếp theo.

Bước 4: Lặp lại các quy trình trên cho đến khi các ô trống trên bảng Sudoku đều đã được điền hết hoặc cũng có thể là người chơi không thể tìm được lời giải.

cau_do = [

[7,8,0,4,0,0,1,2,0],

[6,0,0,0,7,5,0,0,9],

[0,0,0,6,0,1,0,7,8],

[0,0,7,0,4,0,2,6,0],

[0,0,1,0,5,0,9,3,0],

[9,0,4,0,6,0,0,0,5],

[0,7,0,3,0,0,0,1,2],

[1,2,0,0,0,7,4,0,0],

[0,4,9,2,0,6,0,0,7]

]

Người chơi cũng cần phải lưu ý rằng các chỉ số index trong Python sẽ thường được đánh từ 0 trở đi nên có thể thấy các vị trí trong của mỗi ô trong bảng thường sẽ là cau_d0[0][0] cho đến cau_do[8][8].

Ví dụ như: nếu hàm được viết là cau_do[d][c] là ô số ở vị trí cụ thể là dòng d và cột c.

Dưới đây sẽ là hướng dẫn các bước giải thuật toán Sudoku chi tiết nhất anh em cần biết:

Viết hàm in câu đố Sudoku

Đầu tiên, người chơi cần phải viết hàm in câu đố Sudoku đó lên màn hình máy tính của mình. Ở đây người chơi thường sử dụng giao diện dòng lệnh nên sẽ áp dụng hàm print của Python để có thể in đối tượng cần tìm ra màn hình.

Anh em sẽ viết hàm in_ Sudoku để có thể in được câu đố Sudoku với tên gọi q ra màn hình, bên cạnh đó là biến d và c để người chơi có thể biểu diễn cả dòng và cột trong bảng Sudoku.

Nếu dòng d là dòng thứ 3 hoặc 6 thì người chơi sẽ phải thực hiện in ra màn hình một lệnh gồm các kí tự – – – – – – – – – – – –  để làm kí tự ngăn cách. Mục đích của việc này chính là để hiển thị cho các khối ô vuông 3×3 của bảng Sudoku.

READ  Bắn Cá đổi thưởng tặng Code – Cập nhật code bắn cá mới nhất

Còn với trường hợp d là ở cột thứ 3 hoặc 6 thì thay vì dùng kí tự gạch ngang, anh em sẽ sử dụng gạch chéo để ngăn cách. Còn nếu cột đó ở vị trí từ 8 thì người chơi sẽ phải thực hiện xuống dòng mới.

def in_sudoku(q):

for d in range(len(q)):

if d % 3 == 0 and d != 0:

print(“- – – – – – – – – – -“)

for c in range(len(q[0])):

if c % 3 == 0 and c != 0:

print(“| “, end =””)

if c == 8:

print(str(q[d][c]))

else:

print(str(q[d][c]) + ” “, end = “”)

Nếu như chúng ta in thử lệnh cau_do như ở phần đầu thì sau khi nhập người chơi sẽ nhận được kết quả như sau:

Kết quả thuật toán giải Sudoku

Viết hàm tìm ô trống trong Sudoku

Tiếp theo đó sẽ phải tìm các ô trống vẫn chưa được điền các chữ số trong bảng tính Sudoku. Mục tiêu của các anh em game thủ ở đây chính là tìm ra các vị trí ô trống trong câu đố q.

def tim_o_trong(q):

for d in range(len(q)):

for c in range(len(q[0])):

if q[d][c] == 0:

return d, c

return None

Viết hàm kiểm tra tính hợp lệ

Người chơi sẽ thực hiện đặt lần lượt các số thứ tự từ 1 đến 9 với mỗi ô trống mà mình vừa mới tìm được. Sau đó hệ thống sẽ trả cho bạn kết quả là nếu đặt số đó vào ô vuông đó thì có hợp lệ hay không. Hệ thống sẽ cài đặt các quy luật của Sudoku trước đó để đảm bảo hệ thống có thể xác định được tính hợp lệ.

Nếu như trường hợp hệ thống báo về số đó hợp lệ thì anh em sẽ tiếp tục với các ô trống tiếp theo và thử lại xem đã đã hợp lý hay chưa. Còn trường hợp hệ thống báo số của bạn không chính xác thì anh em sẽ phải thử lần lượt các con số tiếp theo.

def kiem_tra(q, gia_tri, dong, cot):

for i in range(len(q[0])):

if q[i][cot] == gia_tri and i != dong:

return False

for i in range(len(q)):

if q[dong][i] == gia_tri and i != cot:

return False

x = cot // 3

y = dong // 3

for i in range(y*3, y*3+3):

for j in range(x*3, x*3+3):

if q[i][j] == gia_tri and i != dong and j != cot:

return False

return True

Viết hàm chính để tìm lời giải cho câu đố của bảng Sudoku

Người chơi sẽ phải thực hiện việc lặp đi lặp lại các bước kể trên để đảm bảo có thể điền kín tất cả các ô trống trong bảng câu đố Sudoku. Còn nếu trường hợp đã quá thời gian mà anh em vẫn không tìm được lời giải thì sẽ bị đánh là thua cuộc. Đây là yếu tố cũng khá quan trọng trong cách giải thuật toán Sudoku.

Chương trình thuật toán giải Sudoku hoàn chỉnh

Anh em có thể xem lại thuật toán giải Sudoku hoàn chỉnh nhất trong ví dụ cụ thể dưới đây. Từ ví dụ này anh em cũng có thể tự mình chạy các thuật toán giải Sudoku một cách nhanh chóng, chính xác nhất.

cau_do = [

    [7,8,0,4,0,0,1,2,0],

    [6,0,0,0,7,5,0,0,9],

    [0,0,0,6,0,1,0,7,8],

    [0,0,7,0,4,0,2,6,0],

    [0,0,1,0,5,0,9,3,0],

    [9,0,4,0,6,0,0,0,5],

    [0,7,0,3,0,0,0,1,2],

[1,2,0,0,0,7,4,0,0],

    [0,4,9,2,0,6,0,0,7]

]

def in_sudoku(q):

for d in range(len(q)):

     if d % 3 == 0 and d != 0:

            print(“- – – – – – – – – – -“)

     for c in range(len(q[0])):

         if c % 3 == 0 and c != 0:

                print(“| “, end =””)

         if c == 8:

                print(str(q[d][c]))

         else:

                print(str(q[d][c]) + ” “, end = “”)

def giai(q):

tim_thay = tim_o_trong(q)

if not tim_thay:

     return True

else:

     d, c = tim_thay

for i in range(1,10):

     if kiem_tra(q, i, d, c):

         q[d][c] = i

         if giai(q):

             return True

         else:

                q[d][c] = 0

return False

def tim_o_trong(q):

for d in range(len(q)):

     for c in range(len(q[0])):

         if q[d][c] == 0:

             return d, c

return None

def kiem_tra(q, gia_tri, dong, cot):

for i in range(len(q[0])):

     if q[i][cot] == gia_tri and i != dong:

         return False

for i in range(len(q)):

     if q[dong][i] == gia_tri and i != cot:

         return False

x = cot // 3

y = dong // 3

for i in range(y*3, y*3+3):

     for j in range(x*3, x*3+3):

        if q[i][j] == gia_tri and i != dong and j != cot:

             return False

return True

in_sudoku(cau_do)

giai(cau_do)

print(‘Loi giai cua Sudoku tren la:’)

in_sudoku(cau_do)

Có thể thấy thuật toán giải Sudoku quay lui là một trong những phương pháp mà người chơi không thể không biết tới khi tham gia vào các sân chơi giải đố Sudoku. Hy vọng với những chia sẻ chi tiết trên đây của blog game sẽ giúp anh em có thể nắm được những thông tin bổ ích và áp dụng vào ván chơi của mình một cách hiệu quả nhất.

Viết một bình luận