Kakuro - Uniqueness of Solutions

For fans of Kakuro

Min hints/max blanks for Grid sizes > 10

Postby Mathimagics » Wed Oct 14, 2015 1:55 pm

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! 8-)

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


KT14a_NH21.jpg
N=14, NH=21, normal symmetry
KT14a_NH21.jpg (44.07 KiB) Viewed 236 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Case 13b has Unique solutions

Postby Mathimagics » Thu Oct 15, 2015 7:17 am

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 ...

KP13b_NH36.jpg
Unique solution grid on 13x3, dual symmetry, NH =36
KP13b_NH36.jpg (64.27 KiB) Viewed 231 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Case 15b has Unique solutions

Postby Mathimagics » Fri Oct 16, 2015 6:30 pm

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
KP15b_NH44_US.jpg (112.61 KiB) Viewed 221 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Review of Grid sizes vs Validity

Postby Mathimagics » Sat Oct 17, 2015 5:01 am

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kakuro - Critical blocks

Postby Mathimagics » Sun Oct 18, 2015 2:57 am

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Minimum hints for N=12

Postby Mathimagics » Mon Oct 19, 2015 7:16 am

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
KP1212_NH14.jpg
N=12, NH= 14, NB=107, unique soln
KP1212_NH14.jpg (63.53 KiB) Viewed 208 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Minimum NH for N=12?

Postby Mathimagics » Mon Oct 19, 2015 8:34 am

Oops! Silly me ... :roll:

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

But does it support unique solutions? We shall find out ...
Attachments
KT1212_NH13.jpg
N=12, NH=13, valid template
KT1212_NH13.jpg (34.43 KiB) Viewed 207 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

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

Postby Mathimagics » Wed Oct 21, 2015 1:06 pm

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
KP12a_NH13.jpg
N=12, NH=13, unique solution
KP12a_NH13.jpg (63.24 KiB) Viewed 200 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Kakuro - Uniqueness of Solutions

Postby Mathimagics » Wed Oct 21, 2015 5:22 pm

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kakuro - Critical blocks

Postby Mathimagics » Fri Oct 23, 2015 4:17 am

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
KP0607_NB28_US.jpg (20.86 KiB) Viewed 189 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)
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

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

Postby Mathimagics » Sun Oct 25, 2015 8:50 pm

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

KP1313_NH16_US.jpg
N=13, NB=128, NH=16, Unique solution
KP1313_NH16_US.jpg (70.3 KiB) Viewed 184 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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

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

Postby Mathimagics » Tue Oct 27, 2015 1:56 am

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.

KP1414_NH21_US.jpg
N=14, NH=21, NB=148, unique solution
KP1414_NH21_US.jpg (68.67 KiB) Viewed 176 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

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

Postby Mathimagics » Tue Oct 27, 2015 3:39 am

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.

KP1515_NH24_US.jpg
N=15, NH=24, NB=172, unique solution
KP1515_NH24_US.jpg (77.67 KiB) Viewed 176 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

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

Postby Mathimagics » Tue Oct 27, 2015 6:25 am

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

KP1616_NH29_US.jpg
N=16, NH=29, NB=196, unique solution
KP1616_NH29_US.jpg (85.98 KiB) Viewed 175 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kakuro - Uniqueness of Solutions

Postby Mathimagics » Tue Oct 27, 2015 6:30 am

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Previous

Return to Kakuro