tarek wrote:With ways to reduce the weak links and SAT, I have no doubt that a minimal 81x81 is doable possibly with ease.
Perhaps only with terabytes of RAM and a super cluster!
The following log reveals some unfortunate, and sobering, facts. We are solving with MiniSAT, just like blue
, but with none of his pre-processing tricks (only the obvious singles checking):
- Code: Select all
12:34:09 Loaded Reduced\Sudoku81-999.txt (3983 givens, 72 are non-removable)
12:34:12 Begin reduction (cumulative)
12:34:12 cell (12,56) is removable, nrem = 1
12:34:13 cell (28,3) is removable, nrem = 2
12:34:13 cell (53,53) is removable, nrem = 3
12:34:14 cell (48,28) is removable, nrem = 4
12:34:15 cell (64,21) is removable, nrem = 5
12:34:16 cell (9,76) is removable, nrem = 6
12:34:16 cell (60,17) is removable, nrem = 7
12:34:17 cell (57,22) is removable, nrem = 8
12:34:18 cell (37,10) is removable, nrem = 9
12:34:48 cell (31,60) is removable, nrem = 10
12:35:26 cell (27,24) is removable, nrem = 11
12:37:07 cell (37,47) is removable, nrem = 12
12:42:17 cell (42,16) is removable, nrem = 13
12:56:51 cell (1,53) is removable, nrem = 14
13:10:38 cell (13,61) is removable, nrem = 15
13:21:51 cell (32,60) is
13:21:51 [ERROR] solver result = -2
I began with a valid grid I pinched from here
Then I checked every one of the 3983 givens to see whether they were removable (individually). Running 5 jobs checking 16 rows each took only 30 minutes. I began to get quietly excited ...
Only 72 of them were non-removable, so I set up phase 2. In this phase I select a removable given at random, then another, applying them cumulatively. The log above shows the progress.
Everything runs smoothly until the 10th removal, when all of a sudden the time to test jumps from 1-2 seconds to 30s, then 38s, then 101s, then 310s, then 874s, 827s ...
Worse still was the failure at step 16, when it got an "out of memory" exception. So all that effort and all I got was a 3868-given version.
I will run a similar test on 36x36 to see if the same behaviour is being exhibited (the effective time doubling) ... judging from blue's comments above, I think it will get further, but hit the same wall.