The New Sudoku Players' Forum

[Mathimagics]

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?

[Mathimagics]

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.

[Mathimagics]

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

43 blank cells, unique solution

KT0808_T006.jpg (58.26 KiB) Viewed 2308 times

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

44 Blank cells, 2 solutions

KT0808_T008.jpg (57.32 KiB) Viewed 2308 times

[Mathimagics]

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:

N = 9, NB = 56, 2 solutions

Kakuro_SPC.jpg (41.04 KiB) Viewed 2309 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 ...

[Mathimagics]

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.

N = 9, NB = 56, unique solution

KT0909_T005.jpg (73.47 KiB) Viewed 2307 times

[Mathimagics]

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)

[Smythe Dakota]

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

[Mathimagics]

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.

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!

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.

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

[Smythe Dakota]

Oops, you're right. 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

[Mathimagics]

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

N = 5, NB = 15

KT0505_min.jpg (15.61 KiB) Viewed 2285 times

N = 6, NB = 24

KT0606_min.jpg (22.83 KiB) Viewed 2285 times

[Mathimagics]

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 


[Mathimagics]

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

N = 11, NB = 88, NH = 12, Unique solution

KP1111_MaxNB_US.jpg (62.39 KiB) Viewed 2255 times

[Mathimagics]

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.

[Mathimagics]

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

N=11, NH=12, minimum hints, normal symmetry

KT11a_NH12.jpg (33.24 KiB) Viewed 2245 times

N=13, NH=16, minimum hints, normal symmetry

KT13a_NH16.jpg (40.33 KiB) Viewed 2245 times

[Mathimagics]

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

N=15, NH=22, minimum hints, normal symmetry

KT15a_NH22.jpg (46.76 KiB) Viewed 2245 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.

N=17, NH=28, minimum hints, normal symmetry

KT17a_NH28.jpg (53.5 KiB) Viewed 2245 times