The New Sudoku Players' Forum

[lancelot]

Here I give a brief introduction on how to solve Sudoku using Python with Exact Cover method. I put more technical details in http://lancelot.freehyperspace5.com/Sudoku.php later. Any comments are very welcomed from all of members of the forum.

Sudoku Puzzle Solver Based on Exact Cover Theory
--------------------------------------------------------------------------------
Programmed with Python

Sudoku is a puzzle game to fill 9*9 grids with 1-9 digits so that they appear once in each of 9 rows, 9 columns and 9 3*3 boxes. Solving Sudoku is an exact cover problem.

Using Vijk to denote that the value of the ith row, jth column is l, where k is the index number of the box corresponds to (I,j). Hence there are 4 groups of restrictions to be fulfilled: (i,j), (i,l), (j,l) and (k,l), where (i,j) means at the grid (i,j) there exists one number; (i,l) means value l is in the ith row; (j,l) means value l is in the jth column; (k,l) means value l is in the kth box. The initial Sudoku matrix can be implemented using array datatype once the Numpy module is installed with Python .

Next, let us construct a 729*324 matrix (here is a complete matrix ) for mathematical modeling of the Sudoku problem. Since k is dependent of i and j, there 9*9*9=729 variations of (I,j,k,l). And for each instance of (I,j,k,l), it corresponds to 4 pairs of (i,j), (i,l), (j,l) and (k,l) which total to 4*9*9=324. Use row index r to denote (i,j,k,l) while column index c denote (i,j), (i,l), (j,l) and (k,l) respectively. If (r,c) is connected, M(r,c)=1; otherwise M(r,c)=0.

For a solved Sudoku, it corresponds to 81 chosen rows which cover exactly all 324 columns of M with 1s without any confliction in 1s between each row. This is clearly an exact cover problem.

Given some known conditions to solve Sudoku, it is a good choice to use the back-tracking method.

KAX is an algorithm to solve exact cover problem using back-tracking. Please refer to Wikipedia for detailed description for this algorithm.

The key issue is to design a recursion function to realize KAX in python. For GUI you have the choices of Tkinter, wxPython, PyGTK and PyQT.

The given example is one of the most difficult Sudoku listed in Wikipedia. The PC used here is with Intel T7300 and 2G memory. The problem is solved in less than 10 seconds.

To learn how to program in python, a forum would be very helpful. Python-forum.org is a user-friendly forum for beginners in English. As for Chinese language, python forum in Tsinghua BBS is a good alternative.

Here is an example of solving Sudoku in Python . You can also refer to some other ways in doing so.