From Sudopedia, the free Sudoku reference guide

From Sudopedia

The article currently states that Ariadne's Thread assumes that the Sudoku has a unique solution.

I don't think this is true. Here is an algorithmic outline of Ariadne's Thread as it applies to Sudoku:

1. For each solved cell (including initial clues), eliminate its value as a candidate from all cells that share a house with that cell.
2. Proceed to the first unsolved cell (call it c). Choose its first candidate value (call it v).
3. Make a copy of the Sudoku, but consider c solved with value v.
4. Apply the rules of Sudoku to the grid:
   1. For each solved cell, eliminate its value as a candidate from all cells that share a house with the solved cell.
   2. If any cell is left with only one candidate, mark that cell as solved and repeat this step as long as it results in newly-solved cells.
5. If all cells are solved, we have discovered the solution for the puzzle.
6. Otherwise, check the puzzle for unsolved cells with no candidates. The existence of such a cell means that our assumption (that c has the value v) must be wrong. We must backtrack:
   1. Discard the copy of the Sudoku.
   2. Remove v as a candidate from cell c. Mark c as solved if it has only one remaining candidate.
7. Repeat the entire algorithm.

This algorithm works just fine on Sudokus with more than one solution. In fact, if you hand it a puzzle with no clues whatsoever, it ends up constructing a Sudoku.

Professor Prune 15:45, 2 February 2008 (EST)

I put in the 4 February 2008 edit. I forgot to log in first, so it didn't go under my name. Sorry about that!

Professor Prune 15:53, 4 February 2008 (EST)