Sudoku is solved using simulated annealing
-
The program accepts a partially completed sudoku grid, where 0 represent an empty spot.
-
All the 9 3x3 sub grids are filled with numbers which are feasible for that grid ie. this random filling will take care of the one of the three constraints of the problem. Thus all the 9 sub grids will have 1-9 exactly once.
-
Next a loop is run until the minimum temperature is achieved.
-
Select a random sub grid.
-
Select two random mutable points ( ie. 0 in given sudoku ) randomly.
-
Swap the values of these randomly selected points.
-
Calculate the energy or fitness. The fitness function used here is: (81*2) - ( total number of unique numbers in each row and column ). When the sudoku is solved this energy will be zero.
-
Accept the new state if its energy is lower than the previous state.
-
Else still accept or reject the new state with the acceptance probability.
-
Decrease the temperature according to the cooling schedule ( current_temperture * 0.8 ).
make
./sudoku_solver test_input.in
Where test_input.in is a file containing a sudoku problem.