.

Phase 1, which aims to eliminate as many candidate grids as cheaply as possible, is now complete. You can appreciate the size of the problem computationally by the fact this "express" culling process still took 4 processes 3.5 days to complete.

But we have eliminated 77% of the grids from consideration as 10-clue candidates, as this table shows:

- Code: Select all
`Phase 1:`

mc = 0: 4

mc = 2: 3

mc = 3: 19

mc = 4: 198

mc = 5: 2118

mc = 6: 15961

mc = 7: 128612

mc = 8: 691034 1%

mc = 9: 2928539 5%

mc = 10: 8032026 14%

mc = 11: 14101485 26%

mc = 12+: 27766690 51%

------------------

53666689

The minimum clue count (mc) is the lower-bound obtained by finding cliques (sets of disjoint UA's), this search doesn't find all cliques, so in most cases the actual minimum clue number is higher, and the actual minimum clue count required to hit every UA is higher still.

I have produce a 2nd version of the clique finder that is more aggressive, and while slower than the method used in Phase 1, is still much quicker than enumerating the Hitting Sets, so I am running that as Phase 2, on the candidates not eliminated in Phase 1. This process should eliminate another 10% from 10-clue consideration.

That should take a few days as well.

I also looked at the cases where the UA process didn't identify anything useful. I looked at the 26 cases with mc < 4. These correspond to very low numbers of UA sets. In most cases I am able to improve the UA count by selecting the best candidate from the 10368 PF-equivalent forms. This will make the Hitting Set algorithm (Phase 3) more effective, although it has little impact on the clique-based MC values we get for the Phase 1/2 calculations.

But how about this? All test cases have isotopes with more UA's available, with the notable exception of the 4 cases where we found no UA's at all (mc = 0). These 4 have NO isotope with any usable UA's. That's a little bit mind-blowing.

I list them here. One thing I have noticed is that all four have distinct values along both diagonals. Is this significant?

[

† EDIT] It has come to my attention that I have been overlooking something blindingly obvious!

(See my post further down for details)

- Code: Select all
`123 | 456 | 789 123 | 456 | 789 123 | 456 | 789 123 | 456 | 789`

456 | 897 | 231 456 | 897 | 312 564 | 897 | 231 564 | 897 | 231

978 | 312 | 456 978 | 231 | 456 978 | 312 | 645 978 | 312 | 645

--------------- --------------- --------------- ---------------

564 | 978 | 312 564 | 978 | 231 645 | 978 | 312 647 | 938 | 512

789 | 123 | 564 789 | 123 | 564 789 | 123 | 456 389 | 125 | 476

231 | 564 | 897 312 | 564 | 897 231 | 564 | 897 251 | 764 | 893

--------------- --------------- --------------- ---------------

897 | 231 | 645 897 | 312 | 645 897 | 231 | 564 895 | 271 | 364

312 | 645 | 978 231 | 645 | 978 312 | 645 | 978 712 | 643 | 958

645 | 789 | 123 645 | 789 | 123 456 | 789 | 123 436 | 589 | 127