On Fri, 16 Sep 2005, Bas wrote:
> -any ideas how to easily incorporate advanced solving strategies?
> solve(problem1) and solve(problem2) give solutions, but solve(problem3)
> gets stuck...
the only way to solve arbitrary sudoku problems is to guess.
of course, you have to deal with guessing wrongly, and it helps if you can
make good guesses!
i wrote a solver based entirely on guessing and backtracking a few months
ago; it's fairly simple, although i wrote it in fairly fine-grained java,
so there's actually quite a lot of code. i had a very different program
structure to you, since i was only doing guesswork; i had a recursive
function that looked like this:
def solve(grid):
"""Solves a grid.
The solution is written in the grid; if no solution can be found, does
nothing to the grid. Returns True if a solution was found, False if not.
"""
x, y = pick_an_empty_cell_to_try(grid)
letters = letters_which_can_be_written_in_this_cell(grid, x, y)
if (letters == []):
return False # there are no legal moves; give up
for letter in letters:
grid.write(x, y, letter) # try a move ...
if (solve(grid)):
return True # we win!
grid.erase(x, y) # ... undo it if it didn't work
return False # none of the legal moves work; give up
the implementation of the grid class is pretty straightforward - it's just
a two-dimensional matrix with some bells and whistles.
letters_which_can_be_written_in_this_cell is also fairly simple, although
it can be made a lot faster by keeping summary information in the grid
object: i had a set for each row, column and region saying which letters
had been written already, so the set of available letters was the inverse
of the union of the sets relevant to the cell; the sets were implemented
as bitmaps, so this was all very fast.
the only tricky bit is pick_an_empty_cell_to_try; you can have fun trying
different heuristics here! the nice thing is that it's okay to use quite
computationally expensive heuristics, since a modestly better choice can
save huge numbers of recursions.
there are a number of much, much more advanced algorithms out there, doing
all sorts of clever stuff. however, my algorithm solves any sudoku i can
throw at it (barring seriously unreasonable stuff) in under a second, so
i'm happy with it.
tom
--
I content myself with the Speculative part [...], I care not for the Practick.
I seldom bring any thing to use, 'tis not my way. Knowledge is my ultimate end.
-- Sir Nicholas Gimcrack
--
http://mail.python.org/mailman/listinfo/python-list
