The New Sudoku Players' Forum

[Mathimagics]

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 1683 times

N=14, NH=21, normal symmetry

KT14a_NH21.jpg (44.07 KiB) Viewed 1683 times

[Mathimagics]

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 1678 times

[Mathimagics]

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 1668 times

[Mathimagics]

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]

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]

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.

[Mathimagics]

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

[Mathimagics]

Phew, that took some work to track down, but we have a unique solution on a 12x12 grid with just 13 interior hint cells:

[Mathimagics]

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]

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 1636 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]

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 1631 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]

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 1623 times

[Mathimagics]

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 1623 times

[Mathimagics]

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 1622 times

[Mathimagics]

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.