Kaquadro the taximan
Every partition is unique
| (2) | 3=1+2 |
| 4=1+3 | |
| 5=2+3 | |
| (3) | 6=1+2+3 |
Kaquadro has the same rules as Kakuro except that the only digits allowed are 1, 2 and 3. Since the second rule allows no repeats, this means that no clue can be longer than 3. The only possible clues are given in the table at the right. Since all partitions are unique, the Kaquadro puzzles must be easier to solve than Kakuro. Every puzzle is at best a quick combinatorial problem.
In what follows, a puzzle will be called proper if it allows one and only one solution. All others will be called improper puzzles. We will now find all possible templates, ie, geometric arrangements of the white cells, and count the number of proper Kaquadro puzzles allowed for each template. One fact that will be crucial in the counting is that when A and B are each chosen from the set {3,4,5} and A≠B, then there is an unique number that belongs to the partition of both A and B. This number we call A∩B. For example: . The other two values can be read off from the table.
The simplest template: M=3
The simplest template is shown here along with the standard scheme for naming rows (by capital letters), columns (by lower case letters) and cells (by both). This is one of the two templates which can be placed inside a 3×3 grid. There are three white cells: Bb, Bc, Cb with clues X=[Bb]+[Bc] and Y=[Bb]+[Cb]. There are only three possibilities for X and Y, so there are at most 9 possible puzzles. The geometrical symmetry group (called G) of the white cells is that of a square with one corner fixed. Since this is just a reflection in the dotted diagonal line, we write . The reflection operation on the puzzle interchanges the clues X and Y.
| [Bc] | X | [Bb] | Y |
| 1 | 3 | 2 | 3 |
| 5 | |||
| 4 | 3 | 4 | |
| 5 | |||
| 2 | 3 | 1 | 3 |
| 4 | |||
| 5 | 3 | 4 | |
| 5 | |||
| 3 | 4 | 1 | 3 |
| 4 | |||
| 5 | 2 | 3 | |
| 5 |
First try the enumeration. Clearly, one must allow three values for [Bc], leading to values of X, Y and [Bb] given in the table here. [Cb] is not listed because it is uniquely determined from the remaining data. Any combination of X and Y which appears more than once in the table is not a valid puzzle, since it has multiple solutions. As a result, we see that all valid puzzles on this template are labelled by the clues (X,Y) where X≠Y. There are six possible values: (3,5), (3,4), (4,3), (4,5), (5,3) and (5,4).
The key to the second argument is to realize that given a puzzle, the solution is unique if [Bb] is unique. But [Bb]=X∩Y, which is unique only if X≠Y. Since [Bc]≠[Cb], the symmetry group of the filled square (called γ) is trivial; we write γ={I}. The factor group G/γ=Z2. The six pairs (X,Y) with X≠Y∈{3,4,5} are connected pairwise under G/γ as (X,Y)↔(Y,X).
This is our first counting result. There are 6 Kaquadro puzzles in the smaller of the two templates that fit inside a 3×3 grid. Of these 3 are essentially different, ie, not carried into each other by the geometric symmetry group.
... and the next: M=4
The second template which fits into the 3×3 grid is shown here. This has a larger number of geometric symmetries (G): the four reflection symmetries of a square, namely the interchange of the two rows (B and C), two columns (b and c), reflections in the diagonals (Bc↔Cb and Bb↔Cc).
For uniqueness one must have . This gives three distinct digits [Bb], [Bc] and [Cb]. But then [Cc] must be equal to one of these. The Type 2 constraints prevent it from equalling [Bc] and [Cb], so one must have [Bb]=[Cc]. In that case W=Y and X=Z. Therefore one can label independent puzzles by the pair (W,X) where W≠X∈{3,4,5}.
The geometric symmetry group which keeps this pattern invariant (γ) is the reflection in the diagonal joining Bc and Cb, which is a group. Under the distinct generated by a row interchange, the equal values move to the squares Bc and Cd. This also interchanges W and X. This completes the analysis of this template. We have 6 distinct puzzles labelled by (W,X) W≠X∈{3,4,5}, which fall into 3 essentially different classes. The symmetries of the template connect every (W,X) with (X,W).
Mission Impossible: M=7,8,9
The first template which does not allow a Kaquadro puzzle is shown here. It has the barest minimum of decorations inside a 4×4 grid. The geometric symmetries are any permutation of the three rows and independently, any permutation of the three columns. The reason this is not a proper puzzle is simple: only 6 is allowed as a clue in each of the columns and rows. Once you find a solution, any permutation generates another solution.
One of the nine next simplest templates on a 4×4 grid is shown here. The others are generated by permuting rows and columns. None of these allow proper Kaquadro puzzles. Easy to prove that by contradiction. Assume you have a solution. The clues for rows B and C are 6, as are those for columns b and c. Now, permuting either of these rows (or columns) will give a different valid solution. Hence the solution cannot be unique. You can adapt this argument to rule out variants in which there are two columns with clue 6 or two rows with clue 6. This rules out many templates with 7 or 6 white cells.
... and possible: M=7
The template here allows the symmetries of reflection about the main diagonal joining Bb and Dd, and reflection in an orthogonal line through the central cell Cc. This defines the geometric group G. The template requires B=6 and E=6. Hence the impossibility proofs above fail. So we need to examine this further. An unique determination of [Bb]=C∩D requires C≠D∈{3,4,5}. Then, by the pigeonhole principle, one has [Cc]=[Bb]. Uptil now, the construction is exactly as in the case of M=4. Next, completion requires [Cd]=[Bc] and [Dc]=[Cb]. Again, the pigeonhole principle forces [Dd]=[Cc]. As a result, it is clear that A=D and C=F. Therefore each puzzle can be uniquely labelled by the ordered pair (A,F) where A≠F∈{3,4,5}. The symmetry of the completed puzzles γ=Z2 is generated by the second transformation listed at the beginning, so that G/γ=Z2, which is the reflection in the long diagonal. The puzzle (A,F) is carried to (F,A) under this. This is the third result. On this template there are 6 puzzles of which 3 are essentially different. Each essentially different puzzle is part of a doublet under the geometric symmetries of the template.
More possibilities: M=5,6
The template shown here has 6 white cells. The rows B and C can be interchanged, so G=Z2. One must have E=6. The 2×2 block is determined exactly as before by the ordered pair (C,D) where C≠D∈{3,4,5}. This yields B=D and [Cc]=[Bb]=C∩D. Now [Dc]=[Cb], and one has two possible values for A: either A=D or A≠D,C. There's no symmetry in the completed puzzle so γ={I} and G/γ=Z2. Each puzzle labelled by (A,C,D) is carried into one with C=D but B≠D under G/γ. Hence there are 24 puzzles in this template, with 12 essentially different, each doubled under symmetries.
The M=5 puzzle is obtained by converting the white cell Dd into a red cell. The construction essentially ends with completing the 2×2 block, since the cell Dc is completely fixed at that point. Hence the counting is the same as in the M=4 case.
Arbitrarily large puzzles
Can one make arbitrarily large Kaquadro puzzles? We approach this can be built by generalizing the procedure we used to extend the construction of the 2×2 block with M=4 to the M=7 case. The construction is shown alongside. Note that once the circled number is fixed by fixing the row and column clues which intersect at that cell, the construction of the block is a deterministic process. Hence the number of such blocks is always 6, and they always come in symmetry related pairs obtained by interchanging the initial row and column clues. This is sufficient to prove that one can make (very simple) Kaquadro puzzles of arbitrary size.
To start on the second step, we define the notion of a bridge connecting two self-contained blocks. A bridge is a linear chain of cells, such that every element is determined by the clues and the value of the cell at one end. A chain is shown here, along with the way it joins on to two self-contained blocks. Each joint is an extension of the case of M=6. The existence proof is completed by filling in a consistent solution and showing that it is unique. A consistent solution is shown in the figure. Uniqueness can be guaranteed by choosing clues to force the circled numbers. All other clues are then forced by the requirement of consistency. Note that an exchange of rows in the upper block does not spoil the puzzle. Nor does an exchange of columns in the lower block.
This puzzle can be further extended below the lower block in two ways: either by adding a bridge to the right of the circled 2 or below it. If the bridge is added below, then the exchange of columns in this block is barred. If it is added to the right, then this operation is not blocked. The rule is clear: every bridge removes the freedom of one permutation: of rows, if it extends a row, and of columns, if it extends a column.
Clearly, one can add larger self-contained blocks in place of each block that we have shown. This completes the proof that arbitrarily large Kaquadro puzzles are possible.
We also prove that all large Kaquadro puzzles are of this kind. This is easy to see. First note that no clue in Kaquadro can be more than 3 cells long. This means, of course, that the largest self-contained box cannot be more than three cells on each side. Having enumerated all the templates upto M=9 we have seen that the self contained blocks can only be of the form examined above. Thus, all Kaquadro puzzles are decomposable into self-contained blocks joined by bridges, as shown above.
Kaquadro is not in NP
The most complex Kaquadro block with M white cells will have some number N or 2×2 blocks and N-1 bridges of 2 white cells. Clearly then N=(M+2)/6. Since each block has one free variable, the integer programming part involves D=N variables. Each of these pieces is decoupled and can be solved in 1 step. Hence Kaquadro can be solved in time linear in the number of white cells, M. If the blocks are larger then D is smaller, but still linear in M. The variables are still decoupled and each block can still be solved in 1 step. The spreadsheet program shows that the memory requirement is also linear in M. Hence Kaquadro is in P and not in NP.
Note that the combinatorial bound on the complexity is, , so that if an exhaustive search were the only way to solve this problem, then Kaquadro would have to be in EXP. The rules serve to reduce the complexity enormously.
© Sourendu Gupta. Mail me if you want to reproduce any part of this page. My mailing address is a simple (satisfactory) puzzle for you to solve. Created on 30 November, 2006.