Backtrack programming is such a powerful technique for problem solving that a number of languages, especially in the area of artificial intelligence, have built-in facilities for backtrack programming. CBack is a simple, but general tool for backtrack programming in the programming language C.

In addition to the usual depth-first search strategy, CBack provides for the more general heuristic best-first search strategy. The source code, shown in its full length, is entirely written in ANSI C and highly portable across diverse computer architectures and C compilers.

CBack has been described in the paper

K. Helsgaun,
"CBack: A Simple Tool for Backtrack Programming in C",
Softw. pract. exp., Vol. 25, No. 8, 1995 (pp. 905-934).

The kernel of CBack is the two functions Choice and Backtrack.

Choice is used when a choice is to be made among a number of alternatives. Choice(N), where N is a positive integer denoting the number of alternatives, returns successive integer.

A call of Backtrack causes the program to backtrack, that is to say, return to the most recent call of Choice which has not yet returned all its values. The state of the program is reestablished exactly as it was when Choice was called, and the next untried value is returned.

CBack was primarily designed for backtrack programming in C. However, it may also be used with programming languages that allows calls to external C functions.

Installation

CBack has been implemented in the programming language C. The is entirely written in ANSI C and portable across a number of computer platforms and C compilers.

The code can be downloaded in two formats

1. CBack-1.0.tgz (gzipped tar file, approximately 100 KB)
2. CBack-1.0.sit (Stuffit archive, approximately 100 KB )

If a UNIX machine is used, download the software in the first format. Next execute the following UNIX commands:

gzip -d CBack-1.0.tgz
tar xvf CBack-1.0.tar

If a MacOS or a Windows machine is used, download the software in the second format. Next unstuff it with Stuffit Expander™ (freeware available at http://www.aladdinsys.com).

The code is distributed for research use. The author reserves all rights to the code.