Constraint Satisfaction by Branch & Sample: anImplementation in C

The Branch & Sample algorithm (B&S) offers a search strategy potentially applicable to constraint satisfaction problems (CSPs) whose variables are interdependent in terms of the constraints to be satisfied. CSPs are often combinatorially explosive (have very large numbers of solutions), and the basic idea of the algorithm is to overcome this by generating a relatively small sample of solutions which are in a certain sense representative of the entire solution space, and scattered over it. (B&S can also handle CSPs with no solutions, or just a suitable number which can be exhaustively generated.) This Web publication presents B&S from the point of view of practical programming. The algorithm is incrementally developed from a simple sketch to full application independent source code in C, available free of charge on gentlemanly conditions. Concerns of user-machine interaction are introduced as part of the algorithm development, and practical advice on how to incorporate B&S into an application program is offered by way of example. For the benefit of non-C programmers, the essentials of C notation is briefly explained.