Subj : Re: Help finishing my sudoku solver
To   : comp.programming
From : websnarf
Date : Tue Jul 19 2005 11:30 pm

pplppp@gmail.com wrote:
> does anyone have an algorithm to determine whether a sodoku puzzle is
> solvable or not? (not the brute force approach of course) And what how
> to determine the minimum number of cells that need to be pre-set in
> order for the puzzle to have no more than 1 solution?
>
> if this is not the right forum please suggest the right one thanks
> any input is appreciated

http://en.wikipedia.org/wiki/Sudoku

Amongst the things noted is the fact that solving them in general, is
NP-complete.

I am pretty sure that the number of starting numbers you require for
the solution to be deterministic varies a lot with the position and
actual values of the numbers.  The semi-brute force solver I wrote and
linked in my earlier post on this can easily be extended to be a full
brute force solver, meaning that it could correctly categorize any
starting position as "impossible", "single solution" or "multiple
solutions".  However, so far I have not yet encountered a puzzle that
my program could not properly classify into one of those three
categories as is.

Oh yes, and my program has pretty good performance, so you could also
easily write a search program on top of it to look for valid puzzles.

-- 
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

.