In some cases you might want the algorithm that solves them to also give you some kinda hint on how hard it would be for a human to solve it.
The most efficient algorithm I know of to solve these kind of problems is Knuth's Dancing Links X algorithm. It's beautiful and very fun to implement.
I have a simple ruby implementation of it geared to solve sudokus online on github: https://github.com/biilmann/Ruby-DLX-Sudoku-Solver
I think the complexity class of Sudoko is NP-Complete (a quick google confirms it's not exactly NP but very close: http://11011110.livejournal.com/23221.html?thread=19381 -- complexity is the same as solving SAT problems which have only one unique solution)
He discusses the strategies used here: http://www2.research.att.com/~gsf/sudoku/
> The solver uses depth first and/or breadth first with constraint propagation to prune the search
That would be backtracking.
Further, the purpose of many the constraint techniques seem to be aimed at creating puzzles that are amenable to humans, not solving them. The article itself states that for solving, backtracking with fewer constraints performs better.
I shared the link because I found his sudoku generator and the constraint methods interesting.
> That would be backtracking.
Let me quote the first para in full:
The solver uses depth first and/or breadth first tree search
with constraint propagation to prune the search for the next
best move (forms of forward checking.) There are space/time
tradeoffs between depth/breadth first search and the constraints
used; sudoku(1) has options to control the combinations.
The common characteristic for all constraints, here and elsewhere,
is that they avoid trial and error. Its fine for a computer
to guess and backtrack but a definite breach of puzzle manners
to require a human to do so.
They're typically designed to be unambiguous (only one correct solution), so in that sense there is always a 'correct' move.
However, finding that correct move is exactly as hard, in the computational sense, as finding the solution to the entire puzzle.
> . . . | . . . | . 1 2
> . . . | . . . | . . 3
> . . 2 | 3 . . | 4 . .
> . . 1 | 8 . . | . . 5
> . 6 . | . 7 . | 8 . .
> . . . | . . 9 | . . .
> . . 8 | 5 . . | . . .
> 9 . . | . 4 . | 5 . .
> 4 7 . | . . 6 | . . .
There should only be one solution. Enjoy yourself, and remember: No guessing! (Source: http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Exceptio...)
It isn't computationally relevant but even if trial and error were a simpler approach I feel like that is not in the spirit of the game. Sudoku is a number maze, the goal is to backtrack.
Also I refuse to attempt something that is supposedly too difficult for humans to solve, I'm incapable of quitting puzzles and don't relish spending the next X hours proving it can be done :)
Within the set of initial grids that have unambiguous solutions there are ones which require guessing or backtracking, these are generally not considered proper Sudokus and are not presented to humans to solve.
A Sudoku is not a destination, it is a journey.
I'd be very interested to see what an algorithm that solves any valid sudoku puzzle looks like. (apart from pathologic solutions like querying a database of all valid 9x9 sudoku combinations).
Edit: using the symmetries described in the same Wikipedia article, the size of the database could be reduced significantly to roughly 5*10^9, which is quite manageable.
You might be interested in the article linked to by this post.