Editing Backtracking (section)

{{Short description|Search algorithm}}
{{for|the [[line search]] algorithm used in [[Mathematical optimization|unconstrained optimization]]|Backtracking line search}}
{{Use dmy dates|date=September 2022}}

'''Backtracking''' is a class of [[algorithm]]s for finding solutions to some [[computational problem]]s, notably [[constraint satisfaction problem]]s, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.<ref>{{cite web | url=http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html | title=CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms | year=1999 |last=Gurari|first=Eitan|archive-url= https://web.archive.org/web/20070317015632/http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html#QQ1-51-128|archive-date=17 March 2007}}</ref>

The classic textbook example of the use of backtracking is the [[eight queens puzzle]], that asks for all arrangements of eight [[chess]] [[queen (chess)|queens]] on a standard [[chessboard]] so that no queen attacks any other.  In the common backtracking approach, the partial candidates are arrangements of ''k'' queens in the first ''k'' rows of the board, all in different rows and columns.  Any partial solution that contains two mutually attacking queens can be abandoned.

Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution.  It is useless, for example, for locating a given value in an unordered table.  When it is applicable, however, backtracking is often much faster than [[brute-force search|brute-force enumeration]] of all complete candidates, since it can eliminate many candidates with a single test.

Backtracking is an important tool for solving [[constraint satisfaction problem]]s,<ref name="BiereHeule2009">{{cite book |first1=A. |last1=Biere |first2=M. |last2=Heule |first3=H. |last3=van Maaren|title=Handbook of Satisfiability|url=https://books.google.com/books?id=shLvAgAAQBAJ&q=backtracking|date=29 January 2009|publisher=IOS Press|isbn=978-1-60750-376-7}}</ref> such as [[crosswords]], [[verbal arithmetic]], [[Algorithmics of sudoku|Sudoku]], and many other puzzles.  It is often the most convenient technique for [[parsing]],<ref name="Watson2017">{{cite book|first=Des |last=Watson|title=A Practical Approach to Compiler Construction|url=https://books.google.com/books?id=05B0DgAAQBAJ&q=backtracking|date=22 March 2017|publisher=Springer|isbn=978-3-319-52789-5}}</ref> for the [[knapsack problem]] and other [[combinatorial optimization]] problems.  It is also the program execution strategy used in the programming languages [[Icon programming language|Icon]], [[Planner programming language|Planner]] and [[Prolog]].

Backtracking depends on user-given "[[procedural parameter|black box procedure]]s" that define the problem to be solved, the nature of the partial candidates, and how they are extended into complete candidates.  It is therefore a [[metaheuristic]] rather than a specific algorithm&nbsp;– although, unlike many other meta-heuristics, it is guaranteed to find all solutions to a finite problem in a bounded amount of time.

The term "backtrack" was coined by American mathematician [[Derrick Henry Lehmer|D. H. Lehmer]] in the 1950s.<ref>{{cite book
 | title= Handbook of Constraint Programming
 | url= https://books.google.com/books?id=Kjap9ZWcKOoC
 | first1= Francesca
 | last1= Rossi
 | first2= Peter 
 | last2=van Beek
 | first3= Toby
 | last3=Walsh
 | date= August 2006
 | page= 14
 | chapter= Constraint Satisfaction: An Emerging Paradigm
 | chapter-url= https://books.google.com/books?id=Kjap9ZWcKOoC&pg=PA14
 | publisher= [[Elsevier]]
 | location= [[Amsterdam]]
 | isbn= 978-0-444-52726-4
 | access-date= 30 December 2008
}}</ref> The pioneer string-processing language [[SNOBOL]] (1962) may have been the first to provide a built-in general backtracking facility.