Search the Community
Showing results for tags 'NP-Complete'.
Found 1 result
Sudoku: NP-CompleteI just tried Sudoku for the first time today - I went straight to "Evil," thinking that it was possible to look at the puzzle, and solve it based on what you see (using "candidate numbers" in the blank cubes). I solved the first puzzle in about thirty minutes, and didn't see what the big deal was (although I couldn't have done it without using the candidate numbers as a sort of "scratch pad"). Then I tried another one, and worked my way into a dead end - every single possibility staring at me was ambiguous, and it was then-and-there that I realized that Sudoku puzzles are NP-complete, and that there's no way to guarantee their solution without "peeking into the future," choosing between one number and another, and going forward until you either solve the puzzle, or hit a dead end. For this, it would require a separate "scratch pad," so that if you hit the dead end, you could undo your work. When I realized this, I realized that Sudoku is a puzzle best left for Turing Machines, and not for the human mind. In a worst-case scenario, a 9-row by 9-column Sudoku puzzle requires 9**9 (9 to the ninth power) combinations. They're *always* solvable (if designed correctly), but they aren't solvable unless you're willing to "peak into the future" and see if your choice was right or wrong. Fo dat sheet.