## Unique solutions on 5x5 grid, 16 blank cells

For fans of Kakuro

### Unique solutions on 5x5 grid, 16 blank cells

I've been wondering for some time just how many Kakuro puzzles with unique solutions (US) can be created on this grid:

N = 5, 16 white cells
KT0505_NB16.jpg (9.93 KiB) Viewed 563 times

It seems to be a relatively simple question, but answering it is not so straight-forward.

One could test all possible settings for the white cells, to see which give rise to US's. Unfortunately there are almost 3 trillion possibilities!

If you wonder how I came up with this number, you'll find the rationale over on this thread.

If we reduce the search to those 4x4 matrix settings that are in reduced form (RF), ie have values in ascending order in row 1 and column 1, we are still left with 20 billion cases to test (19,686,788,064 to be precise).

So I came up with a heuristic method, which uses a Markov chain/perturbation model, very similar to the Pittenger method of random Latin Square generation. By applying a sequence of perturbations to a US grid I can find lots more US cases on the same grid, I just need one to start with. (Finding US's on blank grids is doable, but very much harder!).

At each perturbation I change one or more cell values, keeping the grid valid, then recompute the sums and test the new puzzle for uniqueness, keeping only those changes that are successful. This process then tends to produce solutions very different to the original in a reasonable time.

With a fast solver, for most normal puzzles (on typical grids you'd find anywhere), this process usually leads to at least 5000 variations on the original puzzle in just a few minutes. But in extreme cases, of which this is one, it eventually stops finding new ones after a while, ie. it tends to converge to a smaller set.

But the results for this particular case lead me to believe that there are just 16 distinct RF cases that correspond to US's:

Code: Select all
`1235   1235   1235   1235   1235   1235   1238   12382489   2498   2816   2816   3156   7459   2415   24153156   3156   4759   4928   5479   8126   3957   68599578   8579   5978   5789   7598   9578   5869   89271245   1245   1268   1268   1268   1356   1356   13562879   2897   2351   2489   3152   2135   2135   21353157   3128   4597   3152   5497   4289   4298   45795698   5689   5789   8597   7589   5978   5879   5798`

Now it's possible that my perturbation model has some flaw, and might not lead to every possible solution, but I think that's highly unlikely. Nevertheless, if anyone's aware of some combination I have missed I'd be very pleased to know about it.
Last edited by Mathimagics on Thu Mar 09, 2017 6:44 am, edited 2 times in total.

Mathimagics
2017 Supporter

Posts: 1275
Joined: 27 May 2015
Location: Canberra

### Re: Unique solutions on 5x5 grid, 16 blank cells

I forgot to explain why I couldn't work from the other side of the fence, so to speak, and consider testing word-sums instead.

For the 5x5 grid in question, each of the 4 horizontal and vertical sums can be anywhere from 10 to 30, so they can take any of 21 values.

21 to the 8th power is 37,822,859,361. Urrgh!

Mathimagics
2017 Supporter

Posts: 1275
Joined: 27 May 2015
Location: Canberra

### Re: Unique solutions on 5x5 grid, 16 blank cells

Hi Mathimagics,
Take a look on this thread.
dobrichev
2016 Supporter

Posts: 1707
Joined: 24 May 2010

### Re: Unique solutions on 5x5 grid, 16 blank cells

Thanks, and that's all very interesting, but ...

... I can't see the direct relevance to Kakuro, not immediately anyway.

Word squares can have the same letter appearing more than once in a row/col.

Am I missing something?

Mathimagics
2017 Supporter

Posts: 1275
Joined: 27 May 2015
Location: Canberra