[Haskell-cafe] Code Review: Sudoku solver

[Chris Kuklewicz]

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