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