Mirrored from Sudopedia, the Free Sudoku Reference Guide

Ariadne's Thread

Wikipedia article: Ariadne's thread

In the Greek myth of Theseus and the Minotaur, Ariadne gave the hero Theseus a ball of string and advised him to pay out the string behind him as he traversed the maze of the Labyrinth. He could then follow the string back to retrace his path and get out of the maze.

Ariadne's Thread is the name used for a method to solve a complex problem, such as a Sudoku puzzle, by exploring possible alternatives, backtracking when an error is encountered. The process ends when either no more alternatives are available, or when a valid solution is found.

Another name for this technique is Guessing with Backtrack. As with all solving techniques that involve making arbitrary conjectures without the aid of logic, Ariadne's Thread is controversial and typically is employed only when other solving techniques fail to advance the puzzle.

Here is a detailed step-by-step procedure for solving a Sudoku with pencil and paper solely using Ariadne's Thread:

  1. START: Mark every cell that is not a clue with the candidate digits 1-9.
  2. If there are no unsolved cells, you have solved the Sudoku. STOP.
  3. Choose an unsolved cell (call it c) and one of its candidate values (call it v). Circle this value.
  4. Make a copy of the Sudoku with c having v as its solved value and proceed using this copy of the puzzle.
  5. Check whether any other cell that shares a box, row, or column with c already has v as a solved value. If not, go to step 2.
  6. You must backtrack. If you are working on the original Sudoku, this means the puzzle is unsolvable. STOP.
  7. Otherwise, discard this copy of the Sudoku and return to the one you copied it from.
  8. Remove the circled candidate from its cell. If this leaves the cell with no candidates, go to step 6.
  9. Otherwise, go to step 2.

Obviously by itself this is a very tedious and time consuming procedure more suitable for a computer program than for humans. But combined with other solving strategies, it can be a useful last resort. At step 2, repeatedly employ your other solving strategies until you are stuck before proceeding with Ariadne's Thread. Note that if you are working on one of the copied Sudokus, the solving strategies may result in a contradiction or unsolvable situation. In that case, go to step 6 and proceed from there.

This page was last modified 17:18, 25 July 2010.