Unique solutions on 5x5 grid, 16 blank cells

For fans of Kakuro

Unique solutions on 5x5 grid, 16 blank cells

Postby Mathimagics » Thu Oct 22, 2015 5:38 am

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

KT0505_NB16.jpg
N = 5, 16 white cells
KT0505_NB16.jpg (9.93 KiB) Viewed 298 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   1238
2489   2498   2816   2816   3156   7459   2415   2415
3156   3156   4759   4928   5479   8126   3957   6859
9578   8579   5978   5789   7598   9578   5869   8927


1245   1245   1268   1268   1268   1356   1356   1356
2879   2897   2351   2489   3152   2135   2135   2135
3157   3128   4597   3152   5497   4289   4298   4579
5698   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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

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

Postby Mathimagics » Thu Oct 22, 2015 6:46 am

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

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

Postby dobrichev » Fri Oct 23, 2015 4:05 am

Hi Mathimagics,
Take a look on this thread.
dobrichev
2016 Supporter
 
Posts: 1315
Joined: 24 May 2010

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

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

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


Return to Kakuro