backtracking.asc

Backtracking

Backtracking algorithms are used to find all (or some) solutions that satisfy a constraint.

Backtracking builds a solution step by step, using recursion. If during the process it realizes a given path is not going to lead to a solution, it stops and steps back (backtracks) to try another alternative.

Some examples that use backtracking is solving Sudoku/crosswords puzzle and graph operations.

Listing all possible solutions might sound like brute force. However, it is not the same. Backtracking algorithms are faster because it tests if a path will lead to a solution or not.

Brute Force vs. Backtracking Algorithms

Brute force evaluates every possibility. Backtracking is an optimized brute force. It stops evaluating a path as soon as some of the conditions are broken. However, it can only be applied if a quick test can be run to tell if a candidate will contribute to a correct solution.

How to develop backtracking algorithms?

Backtracking algorithms can be tricky to get right or reason about, but we will follow this recipe to make it easier.

Steps to create backtracking algorithms

1. Iterate through the given input

2. Make a change

3. Recursively move to the next element.

4. Test if the current change is a possible solution

5. Revert the change (backtracking) and try with the next item

Let’s do an exercise to explain better how backtracking works.

Permutations

> Return all the permutations (without repetitions) of a word.

For instace, if you are given the word art these are the possible permutations:

[ [ 'art' ],
  [ 'atr' ],
  [ 'rat' ],
  [ 'rta' ],
  [ 'tra' ],
  [ 'tar' ] ]

Now, let’s implement the program to generate all permutations of a word.

Note	We already solved this problem using an iterative program, now let’s do it using backtracking.

Word permutations using backtracking

link:../../../src/algorithms/permutations-backtracking.js[role=include]

1. Iterate through all the elements

2. Make a change: swap letters

3. Recursive function moving to the next element

4. Test if the current change is a solution: reached the end of the string.

5. Revert the change (backtracking): Undo swap from step 2

As you can see, we iterate through each element and swap with the following letters until we reach the end of the string. Then, we roll back the change and try another path.

In the following tree, you can visualize how the backtracking algorithm is swapping the letters. We are taking art as an example.

digraph g {
  node [shape = record,height=.1];

  art[label = "<f0> A*|<f1> R|<f2> T"];
  art1[label = "<f0> A|<f1> R*|<f2> T"];
  art2[label = "<f0> A|<f1> R|<f2> T", color="red"];
  atr[label = "<f0> A|<f1> T|<f2> R", color="red"];
  rat[label = "<f0> R|<f1> A*|<f2> T"];
  rat1[label = "<f0> R|<f1> A|<f2> T", color="red"];
  rta[label = "<f0> R|<f1> T|<f2> A", color="red"];
  tra[label = "<f0> T|<f1> R*|<f2> A"];
  tra1[label = "<f0> T|<f1> R|<f2> A", color="red"];
  tar[label = "<f0> T|<f1> A|<f2> R", color="red"];

  art:f0 -> art1:f0 [ label = "1. swap A/A"];
  art1:f0 -> art2:f0 [ label = "2. swap R/R"];
  art2:f2 -> art1:f1 [ label = "3.", color="grey", fontcolor="grey"];
  art1:f2 -> atr:f0 [ label = "4. swap R/T"];
  atr:f2 -> art1:f2  [ label = "5.", color="grey", fontcolor="grey"];
  art1:f1 -> art:f0  [ label = "6.", color="grey", fontcolor="grey"];

  art:f1 -> rat:f0 [ label = "7. swap A/R"];
  rat:f0 -> rat1:f0 [ label = "8. swap A/A"];
  rat1:f2 -> rat:f1 [ label = "9.", color="grey", fontcolor="grey"];
  rat:f2 -> rta:f0 [ label = "10. swap A/T"];
  rta:f2 -> rat:f2 [ label = "11.", color="grey", fontcolor="grey"];
  rat:f2 -> art:f2 [ label = "12.", color="grey", fontcolor="grey"];

  art:f2 -> tra:f0 [ label = "13. swap A/T"];
  tra:f0 -> tra1:f0 [ label = "14. swap R/R"];
  tra1:f2 -> tra:f2 [ label = "15.", color="grey", fontcolor="grey"];
  tra:f2 -> tar:f0 [ label = "16. swap R/A"];
  tar:f2 -> tra:f2 [ label = "17.", color="grey", fontcolor="grey"];
  tra:f2 -> art:f2 [ label = "18.", color="grey", fontcolor="grey"];
}

Legend:

• The asterisk (*) indicates start index.

• Black arrows indicate the swap operations.

• Grey arrows indicate the backtracking operation (undo swap).

• The red words are the iterations added to the solution array.

Most of the backtracking algorithms do something similar. What changes is the test function or base case to determine if a current iteration is a solution or not.