Ariadne's thread (logic)
Encyclopedia
Ariadne's thread, named for the legend of Ariadne
, is the term used to describe 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 a desired 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.
- 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.
" are often used interchangeably, which is not necessarily correct. They have two distinctive differences:
In short, trial and error approaches a desired solution; Ariadne's thread blindly exhausts the search space completely, finding any and all solutions. Each has its appropriate distinct uses. They can be employed in tandem - for example, although the editing of a Wikipedia article is arguably a trial-and-error process (given how in theory it approaches an ideal state), article histories provide the record for which Ariadne's thread may be applied, reverting detrimental edits and restoring the article back to the most recent error-free version, from which other options may be attempted.
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.
Artificial intelligence is heavily dependent upon Ariadne's thread when it comes to game-playing, most notably in programs which play chess
; the possible moves are the decisions, game-winning states the solutions, and game-losing states failures. Due to the massive depth of many games, most algorithms cannot afford to apply Ariadne's thread entirely on every move due to time constraints, and therefore work in tandem with a heuristic
that evaluates game states and limits a breadth-first search
only to those that are most likely to be beneficial, a trial-and-error process.
Even circumstances where the concept of "solution" is not so well defined have had Ariadne's thread applied to them, such as navigating the World Wide Web
, making sense of patent law, and in philosophy; "Ariadne's Thread" is a popular name for websites of many purposes, but primarily for those that feature philosophical or ethical debate.
Ariadne
Ariadne , in Greek mythology, was the daughter of King Minos of Crete, and his queen Pasiphaë, daughter of Helios, the Sun-titan. She aided Theseus in overcoming the Minotaur and was the bride of the god Dionysus.-Minos and Theseus:...
, is the term used to describe the solving of a problem with multiple apparent means of proceeding - such as a physical maze
Maze
A maze is a tour puzzle in the form of a complex branching passage through which the solver must find a route. In everyday speech, both maze and labyrinth denote a complex and confusing series of pathways, but technically the maze is distinguished from the labyrinth, as the labyrinth has a single...
, a logic puzzle
Logic puzzle
A logic puzzle is a puzzle deriving from the mathematics field of deduction.-History:The logic puzzle was first produced by Charles Lutwidge Dodgson, who is better known under his pen name Lewis Carroll, the author of Alice's Adventures in Wonderland...
, or an ethical dilemma
Ethical dilemma
An Ethical dilemma is a complex situation that will often involve an apparent mental conflict between moral imperatives, in which to obey one would result in transgressing another....
- 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 a desired 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.
Implementation
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 backtrackingBacktracking
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
- that is, reversing earlier decisions and trying alternatives. Given the record, applying the algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
is straightforward:
- At any moment that there is a choice to be made, make one arbitrarily from those not marked as failures, and follow it logically as far as possible.
- If a contradiction results, back up to the last decision made, mark it as a failure, and try another decision at the same point. If no other options exist there, back up to the last place in the record that does, mark the failure at that level, and proceed onward.
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.
Distinction from trial and error
The terms "Ariadne's thread" and "trial and errorTrial and error
Trial and error, or trial by error, is a general method of problem solving, fixing things, or for obtaining knowledge."Learning doesn't happen from failure itself but rather from analyzing the failure, making a change, and then trying again."...
" are often used interchangeably, which is not necessarily correct. They have two distinctive differences:
- The term "trial and error" implies that each "trial" yields some particular value to be studied and improved upon, removing "errors" from each iteration to enhance the quality of future trials. Ariadne's thread has no such mechanic, making all decisions arbitrarily. For example, the scientific methodScientific methodScientific method refers to a body of techniques for investigating phenomena, acquiring new knowledge, or correcting and integrating previous knowledge. To be termed scientific, a method of inquiry must be based on gathering empirical and measurable evidence subject to specific principles of...
is trial and error; puzzle-solving is Ariadne's thread.
- Trial-and-error approaches are rarely concerned with how many solutions may exist to a problem, and indeed often assume only one correct solution exists (as in a scientific formula). Ariadne's thread makes no such assumption, and is capable of locating all possible solutions to a purely logical problem.
In short, trial and error approaches a desired solution; Ariadne's thread blindly exhausts the search space completely, finding any and all solutions. Each has its appropriate distinct uses. They can be employed in tandem - for example, although the editing of a Wikipedia article is arguably a trial-and-error process (given how in theory it approaches an ideal state), article histories provide the record for which Ariadne's thread may be applied, reverting detrimental edits and restoring the article back to the most recent error-free version, from which other options may be attempted.
Applications
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
Sudoku
is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid contains all of the digits from 1 to 9...
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.
Artificial intelligence is heavily dependent upon Ariadne's thread when it comes to game-playing, most notably in programs which play chess
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
; the possible moves are the decisions, game-winning states the solutions, and game-losing states failures. Due to the massive depth of many games, most algorithms cannot afford to apply Ariadne's thread entirely on every move due to time constraints, and therefore work in tandem with a heuristic
Heuristic
Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...
that evaluates game states and limits a breadth-first search
Breadth-first search
In graph theory, breadth-first search is a graph search algorithm that begins at the root node and explores all the neighboring nodes...
only to those that are most likely to be beneficial, a trial-and-error process.
Even circumstances where the concept of "solution" is not so well defined have had Ariadne's thread applied to them, such as navigating the World Wide Web
World Wide Web
The World Wide Web is a system of interlinked hypertext documents accessed via the Internet...
, making sense of patent law, and in philosophy; "Ariadne's Thread" is a popular name for websites of many purposes, but primarily for those that feature philosophical or ethical debate.
In other media
- In the movie InceptionInceptionInception: The Subconscious Jams 1994-1995 is a compilation of unreleased tracks by the band Download.-Track listing:# "Primitive Tekno Jam" – 3:23# "Bee Sting Sickness" – 8:04# "Weed Acid Techno" – 8:19...
, Ariadne is the name of a character who plays a crucial role creating labyrinths. - It is used as an item in the video game Etrian Odyssey III, as a way to escape from the maze.
See also
- LabyrinthLabyrinthIn Greek mythology, the Labyrinth was an elaborate structure designed and built by the legendary artificer Daedalus for King Minos of Crete at Knossos...
- AriadneAriadneAriadne , in Greek mythology, was the daughter of King Minos of Crete, and his queen Pasiphaë, daughter of Helios, the Sun-titan. She aided Theseus in overcoming the Minotaur and was the bride of the god Dionysus.-Minos and Theseus:...
- BacktrackingBacktrackingBacktracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
- Deductive reasoningDeductive reasoningDeductive reasoning, also called deductive logic, is reasoning which constructs or evaluates deductive arguments. Deductive arguments are attempts to show that a conclusion necessarily follows from a set of premises or hypothesis...
- Computer chessComputer chessComputer chess is computer architecture encompassing hardware and software capable of playing chess autonomously without human guidance. Computer chess acts as solo entertainment , as aids to chess analysis, for computer chess competitions, and as research to provide insights into human...
- J. Hillis MillerJ. Hillis MillerJoseph Hillis Miller, Jr. is an American literary critic who has been heavily influenced by—and who has heavily influenced—deconstruction.- Early life and education :...