## Tuesday, July 28, 2009

### 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 endmodule 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)  endend`

1. Hi Vishnu,

thanks for the post, I think I'm going to try this. Specifically, the backtracking part of the Solver is something I haven't seen before, although I already heard about it in conversations with persons from computer science.

I noted that your code isn't complete, being the Game class missing and of course the tests, although these are simple to reproduce without knowing very much about Ruby.

Regards,

Luis Sergio Oliveira

2. Sure thing, have fun :). I didnt post all the classes to avoid spamming the blog. I will however link to the whole thing once I'm done with a series of posts on sudoku.

3. You might as well github the lot...

4. almost there ;-) and yeah that makes sense

5. For those who might be interested, http://this1that1whatever.com/miscellany/sudoku/ offers Sudoku puzzles to solve. (more test cases!)

I implemented a brute-force with backtracking method (C implementation with recursion) to solve Sudoku puzzles. Making the program solve an empty board results in Sudoku solution boards from which I generate Sudoku puzzles for my web implementation.