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
def initialize(analyzer_klass, question)
@game = Game.new(question)
@analyzer_klass = analyzer_klass
@moves = 0
@rollbacks = 0
attr_reader :moves, :rollbacks
raise "could not solve" unless solve
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)
def make_move(cell, value)
@game[cell] = value
@moves += 1
@rollbacks += 1
@@numbers = (1..9).to_a
def possible_values(game, cell)
@@numbers - game.neighbour_values(cell)
@possible_values.each do |value|
yield @cell, value
class Simple < Base
def initialize(game, analyzer=nil)
@cell = game.empty_cells.first
@possible_values = possible_values(game, @cell)
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.
Luis Sergio Oliveira
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
You might as well github the lot...ReplyDelete
almost there ;-) and yeah that makes senseReplyDelete
For those who might be interested, http://this1that1whatever.com/miscellany/sudoku/ offers Sudoku puzzles to solve. (more test cases!)ReplyDelete
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.