Sudoku Solver - Remembering The Past

The sudoku solver is fairly fast and seems to be doing all the right things. By choosing the cells with the least options the number of useless moves has been reduced considerably. However, there is a fair amount of rework thats currently going on. Every time the state of the game is analyzed, the entire board is scanned to find all possible numbers that can be stored in each empty cell. Once a single cell is filled a new iteration begins. Again, this analysis is repeated by scanning the whole board. But, human's don't do that!

Once I've decided what numbers are playable in each empty cell. I don't repeat this exercise everytime I fill up an empty cell. Most empty cells are not affected by any single cell being filled. If I fill a cell that used to be empty, the only empty cells that are affected are cells that shared a row, column or block with the filled cell. So between iterations, if the analysis of the game was to be saved, I could quickly obtain an analysis for the next iteration by slightly modifying the analysis of the previous iteration. OfCourse this is going to take considerably more code to do, but it should show significant improvements.

Now unfortunately I haven't saved the results of running all this on the machine I used when I first started blogging all this. So the times I paste will not be comparable but will have to be scaled a bit. So Ill repost the highlights of previous runs.

Analyzer::Simple ran 5 puzzles in 3.115519 seconds with 107442 moves and 107168 rollbacks
Analyzer::LeastChoicesFirst ran 5 puzzles in 0.412483 seconds with 631 moves and 357 rollbacks

So last time we saw an improvement of a factor of ten. And now, here is the result of the latest change.

Solved simple with 45 moves and 0 rollbacks in 0.035017 seconds
Solved hard with 83 moves and 29 rollbacks in 0.010338 seconds
Solved evil with 217 moves and 161 rollbacks in 0.024111 seconds
Solved escargot with 217 moves and 159 rollbacks in 0.023176 seconds
Solved other_hard with 69 moves and 8 rollbacks in 0.009236 seconds

Analyzer::StorageBasedLeast ran 5 puzzles in 0.102331 seconds with 631 moves and 357 rollbacks

That's a speed up of about 4 times. This is pretty good. As always the code follows. Notice that this time my analyzer actually has to expose read attributes so that the state can be preserved from one iteration to the next. This series of posts is nearly done. I have one more post which will follow where I'll also link to the entire code on github.

class StorageBasedLeast < Base
     attr_reader :cells_with_values, :cell, :value

     def initialize(game, analyzer=nil)
       @cells_with_values = find_cells_with_values(game, analyzer)
       @cell, @possible_values = cells_with_values.min{|pair_1, pair_2| pair_1[1].length <=> pair_2[1].length}
     end


    def each
       @possible_values.each do |value|
          @value = value
          yield @cell, value
       end
    end

    def find_cells_with_values(game, analyzer)
       return game.empty_cells.collect{|cell| [cell, possible_values(game, cell)]} unless analyzer
       cells_with_values = analyzer.cells_with_values.reject{|pair| pair[0] == analyzer.cell}
       neighbours = game.neighbour_indices(analyzer.cell)
       cells_with_values.collect do |pair|
          values = neighbours.include?(pair[0]) ? pair[1] - [analyzer.value] : pair[1]
          [pair[0],values]
       end
    end
end