Control structures for backtracking search

KBK (25 April 2002) - The fact that Tcl allows new control structures to be defined at the script level by means of uplevel and upvar has led to its being a popular platform for prototyping search algorithms that require backtracking. The general idea is that you can program a proc that makes a nondeterministic choice, and evaluates a script to follow through on the consequences of that choice.

The Wiki offers one toy example, used for Solving cryptarithms like

    S E N D
  + M O R E
 -----------
  M O N E Y

RS examines some of the possibilities in Playing Prolog and Playing predicate logic. Searching a star in space is also interesting, as is Neil Madden's State Space Searching in Tcl.

Joseph Konstan and his grad students (notably Alex Safonov and Sunanda Iyengar) did a tremendous amount of related work in the early days of Tcl. Much of their system was based on imaginative uses of the trace command rather than on a nondeterministic-choice procedure. Their first paper is abstracted at [1], but alas, the full text there appears to be damaged. See TclProp.

Dayton Clark and David Arnow implemented code that is a more direct inspiration for Solving cryptarithms. In their paper, [2], they introduce a more general Tcl-based framework for constraint management and backtracking. The code accompanying their paper has been uploaded to the Half Bakery. See [3].