Kakuro - Uniqueness of Solutions

For fans of Kakuro

Kakuro - Uniqueness of Solutions

Postby Mathimagics » Fri Oct 02, 2015 6:47 am

I've been experimenting with Kakuro uniqueness, and have come up with an interesting example. The question is, for a grid of given size, what is the maximum number of blank cells (cells in which digits are to be placed) for which a unique solution is possible?
Last edited by Mathimagics on Sat Oct 03, 2015 5:57 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kakuro - Uniqueness of Solutions

Postby Mathimagics » Fri Oct 02, 2015 7:03 am

Assuming for the moment a square grid, of size N < 10, then the number of blank cells NB is at most (N-1)^2, so for an 8x8 grid, we have NB <= 49.
Last edited by Mathimagics on Sat Oct 03, 2015 6:15 am, edited 2 times in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kakuro - Maximum Number of Blank Cells

Postby Mathimagics » Fri Oct 02, 2015 1:15 pm

The greatest value for NB that I have discovered for an 8x8 grid with a unique solution is 43.

KT0808_T006.jpg
43 blank cells, unique solution
KT0808_T006.jpg (58.26 KiB) Viewed 329 times


The best result I have for 44 blank cells is shown below, it has 2 solutions, with a 2x2 cycle as indicated:

KT0808_T008.jpg
44 Blank cells, 2 solutions
KT0808_T008.jpg (57.32 KiB) Viewed 329 times
Last edited by Mathimagics on Sat Oct 03, 2015 6:18 am, edited 3 times in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kakuro Uniqueness - Acyclic Cycle?

Postby Mathimagics » Fri Oct 02, 2015 7:20 pm

Here's another curious case, which I came across when trying to find max NB for N = 9.

It's fairly obvious that any symbol cycles (permutations) that occur in a solution will mean multiple solutions, assuming that the pairs of symbols occur in the same digit runs.

But here's another possibility, one that is unique to Kakuro, where the number of different possible symbols can exceed the length of the run. Here's an example:

Kakuro_SPC.jpg
N = 9, NB = 56, 2 solutions
Kakuro_SPC.jpg (41.04 KiB) Viewed 330 times


This puzzle has exactly two solutions, which are obtained by swapping the values each of the two rows indicated. They are interchangeable because:
  • the vertical sums match (both are 11)
  • the swap values are free, ie they don't occur in either of the vertical runs

It's like a 2 symbol cycle but without the matching pairs ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kakuro - Uniqueness of Solutions

Postby Mathimagics » Sat Oct 03, 2015 6:35 am

By perturbing the solution grid above, I was able to find a unique solution example, so my best result for N = 9 is NB = 56.

KT0909_T005.jpg
N = 9, NB = 56, unique solution
KT0909_T005.jpg (73.47 KiB) Viewed 328 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kakuro - Uniqueness of Solutions

Postby Mathimagics » Sun Oct 04, 2015 12:45 am

After much experimenting, I have established what are in all likelihood the maximum value of NB for square grid sizes up to N = 10:

Code: Select all
Maximum blank cells with unique solution
---------------------------------------
      N:    5    6    7    8    9    10
---------------------------------------
 availB:   16   25   36   49   64    81
 max NB:   14   22   32   43   56    70
 min NH:    2    3    4    6    8    11


The values "min NH" are the corresponding minimum number of hint cells (other than the ones in row 1 and col 1), so NB + NH add up to "availB", the size of the available area, ie (N-1)^2.

If anyone is interested ( :? ), I can describe the methods I used to derive these figures.

(Note: new values for max NB have been obtained in most cases, see updated table below)
Last edited by Mathimagics on Mon Oct 05, 2015 7:29 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Kakuro - Uniqueness of Solutions

Postby Smythe Dakota » Sun Oct 04, 2015 9:18 am

I think your nomenclature is non-standard.

To me, the topmost all-black "row" doesn't count, and the leftmost all-black "column" doesn't either. So what you call 8x8, most of us would call 7x7.

But, adopting your nomenclature for the moment, to keep the discussion consistent within this thread --

Are there ways can we reduce the obvious (n-1)^2 maximum? That calculation is nothing more than the total number of white-cell candidates.

Here a few initial observations:

There cannot be two adjacent rows, each of which has no black cells (other than the "forced" black cell in the leftmost column). If there were, you could simply interchange the contents of those two rows, cell by cell, and thus produce a second solution.

More generally, there cannot be two "words" (runs) in adjacent rows, one directly beneath the other, which have the same length and which start in the same column. I once came across a website claiming to have valid kakuro puzzles, but which had two six-digit horizontal words in the upper right corner. Right away I knew that that website was a fake.

Still more generally, there cannot be two words, even in non-adjacent rows, which have the same length and start in the same column, and in which each cell in one word is rook-connected to the corresponding cell in the other.

Bill Smythe
Smythe Dakota
 
Posts: 525
Joined: 11 February 2006

Re: Kakuro - Uniqueness of Solutions

Postby Mathimagics » Sun Oct 04, 2015 12:19 pm

Hi Bill!

Firstly, I apologise for non-standard terminology - I have a mathematical/computational perspective, from which viewpoints the most convenient definition of the grid includes all cells, so a square grid is of size N x N, in which rows and columns are numbered from 0, so the effective area in which digits can appear is (N-1)^2.

Smythe Dakota wrote:There cannot be two adjacent rows, each of which has no black cells (other than the "forced" black cell in the leftmost column). If there were, you could simply interchange the contents of those two rows, cell by cell, and thus produce a second solution.


Consider the example above ("N=9, NB = 56, Unique solution"). The bottom two rows have no interior black cells, yet this solution is the only one that matches the given hints, or "word sums". It's true that swapping the rows makes no difference to the sums, either horizontal or vertical, but you have to take into account the entire grid, whose sums in this case are enough to force the values in these two rows to be just what they are!

Smythe Dakota wrote:More generally, there cannot be two "words" (runs) in adjacent rows, one directly beneath the other, which have the same length and which start in the same column.

Again, this is not true, and for the same reason.

Smythe Dakota wrote:Still more generally, there cannot be two words, even in non-adjacent rows, which have the same length and start in the same column, and in which each cell in one word is rook-connected to the corresponding cell in the other.

I think that all your observations are essentially correct, but only if the "words" in question have the same combination of symbols (what I would call a cycle). If two 6-digit words appear together in a 2x6 pattern, that's only a problem if both of them contained a permutation of the same values, eg {1,2,3,4,5,6}.

In the example I mentioned above, the two 8-digit "words" have different symbol sets, one is {1,2,3,4,5,7,8,9} and the other is {1,2,3,4,6,7,8,9}.

Cycles certainly are an indicator of non-uniqueness of solution, and your observation on rook-connectivity of the pairwise symbols is suely relevant, but only if the digits match.

In fact there can be even more exotic cases of cycles, e.g. 2 matching digits spread over 3 or 4 rows/cols, or even some more complicated than that!

That's why the "Acyclic cycle" example I show above is of particular interest. The 4 symbols are all different, yet they are still interchangeable!

The consequence of cycles is this: say that I were to generate a grid with a given set of values, then produce the corresponding puzzle by adding up the sums, and the feed those sums (hints) into a solver (man or machine).

If there were any cycles in the original grid, I would certainly find that the puzzle had more than one solution.

Cheers
Jim White
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Kakuro - Uniqueness of Solutions

Postby Smythe Dakota » Sun Oct 04, 2015 7:39 pm

Oops, you're right. :oops: To "having the same length and starting in the same column", I need to add another condition, "and having the same digits" (albeit in a different order, of course). The latter condition is automatic only if both words are the maximum length, such as 9 when the symbol set is {1,2,3,4,5,6,7,8,9}.

Bill Smythe
Smythe Dakota
 
Posts: 525
Joined: 11 February 2006

New maximum NB values

Postby Mathimagics » Mon Oct 05, 2015 7:29 am

OK, I've now improved on most of the the max NB/min NH values given above, and extended the table to include N = 11.

The trend suggests that the results for N = 9, 10, 11 may not be final.

Code: Select all
Maximum blank cells with unique solution
--------------------------------------------
      N:    5    6    7    8    9   10   11
--------------------------------------------
 availB:   16   25   36   49   64   81  100
 max NB:   15   24   34   46   56?  71?  87? 
 min NH:    1    1    2    3    8   10   13 


Examples for N=5, 6
KT0505_min.jpg
N = 5, NB = 15
KT0505_min.jpg (15.61 KiB) Viewed 306 times

KT0606_min.jpg
N = 6, NB = 24
KT0606_min.jpg (22.83 KiB) Viewed 306 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kakuro - minimum hints for Unique solution

Postby Mathimagics » Fri Oct 09, 2015 5:50 pm

I've got new max NB/min NH values for N = 9 and N = 10:

Code: Select all
Maximum blank cells with unique solution
--------------------------------------------
      N:    5    6    7    8    9   10   11
--------------------------------------------
 availB:   16   25   36   49   64   81  100
 max NB:   15   24   34   46   59   72   87
 min NH:    1    1    2    3    5    9   13 
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Min hints/max blanks for Uniqueness of Solution

Postby Mathimagics » Tue Oct 13, 2015 6:26 am

I've got new max NB/min NH values for N = 10 and N = 11:

Code: Select all
Maximum blank cells with unique solution

      N:    5    6    7    8    9   10   11
--------------------------------------------
 availB:   16   25   36   49   64   81  100
 max NB:   15   24   34   46   59   74   88*
 min NH:    1    1    2    3    5    7   12 


I think the max/min for N = 11 of 88 blanks/12 internal hints is absolute and provably so.

The 10x10 available area needs to have a hint in every row and column, since we can't have runs (words) of length > 9.

However, we also don't allow single-cell runs (words), which means that no hint cell can appear in row 2, row 9, col 2 or col 9 unless there is also a hint in the adjacent row/col (ie. in row/col 1 or 10).

It therefore takes at least 8 hint cells to fix these problematic rows and cols (as can be seen in the attachment below). This gives a total row/col coverage of 6, leaving 4 rows and 4 cols to be fixed. But we need at least 4 more hint cells to achieve this. QED

KP1111_MaxNB_US.jpg
N = 11, NB = 88, NH = 12, Unique solution
KP1111_MaxNB_US.jpg (62.39 KiB) Viewed 276 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Min hints/max blanks for Grid sizes > 10

Postby Mathimagics » Wed Oct 14, 2015 12:45 pm

For the case above, we have the happy coincidence that for the case N = 11, a puzzle with a unique solution can be created on a grid of 88 blanks + 12 internal hints, and we can't create a grid with any more blanks.

Before looking for max blanks/min hints (that allow unique solution puzzles) to be formed on larger grids, the question that first needs to be asked is just what is the maximum number of blanks possible in a grid of size > 10?

For reasons which will (hopefully) become obvious, I'll address the question of in terms of the minimum number of internal hints, NH. The following table shows what I think are correct results for N = 11 to 18. I've listed the even and odd N separately, as the trend is more evident:

Code: Select all
Min hints (NH) for valid grid

a) Normal symmetry
b) Dual   symmetry

    N:   11   13   15   17   |  12   14   16   18
-------------------------------------------------
a) NH:   12*  16   22   28   |  17   21   25   29
b) NH:   28   36   44   52   |  24   28   32   36


By normal symmetry I mean the symmetry evident in most puzzles, which is where the pattern in the top row appears in reverse order in the bottom, and so on. Dual symmetry is where the rows and columns are all symmetric.

I will post images corresponding to the 8 cases listed above shortly. Notice that the differences between adjacent entries in each of the 4 sets is the same (6|4) for type a, and (8|4) for type b.

The entry marked with a * represents the only exception to this trend. When reducing the pattern used for N=17 to its equivalent in case 15 and 13, for case 11 it was impossible to fit into the available space, so 2 extra hints needed to be used.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Min hints/max blanks for Grid sizes > 10

Postby Mathimagics » Wed Oct 14, 2015 12:53 pm

Images attached for N = 11, 13 type (a) grids.

KT11a_NH12.jpg
N=11, NH=12, minimum hints, normal symmetry
KT11a_NH12.jpg (33.24 KiB) Viewed 266 times


KT13a_NH16.jpg
N=13, NH=16, minimum hints, normal symmetry
KT13a_NH16.jpg (40.33 KiB) Viewed 266 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Min hints/max blanks for Grid sizes > 10

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

Images for N = 15, 17 type (a).

KT15a_NH22.jpg
N=15, NH=22, minimum hints, normal symmetry
KT15a_NH22.jpg (46.76 KiB) Viewed 266 times


You'll notice that both of these cases seem unlikely to produce a well-formed puzzle (ie. with a unique solution). But these patterns can in fact be scrambled so as to keep the same number of blanks but more likely to yield a solution. I just wanted to illustrate the basic patterns I started with.

KT17a_NH28.jpg
N=17, NH=28, minimum hints, normal symmetry
KT17a_NH28.jpg (53.5 KiB) Viewed 266 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Next

Return to Kakuro