21. Kakuro¶
This chapter studies Kakuro puzzles, a variant of the well-known Sudoku puzzles. Two models are presented: a first and obvious model that suffers from too little propagation to be feasible. This is followed by a model that employs user-defined constraints implemented as extensional constraints using tuple set specifications. Interestingly, the tuple set specifications are computed by solving a simple constraint problem.
21.1. Problem¶
Figure 21.1 A Kakuro puzzle¶
Solving a Kakuro puzzle (see Figure 21.1 for an example) amounts to finding digits between 1 and 9 for the non-hint fields on a board. A hint field can specify a vertical hint and/or a horizontal hint:
A vertical hint contains a number \(s\) above the diagonal in the hint field. It requires that all digits on the fields extending from the field left of the hint up to the next hint field or to the end of the row are pairwise distinct and sum up to the value \(s\).
A horizontal hint contains a number \(s\) below the diagonal in the hint field. The requirements are analogous.
The number contained in a hint is called its value and the number of fields constrained by a hint is called its length.
Figure 21.2 Solution for Kakuro puzzle from Figure 21.1¶
The solution for the Kakuro puzzle from Figure 21.1 is shown in Figure 21.2 . Kakuro puzzles are always designed (at least meant to be) to have a unique solution.
21.2. A naive model¶
...
// [kakuro naive:board specification]
class Kakuro : public Script {
protected:
const int w, h;
IntVarArray f;
public:
// [kakuro naive:init function]
// [kakuro naive:posting hint constraints]
Kakuro(const Options& opt)
: Script(opt), w(board[0]), h(board[1]), f(*this,w*h) {
// [kakuro naive:field initialization]
// [kakuro naive:setup]
// [kakuro naive:process vertical hints]
...
// [kakuro naive:branching]
}
...
};
...
Download: kakuro-naive.cpp
const int board[] = {
// Dimension w x h
12, 10,
// Vertical hints
3, 0, 3, 7, 4, 0, 6,21, 7, 0, 4,29, 8, 0, 2,17,
...
-1,
// Horizontal hints
2, 1, 2, 4, 6, 1, 2,17, 9, 1, 2,16, 1, 2, 3, 6,
...
};
A script for the Kakuro model is shown in A naive script and board specification for solving Kakuro puzzles . The script stores the width (w) and height (h) of the board. The fields are stored in an integer variable array f which is initialized to have \(\mathtt{w}\cdot\mathtt{h}\) elements. Note that none of the fields is initialized in the constructor of Kakuro; their initialization is discussed below.
21.2.1. Board specification.¶
The specification of the Kakuro board, as shown in A naive script and board specification for solving Kakuro puzzles , stores width and height of the board, followed by a specification of the hints. The hints are provided in two groups: first vertical hints, then horizontal hints, separated by the integer -1. A hint is described by its coordinates on the board, followed by its length and value. Note that the specification assumes that the field with coordinate \(\langle 0,0\rangle\) is in the left upper corner.
21.2.2. Initializing fields.¶
All fields are initialized to a single shared integer variable black that is assigned to zero:
IntVar black(*this,0,0);
for (int i=0; i<w*h; i++)
f[i] = black;
Only if a field is actually used by a hint, the field will be initialized to an integer variable taking digit values by the following init() function:
IntVar init(IntVar& x) {
if (x.min() == 0)
x = IntVar(*this,1,9);
return x;
}
The test whether the minimum of variable x equals zero is true, if and only if x still refers to the variable black. In this case, a new variable is created with non-zero digits as variable domain. As x is passed by reference, assigning x to the newly created variable also assigns the corresponding field on the board to the newly created variable. This guarantees that a new variable is created at most once for each field.
21.2.3. Posting hint constraints.¶
Posting hint constraints is done best by using a matrix interface b (see Matrix interface for arrays ) to the fields in f. The specification of the hints will be accessed by the variable k, where the dimension of the board has already been skipped:
Matrix<IntVarArray> b(f,w,h);
const int* k = &board[2];
Processing the vertical hints is straightforward. After retrieving the coordinates x and y, the length n, and the value s for a hint from the board specification, the variables covered by the hint are collected in the integer variable argument array (see Argument arrays ) col. The constraint for the hint on the collected variables is posted by the member function hint():
while (*k >= 0) {
int x=*k++; int y=*k++; int n=*k++; int s=*k++;
IntVarArgs col(n);
for (int i=0; i<n; i++)
col[i]=init(b(x,y+i+1));
hint(col,s);
}
The hint() function must constrain that all variables are distinct (using a distinct constraint) and that they sum up to the value of the hint (using a linear constraint). To achieve strong propagation, we want to use domain propagation for both distinct and linear. However, the complexity of domain propagation for linear is exponential, hence it is a good idea to avoid posting linear constraints as much a possible.
Consider a hint of length \(9\). Then obviously, the single possible value of the hint is \(\sum_{i=1}^{9} i=9(9+1)/2\) and hence no linear constraint needs to be posted. Now consider a hint of length \(8\) with value \(s\). Then, the fields covered by the hint take on all but one digit. That is, all fields must be different from \(\sum_{i=1}^9 i -s = 9(9+1)/2 -s\). Taking these two observations into account, the constraints for a hint can be posted as follows, where the value IPL_DOM requests domain propagation (see Selecting the propagation level ):
void hint(const IntVarArgs& x, int s) {
if (x.size() < 8)
linear(*this, x, IRT_EQ, s, IPL_DOM);
else if (x.size() == 8)
rel(*this, x, IRT_NQ, 9*(9+1)/2 - s);
distinct(*this, x, IPL_DOM);
}
Note that there are other special cases where no linear constraint needs to be posted, for example if for a hint of length \(n\) and value \(s\) it holds that \(\sum_{i=1}^n i=s\) (that is, only digits from \(1\) to \(n\) are possible). See More information for more information.
Vertical hints are of course analogous and are hence omitted.
21.2.4. Branching.¶
We choose a branching that selects the variable where the quotient of AFC and domain size is largest smallest (see Branching on integer and Boolean variables ). Values are tried by interval bisection:
branch(*this, f, INT_VAR_AFC_SIZE_MAX(), INT_VAL_SPLIT_MIN());
21.2.5. Why the model is poor.¶
Figure 21.3 Propagation for the Kakuro puzzle¶
When running the script, solving even the tiny board of Figure 21.1 requires \(19\) search nodes. There exist commercially available boards with thousands of hints, which are of course completely out of reach with the naive model. Figure 21.3 shows the possible digits for each field after performing propagation for the Kakuro script but before any search. Consider the two green fields for the hint of length \(2\) and value \(4\). The only possible combination for the two fields is \(\langle 3,1\rangle\). However, propagation does not prune the value \(2\) for both fields. The reason is that a hint constraint is decomposed into a distinct constraint and into a linear constraint and neither constraint by itself warrants more pruning than shown.
21.3. A working model¶
The naive model from the previous section suffers from the fact that hint constraints are decomposed into a distinct constraint and a linear constraint. One remedy would be to implement a dedicated propagator for a distinctlinear constraint. This is impractical: too complicated and too much effort for such a specialized constraint.
21.3.1. Model idea.¶
This section implements distinctlinear constraints as extensional constraints using tuple sets as specification of the possible solutions of distinctlinear constraints. For example, for a hint of length \(3\) and value \(8\), the possible solutions for the corresponding distinctlinear constraint are:
The model needs a method to compute all solutions of a distinctlinear constraint. To simplify matters, we are going to compute all solutions of a distinctlinear constraint by computing all solutions of a trivial constraint problem: the decomposition of a distinctlinear constraint into a distinct and linear constraint.
...
class DistinctLinear : public Space {
protected:
IntVarArray x;
public:
// [kakuro:distinct linear script]
// [kakuro:returning a solution]
...
};
void distinctlinear(Home home, const IntVarArgs& x, int c) {
// [kakuro:set up search engine]
// [kakuro:compute tuple set]
// [kakuro:post extensional constraint]
}
class Kakuro : public Script {
...
// [kakuro:posting hint constraints]
...
};
...
Download: kakuro.cpp
A working script for solving Kakuro puzzles shows the outline for a working script for solving Kakuro puzzles. The class DistinctLinear defines the script used for computing all solutions of a distinctlinear constraint and the function distinctlinear() serves as constraint post function. Apart from how hint constraints are posted, the Kakuro script is the same as in the previous section.
21.3.2. Computing distinct linear solutions.¶
As mentioned, the script for DistinctLinear just posts a linear and distinct constraint for n variables and value s. As the search space of the problem is small anyway, we neither need strong propagation for distinct and linear nor do we need a clever branching:
DistinctLinear(int n, int s) : x(*this,n,1,9) {
distinct(*this, x);
linear(*this, x, IRT_EQ, s);
branch(*this, x, INT_VAR_NONE(), INT_VAL_SPLIT_MIN());
}
When solving the DistinctLinear script, we need its solutions as integer argument arrays for computing a tuple set. The solution() member function of DistinctLinear returns an integer argument array for a solution as follows:
IntArgs solution(void) const {
IntArgs s(x.size());
for (int i=0; i<x.size(); i++)
s[i]=x[i].val();
return s;
}
21.3.3. Posting distinctlinear constraints.¶
The search engine (see Search engines ) for computing all solutions of a DistinctLinear script is initialized as follows:
DistinctLinear* e = new DistinctLinear(x.size(),c);
DFS<DistinctLinear> d(e);
delete e;
Computing a tuple set (see Extensional constraints ) for all solutions of a distinctlinear constraints is straightforward:
TupleSet ts(x.size());
while (DistinctLinear* s = d.next()) {
ts.add(s->solution()); delete s;
}
ts.finalize();
Note that after all solutions have been added to the tuple set ts, it must be finalized before it can be used by an extensional constraint (see Extensional constraints ).
Finally, posting the extensional constraint using the tuple set ts is as to be expected:
extensional(home, x, ts);
21.3.4. Posting hint constraints.¶
Posting a hint constraint follows a similar line of reasoning as in the previous section. If the length of a hint is \(0\), no constraint needs to be posted (hints of length \(0\) are black fields without hints). If the length is \(1\), the single variable is constrained to s directly. For lengths \(8\) and \(9\), distinct is used as it achieves the same propagation as distinctlinear. Note that the case for length \(8\) continues (as it does not have a break statement) with the case for length \(9\) and hence also posts a distinct constraint. In all other cases, distinctlinear is used:
void hint(const IntVarArgs& x, int s) {
switch (x.size()) {
case 0:
break;
case 1:
rel(*this, x[0], IRT_EQ, s); break;
case 8:
rel(*this, x, IRT_NQ, 9*(9+1)/2 - s);
case 9:
distinct(*this, x, IPL_DOM); break;
default:
distinctlinear(*this, x, s); break;
}
}
There is a further important optimization which we will not show (but see More information ). Each time distinctlinear is called, it computes a new tuple set, even though the tuple set is exactly the same for all hints of equal length and value. To guarantee that the same tuple set is computed at most once, one could cache tuple sets: if a tuple set for a certain length and value has already been computed earlier, it is not computed again but taken from a cache (where it had been stored when it was computed for the first time).
21.3.5. This model works.¶
For the example puzzle, propagation alone is sufficient to solve the puzzle. Even puzzles with thousands of hints are solved without search in a fraction of a second (including computing the tuple sets, provided they are cached as sketched above).
21.4. More information¶
Kakuro puzzles with some more examples are available as a Gecode example, see kakuro . In particular, the model caches tuple sets such that for each type of hint its corresponding tuple set is computed at most once as discussed in A working model . Furthermore, the example exploits further special cases where posting a distinct constraint rather than a complete hint constraint is sufficient as discussed in A naive model .
More constraint-based techniques for solving Kakuro puzzles are discussed in [58] .