Backtracking

Backtracking works on the principle of depth first search

The term reset procedure or backtracking describes a problem-solving method within algorithms .

General algorithm

Backtracking is based on the trial and error principle , which means that an attempt is made to develop a partial solution into an overall solution. If it is foreseeable that a partial solution cannot lead to a final solution, the last step or the last steps are taken back and alternative approaches are tried instead. This ensures that all possible solutions can be tried out (principle of the Ariadne thread ). With backtracking algorithms, an existing solution is either found (possibly after a very long runtime), or it can be definitely stated that no solution exists. Backtracking is usually the easiest to implement recursively and is a prototypical use case of recursion.

Funktion FindeLösung (Stufe, Vektor)
  1. wiederhole, solange es noch neue Teil-Lösungsschritte gibt:
     a) wähle einen neuen Teil-Lösungsschritt;
     b) falls Wahl gültig ist:
               I) erweitere Vektor um Wahl;
              II) falls Vektor vollständig ist, return true; // Lösung gefunden!
                  sonst:
                       falls (FindeLösung(Stufe+1, Vektor)) return true; // Lösung!
                       sonst mache Wahl rückgängig; // Sackgasse (Backtracking)!
  2. Da es keinen neuen Teil-Lösungsschritt gibt: return false // Keine Lösung!

Time complexity

In the case of depth-first search , nodes are expanded from each partial solution and a solution tree with a maximum depth of, in the worst case, nodes if the maximum possible branches are possible . ${\displaystyle z}$ ${\displaystyle N}$ ${\displaystyle 1+z+z^{2}+z^{3}+\dotsb +z^{N}}$

The depth-first search and thus also backtracking have an exponential run time in the worst case with and one degree of branching . The greater the search depth , the longer it will take to find a solution. Therefore, backtracking is primarily suitable for problems with a small solution tree. ${\displaystyle O(z^{N})}$ ${\displaystyle z>1}$ ${\displaystyle n}$

However, there are methods with which the time complexity of a backtracking algorithm can be reduced. These are among others:

• Heuristics
• Acceptance of approximate solutions and fault tolerance
• Average input amount

Examples

Known problems that can be solved with backtracking include:

Ladies problem

Solving the women's problem with the help of backtracking

There is a chessboard with fields (each column and row). Now position women so that they cannot hit each other. The ladies problem belongs to the class of constraint satisfaction problems . ${\displaystyle n\times n}$ ${\displaystyle n}$ ${\displaystyle N}$

Jumper problem

Given is a chessboard with squares. A jumper can make various jumps from a certain position if these do not lead over the edge of the board. We are looking for a path in which all fields are visited exactly once (Springerweg). With the help of backtracking, all possible paths can be systematically tried out. A move is valid if the new field is within the playing field and is not yet visited. However, there are far more efficient methods of solving this problem. ${\displaystyle m\times n}$ ${\displaystyle N=8}$

Backpack problem

A backpack with the capacity is given . Furthermore, objects are given values and weights. Objects should now be selected that add up to a maximum value, but whose total weight does not exceed the carrying capacity of the backpack. ${\displaystyle B}$ ${\displaystyle N}$

Staining problem

A map is given with countries which should be colored with different colors. We are looking for a color combination in which all countries that have a common border are colored differently. ${\displaystyle B}$ ${\displaystyle N}$

Solitaire board game

At the beginning there are 32 stones (pens or balls) on a board; one of these is removed in 31 moves by jumping over it with another stone.

Sudoku

The numbers from 1 to 9 should be entered in a field (divided into nine fields) according to certain rules . ${\displaystyle 9\times 9}$ ${\displaystyle 3\times 3}$

Str8ts

The numbers from 1 to 9 should be entered in a field according to certain rules . This type of puzzle can also be solved well with backtracking. ${\displaystyle 9\times 9}$

Search from A to B in a graph

Backtracking is also used to search for a route from A to B in a graph, for example to find connections in a timetable or to determine a route in a route planner or a route through a maze .

Many of these problems are NP-complete .

prolog

The Prolog programming language uses backtracking to generate responses. The interpreter tries out all possible proofs one after the other. Decision points are referred to as choice points . The so-called cut operator !can be used to discard choice points.

literature

• Robert Sedgewick : Algorithms. 2nd Edition. Addison-Wesley, Munich 2002, ISBN 3-8273-7032-9 .
• Niklaus Wirth : Algorithms and Data Structures. 3rd, revised edition. Teubner, Stuttgart 1983, ISBN 3-519-02250-8 .

Web links

Commons : Backtracking  - collection of images, videos and audio files

• c't article about backtracking programming with MiniMax and Alpha-Beta-Cut using the example of the game Othello / Reversi
• Interactive course on backtracking from the Math Prism project at the University of Wuppertal