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 secondsSolved evil with 61125 moves and 61069 rollbacks in 3.105755 secondsSolved escargot with 8969 moves and 8911 rollbacks in 0.482827 secondsSolved simple with 68 moves and 23 rollbacks in 0.004692 secondsSolved other_hard with 14407 moves and 14346 rollbacks in 0.73989 secondAnalyzer::Simple ran 5 puzzles in 5.524553 seconds with 107442 moves and 107168 rollbacks *

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

Hi Vishnu,

ReplyDeletethanks 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

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.

ReplyDeleteYou might as well github the lot...

ReplyDeletealmost there ;-) and yeah that makes sense

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

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