I have established that the puzzle as presented actually has at least
5 redundant clues. The current state of play is:
- Code: Select all
. . 66 . . . . . x7
8x . . . . . . 12 .
. . . . . . . . 88
78 . . . . . . . .
. . . . . . . . .
. . . 63 . . . . 51
. . . . . . . 79 .
. 49 . . . 7x . x8 .
. . . . 35 . 27 . 6x
The remaining candidate list for possible removal is
- Code: Select all
12: try 1x
88: try 8x
51: try x1
79: try x9
49: try 4x or x9
27: try 2x
All other clues have been certified as fixed (non-removable).
The BIG problem I have is the unexpectedly long time it is taking to test individual clue removals (or perhaps not unexpectedly?).
At 30 clues (the original), I knew this case might be a tad unusual because it was the slowest to reduce in the dozen or so samples I tried. It took a DLX solver 240s to prove uniqueness of solution.
The DLX model (virtual) has a notional 6561 rows x 648 columns. It's pretty straight-forward - one value (1...81) per cell + every cell diffrent (1...81) + two sub-problems A and B, (unique A values in row, col and block), ditto for B.
For these clue sets the actual row count is between 2232 (30 clues) and 2573 (25 clues).
No worries, then, we'll crank up MiniSAT, giving it the same exact cover problem model. Unfortunately that took 20 minutes to emulate the DLX solver for 30 clues.
I then removed the half clues indicated above at (1,9) and (2,1), to give a (still unique-soln) 28-clue set. DLX took 25 minutes, MiniSAT took 3h 15m.
For obvious reasons I didn't run any more with MiniSAT - reports of it scaling better than DLX might be true for standard Sudoku, but we have a significantly different model here .
I simply guessed the clue "most likely" to prove removable and sat back patiently.
I got lucky 3 times in a row, DLX solved the 27 and 26 clue cases in 33m and 65m although it had a real conniption when I removed another clue to give 25. Just as well that turned out to be removable, because it took DLX 6.5 hours ... for confirmation.
Do I hear 24? For a "certificate of minimality" we still have to test those clues.
Sadly we have eliminated too many clues from the individual Sudokus for simple enumeration of one list (iteration cost is tiny, but there are potentially billions of solns to check) to be effective. I'm running out of ideas ... (and I have the flu: these conditions may be linked