Is there a name for the do -> recurse -> undo pattern in backtracking?

user_7006570 0
Viewed 81

In backtracking, i.e. the algorithm used for solving the n-queens problem, there are basically two ways to do the recursive call:

  1. copy the parent board to make a child board, modify the child board by placing a new queen, then do the recursive call on the child board.
  2. modify the board directly, do the recursive call, then undo the modification.

The second is preferred since it avoids the costly copy.

This choice is also present in other algorithms, like minimax on games.

Is there a name for pattern 2 as opposed to pattern 1?

tree-search backtracking search algorithm naming
3 Answers

In Constraint Programming and SAT-Solving (where your n-queens example usually comes from) i would argue, that these concepts are described as:

  • copy-based
  • trail(ing)-based

See for example:

Reischuk, Raphael M., et al. "Maintaining state in propagation solvers." International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, Heidelberg, 2009.

Schulte, Christian. "Comparing Trailing and Copying for Constraint Programming." ICLP. Vol. 99. 1999.

Excerpt of the former:

Constraint propagation solvers interleave propagation, removing impossible values from variable domains, with search. The solver state is modified during propagation. But search requires the solver to return to a previous state. Hence a propagation solver must determine how to maintain state during propagation and forward and backward search. [...] This paper also provides the first realistic comparison of trailing versus copying for state restoration.

Both have their pros and cons, analyzed in the references.

Keep in mind, that the trail is usually not only about storing your decisions (board placements), but also propagations happened (this placement leads to these now impossible placements due to alldifferent propagation: these effects must be reverted as well!). For an overview of the implementation of such, see: MiniCP

user_23200350

I would say that the two are the same algorithm, only with a mutable or immutable board.

I would also say that for the specific case of n-queens, the copy isn't expensive at all, since you can represent a board using only 64 bits... you probably spend a lot more than that per level of the call stack :)

user_1529480

A related subject to this matter is a design pattern in object-oriented programming, which is called "command-pattern". It helps to undo recent commands depending on a command stack.

user_37688710
Related