## Kakuro - Uniqueness of Solutions

For fans of Kakuro

### Min hints/max blanks for Grid sizes > 10

Images for N = 12 and 14, type (a).

I will stop at this stage, if anyone wishes to see examples of the other cases, I'll post them on request!

N=12, NH=17, normal symmetry
KT12a_NH17.jpg (37.06 KiB) Viewed 786 times

N=14, NH=21, normal symmetry
KT14a_NH21.jpg (44.07 KiB) Viewed 786 times

Mathimagics
2017 Supporter

Posts: 1762
Joined: 27 May 2015
Location: Canberra

### Case 13b has Unique solutions

I have finally got my new Kakuro generator working, albeit in early alpha-release mode, but it has quickly found that well-formed puzzles exist on the 13x13 grid with dual symmetry and 36 interior hints.

That's hardly surprising, as 36/144 = 25%, which is a fairly high number, so the chances were always good.

So case 13b in the table is ticked off, it can support unique solutions with minimum hints for that type.

Sorry about the size, I can produce templates in smaller versions but not with clues yet! Font selection and positioning is a bit tricky ...

Unique solution grid on 13x3, dual symmetry, NH =36
KP13b_NH36.jpg (64.27 KiB) Viewed 781 times

Mathimagics
2017 Supporter

Posts: 1762
Joined: 27 May 2015
Location: Canberra

### Case 15b has Unique solutions

After some problems dealing with the butterfly effect (cf: thread "Kakuro and the Butterfly Effect"), I have found that grid case 15b (N=15, dual symmetry, NB=152, NH=44) allows unique solutions:

KP15b_NH44_US.jpg (112.61 KiB) Viewed 771 times

Mathimagics
2017 Supporter

Posts: 1762
Joined: 27 May 2015
Location: Canberra

### Review of Grid sizes vs Validity

While I was discovering the solution noted above (15b), it occurred to me that there are are some intrinsic limits on grid templates, which limit the types that need be considered.

For example, a template with 2 runs of length 9 that are aligned and adjacent can never deliver a unique solution.

That's because swappping the row or column values must inevitably deliver the same sums.

Other limits seem to be less obvious, but my experiments, plus a canvas of various puzzles I could find to test, all seem to point to the following limits on what I call critical blocks, which are rectangles of contiguous blank cells:

• 2 x 8
• 3 x 7
• 4 x 6

Any block of blank cells that exceed these limits (such as 5 x 5) is almost certainly incapable of delivering a puzzle with a unique solution.

So I was lucky with the 15x15 case because the 5x5 corners (on which I was building my solution) have 2 hint cells, so pass this test.

Most of the other large sample grids I generated are clearly useless, and I will probably have to revise my table quite significantly.

Mathimagics
2017 Supporter

Posts: 1762
Joined: 27 May 2015
Location: Canberra

### Kakuro - Critical blocks

It's interesting that it's not just the number of cells in the critical block that determines U(G) (by which I mean the property of a grid G that it supports Unique solutions).

So while 25 cells (5 x 5) or more is definitely a no-no, 24 cells is ok if in a 4x6 rectangle, but not 3x8.

What the sizes 2x9, 3x8, 4x7, and 5x5 have in common is that they are guaranteed to contain a cycle of some sort, thus guaranteeing ambiguity in the corresponding solution space of any grid G containing them.

Mathimagics
2017 Supporter

Posts: 1762
Joined: 27 May 2015
Location: Canberra

### Minimum hints for N=12

I have found a unique solution can be formed on grid size N = 12, with NH = 14. This represents an absolute minimum for NH, as no valid grids can be formed with less.
Attachments
N=12, NH= 14, NB=107, unique soln
KP1212_NH14.jpg (63.53 KiB) Viewed 758 times

Mathimagics
2017 Supporter

Posts: 1762
Joined: 27 May 2015
Location: Canberra

### Minimum NH for N=12?

Oops! Silly me ...

Minimum NH for size 12 is in fact 13, as this grid demonstrates!

But does it support unique solutions? We shall find out ...
Attachments
N=12, NH=13, valid template
KT1212_NH13.jpg (34.43 KiB) Viewed 757 times

Mathimagics
2017 Supporter

Posts: 1762
Joined: 27 May 2015
Location: Canberra

### Min NH = 13, grid size N=12: confirmed!

Phew, that took some work to track down, but we have a unique solution on a 12x12 grid with just 13 interior hint cells:
Attachments
N=12, NH=13, unique solution
KP12a_NH13.jpg (63.24 KiB) Viewed 750 times

Mathimagics
2017 Supporter

Posts: 1762
Joined: 27 May 2015
Location: Canberra

### Re: Kakuro - Uniqueness of Solutions

Now here's a curious thing - in a discussion on isomorphisms over here, a question was asked as to whether it was possible to have a template with no clues, no givens, and yet have a unique solution (well, 2 unique solutions, owing to isomorphism obtained by value reflection, ie. mapping each soln value V to 10 - V).

The grid above comes very close to that, it's got the least variety of solutions that I've ever come across. There appear to be just 24 varieties (+24 reflections) of unique-solution cases.

5 4 2 . 6 4 9 8 7 3 5
3 2 1 . 4 5 7 6 2 1 3
8 6 3 2 . 3 8 7 4 2 1
9 8 5 4 7 2 6 3 1 . .
7 5 9 6 4 1 3 2 . 9 5
6 3 4 1 2 . 5 4 7 8 9
4 1 . 7 8 6 1 5 2 4 3
. . 6 8 9 5 2 1 4 3 7
6 7 8 9 5 1 . 9 5 6 8
9 4 5 3 1 2 8 . 1 5 2
7 8 9 5 3 4 6 . 3 7 6

The only variations are the 3 values in column 1, which can {5,3,4], {5,4,3}, {5,4,2}, {5,3,2}, {3,4,5} and {3,4,2}. The values in row 10 can be {9,7}, {9,8}, {8,7} or {8,9}. These options combine to give the 4x6 = 24 variations.

If you feed the implied sums corresponding to each case into a solver, you'll find they are unique-solution puzzles.

Mathimagics
2017 Supporter

Posts: 1762
Joined: 27 May 2015
Location: Canberra

### Kakuro - Critical blocks

Mathimagics wrote:Any block of blank cells that exceed these limits (such as 5 x 5) is almost certainly incapable of delivering a puzzle with a unique solution.

Well, you learn something new every day ... (hopefully!)

Here's a grid with a 5x5 blank cell block, but it's got a unique solution:

KP0607_NB28_US.jpg (20.86 KiB) Viewed 739 times

And here is a summary of what I know so far about these blocks. These block sizes have either US's on their own, or can appear in a bigger grid which has a US. The latter are marked with an "x".

• 2 x 2
• 2 x 3
• 2 x 4
• 2 x 5
• 2 x 6
• 2 x 7
• 2 x 8
• 3 x 3
• 3 x 4
• 3 x 5
• 3 x 6 (x)
• 3 x 7 (x)
• 4 x 4
• 4 x 5 (x)
• 4 x 6 (x)
• 5 x 5 (x)

Mathimagics
2017 Supporter

Posts: 1762
Joined: 27 May 2015
Location: Canberra

### Grid size N = 13, NH = 16, NB = 128

I've found a unique solution on a 13x13 grid with just 16 interior hints.

N=13, NB=128, NH=16, Unique solution
KP1313_NH16_US.jpg (70.3 KiB) Viewed 734 times

Since none of the interior hints can be removed and leave a valid grid, I believe this to be the maximum NB/minimum NH for this grid size.

Mathimagics
2017 Supporter

Posts: 1762
Joined: 27 May 2015
Location: Canberra

### Grid size N = 14, NH = 21, NB = 148

Here is a 14 x 14 grid, 21 internal hints, 148 blank cells, with a unique solution.

While a valid grid can be formed with NH = 19, by setting cells {r3, c4} and {r11, c10} to blank, I can't find a unique solution case on that grid.

N=14, NH=21, NB=148, unique solution
KP1414_NH21_US.jpg (68.67 KiB) Viewed 726 times

Mathimagics
2017 Supporter

Posts: 1762
Joined: 27 May 2015
Location: Canberra

### Grid size N = 15, NH = 24, NB = 172

Here is a 15 x 15 grid with 24 internal hints, 172 blank cells, unique solution.

My solver indicates this one is remarkably straight-forward, ie: definitely no trial-and-error involved.

N=15, NH=24, NB=172, unique solution
KP1515_NH24_US.jpg (77.67 KiB) Viewed 726 times

Mathimagics
2017 Supporter

Posts: 1762
Joined: 27 May 2015
Location: Canberra

### Grid size N = 16, NH = 29, NB = 196

And finally, a 16 x 16 grid with 29 interior hints, 196 blank cells.

N=16, NH=29, NB=196, unique solution
KP1616_NH29_US.jpg (85.98 KiB) Viewed 725 times

Mathimagics
2017 Supporter

Posts: 1762
Joined: 27 May 2015
Location: Canberra

### Kakuro - Uniqueness of Solutions

My min NH/max NB results table, updated:

Code: Select all
`Maximum blank cells with unique solution      N:    5    6    7    8    9   10   11   12   13   14   15   16-------------------------------------------------------------------- availB:   16   25   36   49   64   81  100  121  144  169  196  225 max NB:   15   24   34   46   59   74   88  108  128  148  172  196 min NH:    1    1    2    3    5    7   12   13   16   21   24   29 `

I was able to achieve standard symmetry, ie: hint(r, c) => hint(N - r, N - c), in all cases.

Mathimagics
2017 Supporter

Posts: 1762
Joined: 27 May 2015
Location: Canberra

Previous