- N = 5, 16 white cells
- KT0505_NB16.jpg (9.93 KiB) Viewed 1636 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.
