SourGumdropK Kakuro: Solving techniques 4

Possible permutations PP

If all of a strip's permitted permutations place the same digit in the same cell, it must be the solution for the cell, and all other candidates in the cell can be removed. A permitted permutation is one which contains no duplications of digits and which sums to the correct total.

Candidates
[6,7]
[7,9]
[1,3]
[1,2]

Perms    sum
[6,7,1,1]
[6,7,1,2] 16
[6,7,3,1] 17
[6,7,3,2] 18*
[6,9,1,1]
[6,9,1,2] 18*
[6,9,3,1] 19
[6,9,3,2] 20
[7,7,1,1]
[7,7,1,2]
[7,7,3,1]
[7,7,3,2]
[7,9,1,1]
[7,9,1,2] 19
[7,9,3,1] 20
[7,9,3,2] 21

Figure 1. In the example we ignore the solved cell and so have a column of 4 cells and a sum of 26 - 8 = 18. Although they are shown, the possible combinations are not relevant to the method: all that matters are the remaining candidates. The possible permutations of the remaining candidates and their sums are shown below. If a permutation contains duplicate digits it is not allowed and so no sum is shown.

Notice that only two legal permutations [6,7,3,2] and [6,9,1,2] have the required sum of 18. The crucial factor is that both have digit 6 in the first position and digit 2 in the last position and so we can set these digits as the solutions for the corresponding cells by removing all other candidates in those cells.

Obviously it is only when there are very few remaining candidates for a strip that working out their possible permutations becomes tractable for a human solver. The program could do it at all states of the grid, but any hints found would not be easily validated by a player, so this algorithm is only applied when the proportion of remaining candidates in a strip is less than 3 per cell.

Candidate bounds CB

The candidates in a cell have upper and lower values ("bounds") determined by the strip sum and the possible candidates in the other cells.

Consider a row of 2 cells with sum 3. Being Kakuro wizards we immediately know the solution is [1,2] but ignore that and here think of it in terms of "candidate bounds". The maximum value in the first cell will occur when the second cell takes its minimum value of 1, and must be 3 - 1 = 2. The minimum value of a cell is the row sum minus the maximum value: i.e. 3 - 2 = 1. This enables all candidates other than 1 and 2 to be deleted from all cells in the row.

The same arguments hold true however many cells there are in the row. However, it can be a little more complicated to work out the mininum and maximum candidate combinations.

The maximum value for any cell in a row is the row sum minus the minimum total that can be made from the remaining candidates in the other cells in the row.

Figure 2. The minimum total that can be made from the three rightmost cells in the figure is 1 + 7 + 8 = 16. If this is the minimum for the rest of the row, the leftmost cell cannot have a value greater than 19 - 16 = 3. So candidates 4,5,6,7,8,9 can be removed.

The minimum value for any cell in a row is the row sum minus the maximum total that can be made from the remaining candidates in the other cells in the row.

Figure 3. The maximum total that can be made from the two rightmost cells in the figure is 4 + 9 = 13. If this is the maximum for the rest of the row, the leftmost cell cannot have a value less than 19 - 2 - 13 = 4. So candidates 1,2,3 can be removed.

Isolated necks IN

A "neck" is a cell made special by a particular type of grid layout. This form of layout sometimes makes it possible to solve the cell at the neck by simply adding and subtracting the sums across and down. Please see the figure.

Figure 4. A neck with solution 7. Because the block of cells to the left of the neck are completely isolated from the rest of the grid, the solution for the neck cell is the sum of the sums across minus the sum of the sums down: 19+28+4+3-(21+19+4+3)=7.

Last updated: 2012-10-28 Sitemap