Sudoku Solver using Simulated Annealing

Here is my failed attempt to solve Sudoku using Simulated Annealing. ( I think it is good to fail – it makes me learn 🙂 )

Input to the algorithm – initial Sudoku board configuration – set of 81 numbers – where a missing number in the board is indicated by -1.

Algorithm :

We choose random numbers between (1-9) and allocate it to 2 random ( not fixed i.e not already given numbers in the input ) cells on each sub-square* – making sure that each sub-square has no repeated integers.

* There are 9 sub-squares in the Sudoku board

The cost function for the algorithm is the number of integers between (1-9) which are not used per row and per column and sum those values across the grid.

The algorithm then tries to minimize the above cost function and then it follows the general Simulated Annealing pattern of reducing the temperature.

The Alpha value chosen by the algorithm is .94

However, using the above value of Alpha – algorithm has not converged to the solution.

The output of the algorithm prints out the resultant Grid and the best possible result.
The output also includes the number of Integers which are still mis-positioned.

Most of the runs of the algorithm end up between 5-6-7 numbers still out of place.

Command to run the code

python SudokuSolver -1 -1 -1 -1 -1 7 5 -1 4 -1 3 6 4 -1 -1 -1 -1 2 -1 -1 -1 -1 6 -1 -1 7 8 -1 -1 -1 5 1 -1 2 -1 -1 -1 -1 -1 -1 -1 9 -1 -1 -1 -1 -1 -1 2 -1 4 -1 -1 1 -1 -1 -1 8 9 -1 -1 -1 6 1 5 -1 7 3 -1 -1 -1 -1 -1 2 9 1 -1 5 -1 8 3

Code

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s