Sudoku Solver - The Obvious Next Step

     So last time I spoke about how creating the constraints checking analyzer was not the best idea I had had. While my solver was smarter, it was far slower. I needed a different tack to make the solver smarter AND faster. Now the obvious next step occured to me as has probably occured to anyone else who has ever attempted this problem. Humans solve sudoku, not by solving just any random cell, but by solving the cell with the LEAST number of choices.  

    Here's escargot, almost solved. We have three unsolved cells and two and six are the only remaining numbers. I've color coded the unsolved cells. Now as I described before here, we can visualize the process of filling in all the remaining cells as a huge directed graph leading us to the final state, where the entire puzzle is solved. So I've done that and attached that image here. 

    So the idea is that the black circle at the top represents our initial state. Green represents a state where we fill in  the green square, red the red square and blue the blue square. The arrow mentions what number we use. The exception to the color rule is the final black square. Depending on which route we take to get there it would have a different color obviously. But thats the state when the puzzle is complete. As discussed previously, there are multiple routes to get from the beginning to the end. Now here's a very simple puzzle where the green square starts off with 2 options and the other squares one option each. This is what the older solver does.

     We pick the first cell to play, which is the green square and play two. We reach a dead end, so then we play six. Once we do that the other cells fall into play. Now if we try the newer approach and first play the most constrained cell, it looks like this

    So the human tendency to play the cell with the least options first, essentially converts that really complicated graph to a tree with far FEWER branches than if we had played the first cell that was free every turn. As an added bonus, checking for the constraints of every cell each turn is bound to also help detect dead ends or bad branches early. Now in this case we saw one cell with 2 options and the other cells with 1 option. In a complete game the variation is far greater. So let's modify the solver and see how it does.

Solved hard with 83 moves and 29 rollbacks in 0.098862 seconds
Solved evil with 217 moves and 161 rollbacks in 0.249229 seconds
Solved escargot with 217 moves and 159 rollbacks in 0.250393 seconds
Solved simple with 45 moves and 0 rollbacks in 0.040218 seconds
Solved other_hard with 69 moves and 8 rollbacks in 0.106688 seconds

Analyzer::LeastChoicesFirst ran 5 puzzles in 0.745781 seconds with 631 moves and 357 rollbacks

    That's a fantastic improvement. The number of moves has come down to 631 from 36,000. And the time has come down to 0.74 seconds.Which is about nearly 1/10th of the original. Great success! There's more to come though.

Here's the code

class LeastChoicesFirst < analyzer="nil)" cells_with_values =" game.empty_cells.sort.collect{|cell|" possible_values =" cells_with_values.min{|pair_1,"> pair_2[1].length}
   end
 end