Brute force sudoku cracker

[Tom Anderson]

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