I had written about optimising the sudoku solver by remembering moves made in the past. Another strategy that I had tried parallely was to do a short-circuit evaluation. Each iteration of the solver is about searching all the empty cells to find the list of acceptable moves and then choosing the cell with the least moves. However, clearly a cell with zero options means that it's time to backtrack. Clearly instead of continuing to search the list of cells, that's a place to jump out of a search. Similarly a cell with one option means that there is only one option so I might as well make that move.
I experimented with a short circuited search where I jumped out the minute I found something with some "n" moves and I varied "n" from upwards. It turned out the best option was to jump out when I had zero or one option. Sadly this optimisation only gives me a factor of 3 improvement, and doesn't stack much with the previous one.
Anyway the whole code is available at github -> http://github.com/pathsny/Sudoku-Solver
thanks for the code :)
ReplyDelete