Thuật toán giải Sudoku nhanh nhất Python

Để hoàn thành dự án này, bạn cần làm quen với các khái niệm lập trình cơ bản, chẳng hạn như sử dụng mảng hai chiều, cấu trúc điều khiển [câu lệnh if, vòng lặp for, v.v.] và các hàm

Bạn cũng cần biết Sudoku hoạt động như thế nào. Nếu bạn không quen, đây là một trang web tuyệt vời mà bạn có thể tham khảo – https. //www. học sudoku. com/sudoku-quy. html

Dưới đây là một số chủ đề chúng tôi sẽ đề cập trong dự án hôm nay

• phương pháp quay lui là gì
• Cách sử dụng đệ quy trong lập trình
• Cách giải Sudoku bằng đệ quy trong Python

Mục lục

Ý chính

Trước khi tiếp tục, chúng ta hãy xem qua một số khái niệm chính cần thiết cho dự án hôm nay. Đầu tiên là khái niệm quay lui. Chúng ta sẽ sử dụng phương pháp quay lui để giải câu đố Sudoku sau này

quay lui là gì?

Quay lui là một kỹ thuật lập trình trong đó chúng tôi xây dựng một giải pháp từng bước một. Tại bất kỳ thời điểm nào, nếu chúng tôi nhận ra rằng không thể tìm ra giải pháp hợp lệ cho bước hiện tại, chúng tôi sẽ quay lại bước trước đó và thay đổi giải pháp cho bước đó

Trong trường hợp Sudoku, quay lui yêu cầu chúng ta giải từng ô một. Tại bất kỳ thời điểm nào, nếu chúng tôi đến một ô mà chúng tôi không thể giải quyết, chúng tôi sẽ quay lại ô trước đó và thay đổi giải pháp cho ô đó

Các bước chi tiết như sau

1. Quét qua các ô theo từng hàng cho đến khi bạn đến một ô trống
2. Kiểm tra các số từ 1 đến 9 cho ô đó. Ngay khi tìm thấy một số hợp lệ, chúng tôi 'giả định' rằng đây là câu trả lời đúng và điền vào ô bằng số đó
3. Chuyển sang ô trống tiếp theo và lặp lại Bước 2 cho ô đó
4. Tiếp tục lặp lại cho đến khi chúng tôi gặp một ô không có câu trả lời hợp lệ [i. e. , tất cả các số từ 1 đến 9 đều trượt]
5. Khi điều đó xảy ra, hãy quay lại ô trước đó và thử số hợp lệ tiếp theo
6. Tiếp tục lặp lại cho đến khi cuối cùng chúng ta giải được câu đố

Nghe có vẻ khó hiểu? . Video được quay bằng bộ giải tại https. //trò chơi bài. io/sudoku/]

Trong video quay ở trên, chúng ta bắt đầu bằng cách chèn số 2 vào ô cuối cùng của hàng 1

Tiếp theo, chúng ta chuyển sang hàng 2 và chèn số 1 vào ô đầu tiên

Sau đó, chúng tôi chuyển sang ô tiếp theo và cố gắng chèn các số từ 1 đến 9. Thật không may, không có con số nào hoạt động. Khi điều đó xảy ra, chúng ta cần quay lại

Chúng tôi quay trở lại ô trước đó và thử số hợp lệ tiếp theo. Vì ô trước có giá trị là 1 nên ta thử tiếp theo là số 2. Số này không thành công nhưng số 3 tiếp theo hoạt động

Khi chúng tôi tìm thấy một số hoạt động, chúng tôi sẽ chuyển sang ô tiếp theo một lần nữa. Lần này, số 1 hoạt động cho ô đó

Điều này tiếp tục lặp lại cho đến khi chúng tôi giải quyết toàn bộ bảng Sudoku

Nghiên cứu kỹ video và đảm bảo bạn hiểu đầy đủ cách hoạt động của tính năng quay lui trước khi tiếp tục. Một trường hợp quay lui khác xảy ra ở 00. 38

Khi bạn đã quen với việc quay lui, hãy chuyển sang đệ quy. Chúng tôi sẽ sử dụng đệ quy và quay lui để giải câu đố Sudoku trong dự án của chúng tôi

Đệ quy là gì?

Đệ quy là một kỹ thuật mà một hàm gọi chính nó trong quá trình thực thi

Điều này rất hữu ích khi giải pháp cho vấn đề lập trình phụ thuộc vào giải pháp cho các trường hợp nhỏ hơn của cùng một vấn đề

Giả sử chúng ta có một bảng Sudoku với 10 ô trống

Để quyết định xem một số có hợp lệ cho ô trống đầu tiên hay không, chúng ta có thể sử dụng đệ quy để thử giải 9 ô còn lại. Nếu tìm được nghiệm cho 9 ô còn lại thì biết số hiện tại là số chính xác

Mặt khác, nếu chúng tôi không thể tìm ra giải pháp cho 9 ô còn lại, chúng tôi sẽ cập nhật ô hiện tại thành số có thể tiếp theo. Nói cách khác, dựa trên kết quả không thành công của 9 ô còn lại, chúng tôi quay lại ô hiện tại để cập nhật giá trị của nó

Đây là ý chính về cách chúng ta sẽ sử dụng đệ quy để giải câu đố Sudoku trong dự án này

Để biết thêm ví dụ về cách sử dụng đệ quy để giải quyết các vấn đề khác, bạn có thể xem các bài đăng này [tại đây và tại đây]

Sẽ dễ hiểu hơn về đệ quy khi chúng ta bắt đầu làm việc với dự án của mình. Hãy làm điều đó ngay bây giờ

Hãy làm nó

Tôi đã chia nhỏ dự án thành 5 bước

Bước 1. Tạo và in bảng

Bước này yêu cầu chúng ta tạo một mảng có tên là

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

2. Mảng này lưu bảng Sudoku sau đây dưới dạng mảng hai chiều

Mỗi phần tử trong

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

2 là một mảng lưu trữ một hàng trong bảng Sudoku, trong đó các ô trống được thay thế bằng số 0.

Ví dụ,

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

4 lưu hàng đầu tiên.

Nói cách khác,

myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]

Sau khi tạo bảng, bạn cần viết mã để in bảng. Hãy thử làm điều này cho mình

Kết quả mong đợi

Bạn sẽ nhận được kết quả sau khi chạy mã của mình

[0, 4, 0, 7, 0, 0, 1, 3, 0]
[0, 0, 2, 0, 0, 0, 6, 0, 0]
[0, 0, 0, 4, 2, 0, 0, 0, 0]
[6, 0, 0, 0, 0, 2, 0, 0, 3]
[2, 3, 1, 0, 7, 0, 0, 8, 0]
[4, 0, 0, 3, 1, 0, 0, 0, 0]
[0, 7, 0, 0, 0, 8, 0, 0, 0]
[0, 0, 6, 0, 3, 0, 0, 0, 4]
[8, 9, 0, 0, 5, 0, 0, 0, 6]

Cần giúp đỡ?

Đoạn mã sau tạo một mảng hai chiều có ba phần tử. Ba phần tử là các mảng

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

5,

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

6 và

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

7

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

Đoạn mã sau in mảng trên

for line in myArray:
    print[line]

Hãy thử sửa đổi mã ở trên để hoàn thành Bước Một

giải pháp đề xuất

Nhấp để xem giải pháp được đề xuất

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

0

Bước 2. Viết hàm kiểm tra xem một số có hợp lệ cho một ô nào đó không

Ở Bước 2, chúng ta cần viết một hàm có tên là

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

8 có bốn tham số –

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

9,

for line in myArray:
    print[line]

0,

for line in myArray:
    print[line]

1 và

for line in myArray:
    print[line]

2

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

9 đại diện cho bảng Sudoku trong khi

for line in myArray:
    print[line]

0 và

for line in myArray:
    print[line]

1 tương ứng với hàng và cột của một ô. Hàm

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

8 kiểm tra xem có thể đặt

for line in myArray:
    print[line]

2 vào ô được chỉ định bởi

for line in myArray:
    print[line]

0 và

for line in myArray:
    print[line]

1 hay không. Nếu có thể, hàm trả về

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

00. Khác, nó trả về

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

01

Chẳng hạn, đối với ô được đánh dấu trong bảng Sudoku ở Bước Một,

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

02 và

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

03 [hãy nhớ rằng

for line in myArray:
    print[line]

0 và

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

05 bắt đầu từ chỉ số 0]. Nếu

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

06, hàm

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

8 sẽ trả về

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

01 vì

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

09 đã tồn tại trong hàng đó. Ngược lại, nếu

myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]

30,

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

8 sẽ trả về

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

00

Hãy thử mã hóa chức năng này cho mình. Hãy nhớ rằng bạn phải kiểm tra xem có tồn tại

for line in myArray:
    print[line]

2 trong hàng, cột và ô vuông 3×3 hiện tại không

Kết quả mong đợi

Sau khi mã hóa chức năng, bạn có thể kiểm tra xem nó có hoạt động chính xác hay không bằng cách chạy các câu lệnh sau

myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]

3

Nếu bạn chạy mã ở trên, bạn sẽ nhận được đầu ra sau

myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]

8

Đối với câu lệnh đầu tiên, 6 đã tồn tại ở hàng 3. Đối với lần thứ hai, 6 tồn tại trong cột 6. Đối với cái thứ ba, 6 tồn tại ở ô 3 × 3 dưới cùng bên phải

Do đó, đối với 3 câu lệnh đầu tiên, bạn nhận được kết quả là

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

01

Đối với câu lệnh cuối cùng, bạn nhận được

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

00 vì 6 là một số hợp lệ tại

myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]

36,

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

03

Cần giúp đỡ?

Tương đối dễ dàng để kiểm tra xem

for line in myArray:
    print[line]

2 có tồn tại trong một hàng và cột nhất định hay không. Khó kiểm tra xem nó có tồn tại trong hình vuông 3×3 hiện tại không

Một cách để làm điều đó là tìm ra vị trí của góc trên cùng bên trái của hình vuông. Chẳng hạn, đối với ô được đánh dấu trong ví dụ của chúng tôi, góc trên cùng bên trái của hình vuông nằm ở hàng 6, cột 3

Để lấy hàng của góc trên cùng bên trái, bạn có thể sử dụng công thức

myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]

39.

myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]

80 cho chúng ta phần còn lại khi

for line in myArray:
    print[line]

0 chia cho 3. Điều này cho chúng ta biết ô hiện tại cách hàng của góc trên cùng bên trái bao xa

Trong ví dụ của chúng tôi,

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

02 cho ô được đánh dấu.

myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]

80 cung cấp cho chúng tôi

myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]

84, cho biết ô được tô sáng nằm dưới góc trên cùng bên trái một hàng

myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]

39 cho chúng ta

myArray = [[1, 2, 3],
           [2, 7, 1],
           [1, 9, 7]]

09, là hàng của góc trên cùng bên trái của hình vuông 3×3 đó

Để lấy cột của góc trên cùng bên trái, bạn có thể sử dụng công thức

myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]

87

Điều này mang lại cho chúng tôi 3 cho ô được đánh dấu

Từ góc trên cùng bên trái, bạn có thể sử dụng vòng lặp để kiểm tra xem có tồn tại

for line in myArray:
    print[line]

2 ở hàng 6, 7 và 8 cho các cột 3, 4, 5 không

Dựa trên mô tả ở trên, hãy thử sửa đổi giải pháp cho Bước Bốn để giải quyết toàn bộ bảng Sudoku