Ariadne's thread (logic)

Ariadne's thread, named for the legend of Ariadne, is the solving of a problem with multiple apparent means of proceeding - such as a physical maze, a logic puzzle, or an ethical dilemma - through an exhaustive application of logic to all available routes. It is the particular method used that is able to follow completely through to trace steps or take point by point a series of found truths in a contingent, ordered search that reaches an end position. This process can take the form of a mental record, a physical marking, or even a philosophical debate; it is the process itself that assumes the name.

The key element to applying Ariadne's thread to a problem is the creation and maintenance of a record - physical or otherwise - of the problem's available and exhausted options at all times. This record is referred to as the "thread", regardless of its actual medium. The purpose the record serves is to permit backtracking - that is, reversing earlier decisions and trying alternatives. Given the record, applying the algorithm is straightforward:

This algorithm will terminate upon either finding a solution or marking all initial choices as failures; in the latter case, there is no solution. If a thorough examination is desired even though a solution has been found, one can revert to the previous decision, mark the success, and continue on as if a solution were never found; the algorithm will exhaust all decisions and find all solutions.

The terms "Ariadne's thread" and "trial and error" are often used interchangeably, which is not necessarily correct. They have two distinctive differences:

Obviously, Ariadne's thread may be applied to the solving of mazes in the same manner as the legend; an actual thread can be used as the record, or chalk or a similar marker can be applied to label passages. If the maze is on paper, the thread may well be a pencil.

Logic problems of all natures may be resolved via Ariadne's thread, the maze being but an example. At present, it is most prominently applied to Sudoku puzzles, used to attempt values for as-yet-unsolved cells. The medium of the thread for puzzle-solving can vary widely, from a pencil to numbered chits to a computer program, but all accomplish the same task. Note that as the compilation of Ariadne's thread is an inductive process, and due to its exhaustiveness leaves no room for actual study, it is largely frowned upon as a solving method, to be employed only as a last resort when deductive methods fail.

...
Wikipedia