Hướng dẫn python efficient sudoku solver - python - trình giải sudoku hiệu quả

Bộ giải Sudoku với Python: Một cách tiếp cận có phương pháp để tối ưu hóa thuật toán [Phần 2]

Đây là phần thứ hai của một loạt các bài báo dành riêng cho trò chơi nổi tiếng của Sudoku. Đặc biệt hơn, làm thế nào chúng ta có thể xây dựng một tập lệnh để tự động giải các câu đố Sudoku với đệ quy và do đó cải thiện hiệu suất của nó.

Bài viết thứ hai này dự định chứng minh quá trình tư duy để tối ưu hóa giải pháp vũ lực mà chúng tôi đã sử dụng cho bộ giải Sudoku của chúng tôi.

Bản demo của thuật toán quay lại

Trong bài viết trước, thuật toán quay lại đã được giới thiệu để giải quyết sudoku bằng cách lặp qua tất cả các giá trị có thể cho mỗi ô cho đến khi không có xung đột giữa giá trị mới được đưa vào bảng và các giá trị của các ô thuộc cùng một hàng, cột hoặc khối. Giải pháp, tuy nhiên hiệu quả, không phải là tối ưu vì nó không sử dụng bất kỳ thông tin nào do Hội đồng quản trị cung cấp.
This solution, however efficient, is far from optimal as it does not make use of any of the information provided by the board.

Tối ưu hóa bằng cách loại bỏ các lần lặp không cần thiết

Ý tưởng đầu tiên để tối ưu hóa mã của chúng tôi đến từ quan sát rằng thuật toán của chúng tôi lặp đi qua tất cả các số 1 đến 9 tuần tự (hàng 9) cho đến khi nó tìm thấy một giá trị không xung đột với một ô khác trong cùng một hàng, cột hoặc khối đã chứa cùng một giá trị . Tuy nhiên, bảng cung cấp cho chúng tôi một số thông tin về những con số nào không thể được thêm vào trong một ô nhất định.

Hàm giải quyết chính () thực hiện quay lại

Ý tưởng là quét bảng trước của chúng tôi, lưu tất cả các giá trị hợp pháp cho mỗi ô trong bộ nhớ và lặp qua chúng thay vì lặp qua tất cả các số. Đồ họa sau đây cho thấy tập hợp các giá trị được phép cho 2 ô của bảng. Vì nó được ngụ ý từ các quy tắc trò chơi, mỗi hàng, cột và khối không thể chứa cùng một số hơn một lần, do đó tất cả các số được tìm thấy trong các ô thuộc cùng một hàng, cột và khối của một ô nhất định được loại trừ.
The following graphic demonstrates the set of allowed values for 2 cells of the board. As it is implied from the game rules every row, column and block cannot contain the same number more than once, thus all numbers found in cells belonging in the same row, column and block of a given cell are excluded.

Giá trị hợp pháp cho 2 ô bảng

Bây giờ ý tưởng của chúng tôi đã rõ ràng, chúng tôi đang chuyển sang thực hiện với mã của chúng tôi. Chúng tôi sẽ tạo 2 chức năng cho nhiệm vụ này:

1. Hàm enable của chúng tôi khởi tạo cấu trúc dữ liệu (từ điển) để lưu các giá trị và lặp lại thông qua các ô của bảng, xác định các giá trị trống và gọi hàm thứ hai của chúng tôi để thực sự thực hiện các điều kiện mà chúng tôi mô tả.

2. Hàm cho phép () có logic tương tự với hàm isValid () mà chúng ta đã thấy trong Phần 1, tuy nhiên trong trường hợp này, nó trích xuất cho mỗi ô một danh sách các số hợp pháp.

Có từ điển bộ đệm của chúng tôi tại chỗ, chúng tôi đã sẵn sàng để kiểm tra xem điều này sẽ giúp tăng cường hiệu suất chương trình của chúng tôi.

Chúng ta cần thay thế hàm giải quyết () bằng một hàm mới SolveWithCache () mong đợi bộ đệm từ điển trong danh sách tham số của nó và lần này chỉ lặp lại thông qua danh sách các giá trị hợp pháp cho mỗi ô thay vì tất cả các số 1.

Kiểm tra mã của chúng tôi sau khi thực hiện tất cả các thay đổi đang cung cấp cho chúng tôi kết quả mong muốn, thời gian thực hiện giảm đáng nể so với phiên bản đầu tiên của chúng tôi:

Thời gian thực hiện của chương trình trên là: 15.41820478439331 s

Tối ưu hóa bằng cách thêm thông tin vào chương trình của chúng tôi

Chuyển từ một lần lặp tốn kém sang bộ đệm được chọn trước của các giá trị là một bước tiến tốt, nhưng vẫn còn rất nhiều việc phải làm để tối ưu hóa thuật toán của chúng tôi.

Có nhiều thông tin về bảng Sudoku chưa được tích hợp vào logic thuật toán của chúng tôi:

Nếu chúng ta nghiên cứu các giá trị hợp pháp của các ô hàng đầu tiên, vì chúng được tạo ra bởi hàm CachevalidValues ​​() của chúng ta, chúng ta thực hiện quan sát rằng một số số xuất hiện dưới dạng giá trị hợp pháp cho nhiều ô và một số số khác cho ít ô hơn. Vì chúng ta đã biết rằng mỗi số từ 1 trận9 chắc chắn sẽ xuất hiện trong mỗi hàng, nên rõ ràng là những con số này xuất hiện ít thường xuyên hơn Các tế bào của hàng.

Để làm cho điều này rõ ràng hơn với một ví dụ trực quan:

Đối với hàng đầu tiên của bảng đã cho, chúng tôi đã trích xuất các giá trị hợp pháp cho từng ô và thêm chúng trong ngoặc. Thu thập các giá trị từ tất cả các ô của hàng 1, chúng tôi nhận thấy rằng số 6 xuất hiện dưới dạng giá trị ứng cử viên chỉ trong 2 ô, trong khi số 1,5,7,9 xuất hiện trong 4 ô khác nhau.

Điều này được dịch thành số 6 có cơ hội phổ biến tốt hơn trong một ô nhất định khi nó cạnh tranh với các số có tần số cao hơn (chỉ dựa trên thông tin được trích xuất bởi hàng).

Cách để tận dụng thông tin là bằng cách đặt hàng danh sách các giá trị hợp pháp cho từng ô (đã được cung cấp trong bộ đệm của chúng tôi) bằng cách có cơ hội trước Có khả năng là các tùy chọn chính xác cuối cùng và chúng tôi sẽ làm cho nó để chúng sẽ trình bày đầu tiên trong thuật toán của chúng tôi khi lặp lại thông qua các giá trị hợp pháp.

Để đạt được điều này, chúng tôi tạo một chức năng mới để đi qua tần suất xuất hiện cho mỗi hàng và sẽ trả về bộ đệm với danh sách các giá trị hợp pháp theo thứ tự:

Hàm đặt hàng

Sau khi sửa đổi mới nhất, chúng tôi cho chương trình của chúng tôi thử và viết ra thời gian thực hiện cho chương trình của chúng tôi:

Thời gian thực hiện của chương trình trên là: 13.673209190368652 s

Đây là một cải tiến so với việc triển khai bộ đệm không có thứ tự trước đây của chúng tôi, nhưng chúng tôi sẽ cố gắng tiến thêm một bước: cho đến nay chúng tôi đã tạo ra một cấu trúc dữ liệu nơi chúng tôi lưu các giá trị tiềm năng cho mỗi ô và chúng tôi đã đặt hàng dựa trên số lượng Thời gian giá trị ứng cử viên này xuất hiện trên các ô của cùng một hàng-ít thường xuyên xuất hiện, chúng tôi sẽ ưu tiên hơn trong quá trình lặp lại.
So far we have created a data structure where we save the potential values for each cell and we ordered them based on how many times this candidate value appears on cells of the same row-the less frequently appears the more priority we give this value during our backtracking iteration.

Ý tưởng tiếp theo là tích hợp trong thuật toán của chúng tôi cũng như thông tin đến từ cột và khối ô. Như được mô tả trong hình ảnh sau đây, đối với tế bào [0] [1] Chúng ta có các giá trị hợp pháp [1,4,5,7,9]. Dựa trên phân tích tần số xuất hiện cho tất cả các ô liên quan đến cái mà chúng ta quan tâm Trong, chúng tôi có thể đặt hàng danh sách các giá trị hợp pháp như sau: [4,7,1,5,9] mà chúng tôi hy vọng sẽ hạn chế các dự đoán sai và do đó lặp lại thuật toán quay lại của chúng tôi.
Based on the appearance frequency analysis for all the cells related to the one we are interested in, we can order the list of legitimate values as following : [4,7,1,5,9] which we hope will limit the wrong guesses and consequently iterations of our backtracking algorithm.

Phân tích xuất hiện tần số đầy đủ cho ô [0] [1]

Sau đó, chúng ta cần tạo một chức năng dài mới để thực hiện logic được mô tả ở trên. Bây giờ chúng tôi không chỉ lặp lại thông qua các ô của một hàng để thu thập tần số xuất hiện, mà còn thông qua các ô của mỗi cột và từng khối.

Ngay khi mã mới của chúng tôi không có lỗi, chúng tôi sẽ cố gắng đo lường hiệu suất:

Thời gian thực hiện của chương trình trên là: 13.849200248718262 s

Chúng tôi nhận thấy rằng logic mới này không cải thiện chương trình của chúng tôi như chúng tôi mong đợi. Thông tin từ các hàng, cột và khối kết hợp không giúp thuật toán của chúng tôi đoán hiệu quả hơn. Tuy nhiên, vẫn còn chỗ để cải thiện đáng kể, như chúng tôi thấy trong Phần III.
There is still room for significant improvement however, as we see in Part III.

Cảm ơn vì đã đọc!