3 ms·
That is not true. They're typically designed to be unambiguous (only one correct solution), so in that sense there is always a 'correct' move. However, findin
by crux_ 16y ago
That is not true.
They're typically designed to be unambiguous (only one correct solution), so in that sense there is always a 'correct' move.
However, finding that correct move is exactly as hard, in the computational sense, as finding the solution to the entire puzzle.
> . . . | . . . | . 1 2
> . . . | . . . | . . 3
> . . 2 | 3 . . | 4 . .
> ------+-------+------
> . . 1 | 8 . . | . . 5
> . 6 . | . 7 . | 8 . .
> . . . | . . 9 | . . .
> ------+-------+------
> . . 8 | 5 . . | . . .
> 9 . . | . 4 . | 5 . .
> 4 7 . | . . 6 | . . .
There should only be one solution. Enjoy yourself, and remember: No guessing! (Source: http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Exceptionally_difficult_Sudokus_.28hardest_Sudokus.29 http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Exceptio...)
- thret 16y agoWell, an ambiguous Sudoku is like a 12 line sonnet... It isn't computationally relevant but even if trial and error were a simpler approach I feel like that is not in the spirit of the game. Sudoku is a number maze, the goal is to backtrack. Also I refuse to attempt something that is supposedly too difficult for humans to solve, I'm incapable of quitting puzzles and don't relish spending the next X hours proving it can be done :)
- crux_ 16y agoI believe the above puzzle has only one valid solution.
- jws 16y ago9x9 grid of digits with an ambiguous solution is not a Sudoku. It is part of the definition. Within the set of initial grids that have unambiguous solutions there are ones which require guessing or backtracking, these are generally not considered proper Sudokus and are not presented to humans to solve. A Sudoku is not a destination, it is a journey.
- T-hawk 16y agoIf a Sudoku has one and only one solution, then it is always solvable without guessing or backtracking. It just might not be within the scope of the human brain. There exist (many) configurations where every cell is influenced by every other, so to solve any one cell essentially requires a simultaneous solve of the entire puzzle. There's no theoretical reason a human couldn't do that too; it's a problem simply of computational capacity not fundamental approach.
- crux_ 16y agoHow would you structure a program to solve such a puzzle without having it generate and test potential solutions along the way?