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
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

5 comments:

  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

    ReplyDelete
  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.

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

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

    ReplyDelete
  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.

    ReplyDelete