[Haskell-cafe] Code Review: Sudoku solver
Chris Kuklewicz
haskell at list.mightyreason.com
Tue Apr 4 03:59:33 EDT 2006
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
More information about the Haskell-Cafe
mailing list