From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Systems (Rated Start-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Systems, which collaborates on articles related to systems and systems science.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
Taskforce icon
This article is within the field of Operations research.


I don't know who copied from whom, maybe both from a third party even. But this article is almost identical to the Wikipedia article: Marcus

It looks to me like this version existed only after the Wikipedia version of similar wording. I'd bet dollars to donuts they copied the Wikipedia article. --Cheeser1 (talk) 05:20, 12 January 2008 (UTC)

Muddle Rationale[edit]

The rationale expressed in this article is often muddled, internally inconsistent and possibly inconsistent with related material, e.g.

Consider the original text, before my paltry cleanup:

-- When backtracking is used in a constraint programming language, it has an added complication that the information stored about the constraints needs to be updated as well. In these languages, a simple depth first search is an adequate implementation technique, as it is in Planner and Prolog. In implementing backtracking, it is common to keep a variable trail, to record the changes in the values of a particular variable. A smart implementor will avoid creating a variable trail between two successive changes when there is no choice point, as the backtracking will erase all of the changes as a single operation. --

Re: The phrase 'has an added complication that the information stored' is clueless about what 'the information' is or who stores it or why it is being stored.

Similaryly, re: 'variable trail to record the changes' is totally unclear about the relationship of the 'variable trail' to the obvious state history that MUST be maintained in order to recover state when backing up.

I've cleaned up what I could, but this article needs work. Sorry, if this sounds harsh. Just trying to be specific about the confusion here. LarryLACa 11:49, 12 December 2005 (UTC)

One solution or all of them?[edit]

This article is not clear about the goal of searching, but implicitly it seems that it assumes finding one solution to the search problem (without proving its uniqueness, even if it should be) suffices (or alternatively proving that none exist). This can be seen for instance in the pseudo-code. However, there are many cases where one wants to count the number of solutions, and this is when backtracking will be used inevitably, if only to show that a solution found is unique. Think of the n queens problem. I believe the term backtracking is also used for such problems, and think the wording should be adapted to allow for this case. Marc van Leeuwen (talk) 09:31, 27 May 2008 (UTC)

dependency-directed backtracking[edit]

Is dependency-directed backtracking (see Stallman, Richard M (1977). "Forward Reasoning and Dependency-Directed Backtracking In a System for Computer-Aided Circuit analysis". Artificial Intelligence 9. pp. 135–196.  Unknown parameter |coauthors= ignored (|author= suggested) (help)) worth mentioning in this article and redirecting here? -- Beland (talk) 17:49, 17 August 2008 (UTC)

Someone is also asking if this is the same as backjumping on that article's talk page. -- Beland (talk) 17:51, 17 August 2008 (UTC)

possible new technique : turbobacktracking[edit]

an algo that might "capture" the "profile" of the part of bactracking type solution might count more than one solution at a time... — Preceding unsigned comment added by (talk) 17:59, 24 July 2011 (UTC)

to fight against software processing stall, any backtracking or turbobacktracking might use smart tests both on forward and backtrack (talk) 08:24, 11 November 2012 (UTC)

Knuth and Cormen References[edit]

Although both the Knuth and Cormen references are classic books in the field of algorithms, neither deal with backtracking. On Knuth's page about The Art of Computer Programming ( Backtracking is set to be talked about in Volume 4, which has not yet been released. In Cormen et al. there is no index reference to backtracking. — Preceding unsigned comment added by Sness (talkcontribs) 04:25, 7 April 2014 (UTC)

"most efficient"?[edit]

(if not the most efficient[citation needed]) has been there since 2011. Isn't it time this should be removed? — Preceding unsigned comment added by (talk) 01:25, 13 April 2014 (UTC)

confusing and unnecessary distinction[edit]

I suggest a modification on your algorithm with four reasons:

1. I am afraid You make an unnecessary distinction between the first child and the others. Father creates the first and elder brother makes the next. The knowledge in reject(), accept() and first() is inherited from different creators. It is confusing.

2. Your interface of nodes makes possible to rewind the iteration of children. Backtrack definitely don't want that.

3. Your code can be shorter. Your interface of node can be simpler.

4. The domain of your backtrack search is restricted to tree but it could be a directed graph.

Please, check this out:

 procedure bt(c) 
   if reject(P,c) then return 
   if accept(P,c) then output(P,c) 
   while s ← next(P,c), s ≠ Λ do 

Csaba Kelemen (talk) 13:32, 28 June 2015 (UTC)


Your algorithm is very clear. And I think constraints should appear in your algorithm. In many case, you need adapting your data at different level, this is where backtracking happened. So need add 'changeData/restoreData' to keep track or backtrack.

procedure bt(c)

 if reject(P,c) then return
 if accept(P,c) then output(P,c)
 // change some data struct for next level
 s ← first(P,c)
 while s ≠ Λ do
   s ← next(P,s)
 // restore data struct for sibling
 restoreData(P,c)  — Preceding unsigned comment added by Moan1223 (talkcontribs) 13:35, 30 August 2016 (UTC) 

give the categories of the problem in backtracking — Preceding unsigned comment added by (talk) 15:07, 27 November 2016 (UTC)