set of assignments provides a solution. These search trees are obviously exponential, and in the worstcase scenario every node may have to constructed. However, large-scale pruning of the search tree can occur by judicious use of consistency methods. The idea is to do a small amount of extra work that (hopefully) identifies variable-value assignments that are already logically ruled out by the current choice of assignment, meaning that those branches of the search tree need not be explored. While there are no guarantees that this extra work is anything other than an overhead, in practice enough search is pruned to give efficient solutions for otherwise intractable problems. Taking a specific example from the empirical evaluation reported later in this paper, an all closest string problem for a fixed distance involving strings of length 25 with a 4-symbol alphabet will require at most 425 ≈ 1.1 × 1015 nodes to be searched. An efficient solver will search only 3 or 4 ×109 nodes, with the remainder being ruled out by efficient propagation of the logical results of the assignments during search. Moreover, an efficient solver will search around 300,000 of the remaining nodes per CPU second. It is this efficient reduction in search space that allows CSP practitioners to solve otherwise intractable problems.

Heuristics exist for choices of variable-value pair for the next node, and as before these may have no effect on the number of nodes visited. Again, in general, variable and value orderings designed for specific problem classes can lead to several orders of magnitude reduction in the number of nodes needed to find a solution. Standard choices for variable orderings include random, smallest domain, largest domain, most-constrained (i.e. chooses avariable that appears in a maximal number of constraints),
least-constrained, etc. Results will vary with the problem class and model under consideration. Taking another specific example from experiments in this paper involving closest string problems, enforcing singleton singleton arc consistency - a limited depth procedure that aims to prune entire branches near the root, see [1] for a full analysis - at the root node of a search tree can be a huge loss. It can take three times longer to reach the first closest string at a given distance than it takes to find all closest strings.

In summary, the solution performance for instances of a class of CSPs will depend crucially on choices of model, consistency, search order and the solver used. Moreover, empirical evaluation is often the only way to decide which of these choices is better for a given set of circumstances.

## 1.2.1 The Minion Csp **Solver**

The constraint solver Minion [10] uses the memory architecture of modern computers to speed up the backtrack process compared to other solvers. Minion has an extensive set of constraints, together with efficient propagators that enforce consistency levels very rapidly. Minion has been used to solve open problems in combinatoric algebra [5], finding billions of solutions in a search space of size 10100 in a matter of hours. Minion is used as the solver for this investigation as it offers both fast and scalable constraint solving, which are important factors when solving closest string problems. Moreover, the user can easily specify bespoke variable orderings, and less easily specify value orderings.

## 1.3 Formal Definitions And Results

Before proceeding to the technical Sections, we first formalise Hamming Distances and Diameters, and closest strings:
Definition. Let S1 and S2 be strings of length L over an alphabet Σ. Let D be the binary string of length L such that

D(i) = 1 S1(i) 6= S2(i)
$$D(i)=\left\{\begin{array}{l l}{{1}}&{{S1(i)\neq S2}}\\ {{0}}&{{o t h e r w i s e i}}\end{array}\right.$$
The Hamming Distance hd(S1,S2) is defined as the sum from i = 1 *to L of the D*(i).