Sudoku solver in Ruby

I decided to try writing a sudoku solver back when I first wanted to learn ruby. For some reason I had gotten it into my head that brute forcing would take a long time. This clearly isn't true. Eitherway back then I couldn't think of a way to solve it that did not involve backtracking. But it made sense for me to first get it working before I found a way to improve it.

I designed it so that I had a generic backtracking solver class that could accept any "problem analyzer". The back tracking solver would ask the analyzer to suggest a list of valid moves. It would save the state, make one move and then ask the analyzer to make another suggestion. Anytime the analyzer had no suggestions, it would backtrack.

Then I designed it with the simplest problem analyzer I could think of. This would pick up the first empty cell. Throw in any of the legal numbers in that cell (anything that wasn't in the row, column or block and from the range 1-9). 

So how did it do? Well in order to test it I searched the net for various sudoku puzzles and put in 5 puzzles as my test cases. One website had 3 grades of puzzles. Simple, Hard and Evil. I found on another site another hard puzzle. And finally on the internet I found this puzzle called escargot which apparently was the hardest sudoku puzzle ever.  Here are the results

Solved hard with 22873 moves and 22819 rollbacks in 1.191012 seconds
Solved evil with 61125 moves and 61069 rollbacks in 3.105755 seconds
Solved escargot with 8969 moves and 8911 rollbacks in 0.482827 seconds
Solved simple with 68 moves and 23 rollbacks in 0.004692 seconds
Solved other_hard with 14407 moves and 14346 rollbacks in 0.73989 second
Analyzer::Simple ran 5 puzzles in 5.524553 seconds with 107442 moves and 107168 rollbacks 

So here's the code for the Solver and the simple analyzer.

class BackTrackingSolver
  def initialize(analyzer_klass, question)
    @game = Game.new(question)
    @analyzer_klass = analyzer_klass
    @moves = 0
    @rollbacks = 0
  end
  
  attr_reader :moves, :rollbacks

  def solution
    raise "could not solve" unless solve
    @game.cell_values
  end

 def solve(analyzer=nil)
   return true if @game.complete?
   analyzer = @analyzer_klass.new(@game, analyzer)
   analyzer.each do |cell, value|
     make_move cell, value
     return true if solve(analyzer)
     rollback cell
   end
   false
  end

  def make_move(cell, value)
    @game[cell] = value
    @moves += 1
  end

  def rollback(cell)
    @game.clear(cell)
    @rollbacks += 1
  end 
end

module Analyzer
  class Base
    @@numbers = (1..9).to_a
    
    def possible_values(game, cell)
      @@numbers - game.neighbour_values(cell)
    end

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

 class Simple < Base
   def initialize(game, analyzer=nil)
   @cell = game.empty_cells.first
   @possible_values = possible_values(game, @cell)
  end
end