Daniel Fischer wrote:
> does anybody know whether in a uniquly solvable sudoku-puzzle guessing is
> never necessary, i.e. by proper reasoning ('if I put 6 here, then there must
> be a 3 and thus the 4 must go there...' is what I call guessing) there is
> always at least one entry determined?
>
http://www.phil.uu.nl/~oostrom/cki20/02-03/japansepuzzles/ASP.pdf
"As an application, we prove the ASP-completeness (which implies
NP-completeness) of three popular puzzles: Slither Link, Cross Sum, and Number
Place."
As the size of the puzzle N increases, it is np-complete.
(3x3x3,4x4x4,5x5x5,...)
And the definition of "logic" vs "brute force" is a imprecise. Complex logic
looks like "hypothetical guess and check", and the efficient dancing links
algorithm by Knuth is very smart brute force.
--
Chris
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
