Pencilmark Sudoku

Programs which generate, solve, and analyze Sudoku puzzles

Re: Pencilmark Sudoku

Postby dobrichev » Sun Nov 08, 2020 1:19 pm

Very impressive result, Tom! Congratulations!

Now I believe 85's exist.
The problem is with these thousands of core-hours.

Do you have canonicalization procedure for pencilmark subgrid?
If no, IMO investing some effort there would reduce the times for vicinity search on the cost of huge files containing sorted subgrids that are already checked at {+n}.

Another idea is to generalize the unavoidable set concept to pencilmarks (i.e. representing a regular UA as a list of generalized UA, each corresponding to a particular permutation of givens). Then, with some luck, we may achieve full scan of a chosen solution grid using McGuire's method within reasonable core-hours. Both the whole search space, and, on the other hand, the sets requiring N constrains to be resolved (being composed of mutually disjoint generalized UA sets) grow enormously and I have no idea up to which degree they compensate each other. Also I don't know the reasonable minimum of constrains to start from, but for initial investigations it could be far less than 85.
dobrichev
2016 Supporter
 
Posts: 1845
Joined: 24 May 2010

Re: Pencilmark Sudoku

Postby 999_Springs » Mon Nov 09, 2020 3:07 am

dobrichev wrote:The posted hard puzzle is a record. It has backdoor of size 6 in singles + locked candidates. The hardest so far have BD 6 in singles (Tarek's hardest) but BD 4 in singles + locked. From my collection hardest are BD 4 in singles + locked too.

So that a brute force solver needs 6 lucky nested guesses, and much more if not so lucky.

this puzzle i created should be backdoor size 9 in singles and locked candidates and subsets as well

Code: Select all
123  12   123 |456  45   456 |789  78   789 
456  45   456 |789  78   789 |123  12   123 
789  78   789 |123  12   123 |456  45   456 
--------------+--------------+-------------
12   23   13  |45   56   46  |78   89   79  
45   56   46  |78   89   79  |12   23   13  
78   89   79  |12   23   13  |45   56   46  
--------------+--------------+-------------
13   123  12  |46   456  45  |79   789  78  
46   456  45  |79   789  78  |13   123  12  
79   789  78  |13   123  12  |46   456  45 
999_Springs
 
Posts: 591
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Re: Pencilmark Sudoku

Postby tdillon » Wed Nov 11, 2020 4:59 am

dobrichev wrote:Now I believe 85's exist.

Seems plausible, even likely. Given the daunting size of the space no feasible amount of searching with the technique I've used provides much evidence for a minimum. For each lower clue count it's taken longer to find an example than for the one before, but not *that* much longer. And in each case finding one puzzle has led to many more nearby. It could be that the hole I'm digging can be deeper. But all the low-clue puzzles I've found share just a few thousand solution grids: maybe there are deeper holes elsewhere.

dobrichev wrote:Do you have canonicalization procedure for pencilmark subgrid? If no, IMO investing some effort there would reduce the times for vicinity search on the cost of huge files containing sorted subgrids that are already checked at {+n}.

No, my procedure doesn't do any canonicalization, or even keeping track of where it's been. It's just random -1+m-n search. i.e., drop a random clue, randomly re-constrain, randomly re-minimize.

dobrichev wrote:Another idea is to generalize the unavoidable set concept to pencilmarks.

This sounds like an interesting approach to explore!
tdillon
 
Posts: 66
Joined: 14 June 2019

Re: Pencilmark Sudoku

Postby dobrichev » Sat Nov 14, 2020 10:04 am

Some fun with the first published 86-constraints puzzle.
tdillon wrote:And here is an example:

Code: Select all
123456789.2345678...3456...123456..912345.7.9123456.89123456.89123456789123456.89.234..78..2345678...34.678.123456789123456789123456.89123456789.234.678..2345678..2345678...345678..23456789123456..91234567.9123456.8912345678912.4.67891234567891234567891234567891.34.6..91234.6...1234.678.1234.6.8.12345678912.4.....12345678.1.3456789..34567891.34567891234567891234567891234567891234567891234567891234567891.3456789..345678.1.345678912345678912345678912345678912.456789123456789123456789123456789.234567891234567891234567.9123456789123456.89123456789123456789123456789123456789.2.456789..3456789123456789.23456789123456789123456789123456789.23456789123456789.234567891.3456789123456789123456789123456.891234567891234.678.123456789


Do {-1}, count solutions, and compare to Megaclue.
39 out of 86 subgrids have number of solutions > 2^31.
Hidden Text: Show
Code: Select all
 #subgr #solutions
      2 6
      1 9
      1 449
      1 614
      1 748
      1 1472
      1 1998
      1 2292
      1 2441
      1 3952
      1 4140
      1 4966
      1 6129
      1 7195
      1 17986
      1 19497
      1 21279
      1 21646
      1 55989
      1 70015
      1 106156
      1 139886
      1 479837
      1 4546427
      1 4551625
      1 4777854
      1 13575352
      1 14097011
      1 16698713
      1 20074729
      1 23077406
      1 24770987
      1 31242441
      1 44192156
      1 84507585
      1 110676460
      1 116574260
      1 122398121
      1 135449860
      1 192709328
      1 255534165
      1 322900083
      1 432065562
      1 569854818
      1 1069800698
      1 1906592388
     39 > 2^31

Nevertheless 3 subgrids have < 10 solutions.
Taking one of them gives the following unsolved pencilmarks, which are easy completable by hand to 2 different valid puzzles after adding a single additional constraint.
Initial pencilmarks
Code: Select all
+-------------------------------+-------------------------------+-------------------------------+
| 123456789 2345678   3456      | 1234569   1234579   12345689  | 12345689  123456789 12345689  |
| 23478     2345678   34678     | 123456789 123456789 12345689  | 123456789 234678    2345678   |
| 2345678   345678    23456789  | 1234569   12345679  12345689  | 123456789 1246789   123456789 |
+-------------------------------+-------------------------------+-------------------------------+
| 123456789 123456789 13469     | 12346     1234678   123468    | 123456789 124       12345678  |
| 13456789  3456789   13456789  | 123456789 123456789 123456789 | 123456789 123456789 123456789 |
| 13456789  345678    13456789  | 123456789 123456789 123456789 | 123456789 123456789 123456789 |
+-------------------------------+-------------------------------+-------------------------------+
| 123456789 23456789  123456789 | 12345679  123456789 12345689  | 123456789 123456789 123456789 |
| 123456789 2456789   3456789   | 123456789 23456789  123456789 | 123456789 123456789 23456789  |
| 123456789 23456789  13456789  | 123456789 123456789 12345689  | 123456789 1234678   123456789 |
+-------------------------------+-------------------------------+-------------------------------+

Reduced pencilmarks
Code: Select all
+-------------+-------------+---------------+
| 1   2   4   | 3   5   6   | 8     7   9   |
| 3   5   6   | 7   8   9   | 1     2   4   |
| 7   8   9   | 24  14  12  | 5     6   3   |
+-------------+-------------+---------------+
| 2   1   3   | 6   7   8   | 9     4   5   |
| 456 9   78  | 245 14  13  | 3[6]  18  27  |
| 456 46  78  | 245 9   123 | [3]6  18  27  |
+-------------+-------------+---------------+
| 8   3   2   | 9   6   4   | 7     5   1   |
| 46  46  5   | 1   3   7   | 2     9   8   |
| 9   7   1   | 8   2   5   | 4     3   6   |
+-------------+-------------+---------------+


Removing simultaneously the 3 constraints that alone lead to 6,6,9 solutions, results in this subgrid having 96 solutions which is completable to 2 solution grids by adding back 3 constraints in 24 different ways.
Code: Select all
+-------------------+-------------------+-------------------+
| 1     2     4     | 35    56    356   | 8     7     9     |
| 3     5     6     | 7     8     9     | 1     2     4     |
| 7     8     9     | 24    124   124   | 5     6     3     |
+-------------------+-------------------+-------------------+
| 2     1     3     | 6     7     8     | 9     4     5     |
| 456   469   78    | 23459 12459 12345 | 36    18    27    |
| 456   469   78    | 23459 12459 12345 | 36    18    27    |
+-------------------+-------------------+-------------------+
| 8     3     2     | 49    469   46    | 7     5     1     |
| 46    46    5     | 1     3     7     | 2     9     8     |
| 9     7     1     | 8     25    25    | 4     3     6     |
+-------------------+-------------------+-------------------+
dobrichev
2016 Supporter
 
Posts: 1845
Joined: 24 May 2010

Re: Pencilmark Sudoku

Postby dobrichev » Sat Nov 14, 2020 10:23 am

999_Springs wrote:this puzzle i created should be backdoor size 9 in singles and locked candidates and subsets as well

Hi 999_Springs,

Surely your famous puzzle closes forever all discussions of heroic achievements on this subject.

Well done!
dobrichev
2016 Supporter
 
Posts: 1845
Joined: 24 May 2010

Re: Pencilmark Sudoku

Postby tdillon » Fri Nov 20, 2020 4:51 am

The megaclues are impressive! Following Mladen's example I ran {-1} with solution counting for a different 86 clue puzzle (the first found here) with a limit set arbitrarily at 9e11 (judging this to be either big enough or else a good place to stop and try a different approach). For 13 of the 86 clues removing the clue gives over 900 billion solutions!

Code: Select all
      2 6
      1 9
      1 366
      1 449
      1 614
      1 748
      1 1181
      1 1472
      1 1998
      1 2292
      1 2441
      1 3952
      1 4140
      1 4966
      1 6129
      1 19497
      1 21279
      1 21646
      1 69255
      1 97934
      1 119609
      1 139886
      1 143285
      1 728036
      1 979338
      1 1015375
      1 3131021
      1 3401356
      1 3665796
      1 4295863
      1 7402611
      1 8832652
      1 17990265
      1 19906447
      1 21367839
      1 32945194
      1 33042500
      1 33500378
      1 42490396
      1 73439284
      1 104126185
      1 108464422
      1 146897871
      1 148708920
      1 184854517
      1 201995526
      1 206131255
      1 231231901
      1 305726547
      1 483837442
      1 685870169
      1 1059667519
      1 4542948762
      1 5244212895
      1 5294934615
      1 7618518691
      1 8285396302
      1 8407314757
      1 8728224219
      1 17469422275
      1 20698512585
      1 35660734242
      1 66241408423
      1 72855488273
      1 74022777708
      1 121774376425
      1 126142288689
      1 189192530656
      1 199917561308
      1 308720852029
      1 482056369607
      1 487269219690
     13 900000000000+
tdillon
 
Posts: 66
Joined: 14 June 2019

Re: Pencilmark Sudoku

Postby dobrichev » Fri Nov 20, 2020 5:12 pm

This pattern with only 78 constraints is completable to unique puzzle by adding 8 more constraints.
Code: Select all
+-------------------------------+-------------------------------+-------------------------------+
| 123456789 123456789 123456789 | 123456789 135689    1356789   | 1356789   13689     135689    |
| 23456789  123456789 2456789   | 123456789 1234568   123456789 | 136789    123456789 1356789   |
| 23456789  123456789 2456789   | 12456789  13456789  123456789 | 1356789   6789      123456789 |
+-------------------------------+-------------------------------+-------------------------------+
| 123456789 123456789 123456789 | 123456789 123456789 123456789 | 1236789   12346789  12346789  |
| 1345689   145689    45689     | 123456789 45689     123456789 | 123456789 24689     123456789 |
| 123456789 123456789 123456789 | 123456789 123456789 123456789 | 1236789   12346789  12346789  |
+-------------------------------+-------------------------------+-------------------------------+
| 123456789 12456789  12456789  | 123456789 1345689   123456789 | 12356789  12346789  123456789 |
| 123456789 12456789  2456789   | 123456789 123456789 123456789 | 12356789  123456789 123456789 |
| 12356789  123456789 12456789  | 123456789 123456789 12356789  | 1235678   1236789   123456789 |
+-------------------------------+-------------------------------+-------------------------------+


Adding 4 constrains can be done at least in these 4 quite similar ways which leave these pencilmarks having only 184 solutions.
Hidden Text: Show
Code: Select all
1234567891234567891234567891234567891.3.56.891.3.567891.3.567891.3..6.891.3.56..9.23456789123456789.2.456789123456789123456.8.1234567891.3..67891234567891.3.56789.23456789123456789.2.45678912.4567891.34567891234567891.3.56789.....67891.3456789123456789123456789123456789123456789123456789123456789123..67891234.67891234.67891.3456.891..456.89...456.89123456789...456.891.3456789123456789.2.4...89123456789123456789123456789123456789123456789123456789123456789123..67891234.67891234.678912345678912.45678912.4567891234567891.3456.89123456789123.567891234.678912345678912345678912.456789.2.456789123456789123456789123456789123.56789123456789123456789123.5678912345678912.456789123456789123456789123.56789123.5678.123..6789123456789
1234567891234567891234567891234567891.3.56.891.3.567891.3.567891.3..6.891.3.56..9.23456789123456789.2.456789123456789123456.8.1234567891.3..6789123.567891.3.56789.23456789123456789.2.45678912.4567891.34567891234567891.3.56789.....6789123456789123456789123456789123456789123456789123456789123456789123..67891234.67891234.67891.3456.891..456.89...456.89123456.89...456.89123456789123456789.2.4...89123456789123456789123456789123456789123456789123456789123456789123..67891234.67891234.678912345678912.45678912.4567891234567891.3456.89123456789123.567891234.678912345678912345678912.456789.2.456789123456789123456789123456789123.56789123456789123456789123.5678912345678912.456789123456789123456789123.56789123.5678.123..6789123456789
1234567891234567891234567891234567891.3.56.891.3.567891.3.567891.3..6.891.3.5..89.23456789123456789.2.456789123456789123456.8.1234567891.3..67891234567891.3.56789.23456789123456789.2.45678912.4567891.34567891234567891.3.56789.....67891.3456789123456789123456789123456789123456789123456789123456789123..67891234.67891234.67891.3456.891..456.89...456.89123456789...456.891.3456789123456789.2.4.6..9123456789123456789123456789123456789123456789123456789123456789123..67891234.67891234.678912345678912.45678912.4567891234567891.3456.89123456789123.567891234.678912345678912345678912.456789.2.456789123456789123456789123456789123.56789123456789123456789123.5678912345678912.456789123456789123456789123.56789123.5678.123..6789123456789
1234567891234567891234567891234567891.3.56.891.3.567891.3.567891.3..6.891.3.5..89.23456789123456789.2.456789123456789123456.8.1234567891.3..6789123.567891.3.56789.23456789123456789.2.45678912.4567891.34567891234567891.3.56789.....6789123456789123456789123456789123456789123456789123456789123456789123..67891234.67891234.67891.3456.891..456.89...456.89123456.89...456.89123456789123456789.2.4.6..9123456789123456789123456789123456789123456789123456789123456789123..67891234.67891234.678912345678912.45678912.4567891234567891.3456.89123456789123.567891234.678912345678912345678912.456789.2.456789123456789123456789123456789123.56789123456789123456789123.5678912345678912.456789123456789123456789123.56789123.5678.123..6789123456789

Code: Select all
+----------------------+----------------------+----------------------+
| 1      2      3      | 4      5      68     | 7      68     9      |
| 4568   4568   568    | 7      68     9      | 1      2      3      |
| 678    6789   79     | 1      3      2      | 5      68     4      |
+----------------------+----------------------+----------------------+
| 245678 456789 256789 | 689    14     35     | 268    13     678    |
| 3      1      68     | 2      68     7      | 4      9      5      |
| 245678 456789 256789 | 689    14     35     | 268    13     678    |
+----------------------+----------------------+----------------------+
| 57     57     1      | 68     9      68     | 3      4      2      |
| 268    68     268    | 3      7      4      | 9      5      1      |
| 9      3      4      | 5      2      1      | 68     7      68     |
+----------------------+----------------------+----------------------+

They are resolvable to unique solution by adding 4 more constrains in 944 different ways. Below are the first and last.
Hidden Text: Show
Code: Select all
1.........2.........3.........4.........5...........8.......7.......6.8.........9...456.8....456.8.....56.8.......7.......6.8.........91.........2.........3............78......6789......7.91..........3.......2...........5.........6.8....4........45678....456789.2..56789.......891..4.......3.5.....2...6.8.1.3...........678...3......1.............6.8..2............6.8.......7.....4.............9....5.....2.45678....456789.2..56789.....6.891..4.......3.5.....2...6.8.1.3...........678.....5.7......5.7..1.............6.8.........9.....6.8...3.........4......2........2...6.8......6.8..2...6.8...3............7.....4.............9....5....1................9..3.........4.........5.....2.......1.............6.8.......7.......6.8.
1.........2.........3.........4.........5.........6.8.......7.......6.8.........9...456.8....456.8.....56.8.......7.......6.8.........91.........2.........3...........678......6789......7.91..........3.......2...........5.........6.8....4......2.45678....456789.2..56789.....6.891..4.......3.5.....2...6.8.1.3...........678...3......1.............6.8..2............6.8.......7.....4.............9....5.....2.45678....456789.2..56789.....6.8.1..4.......3.5.....2...6.8.1.3...........6.8.....5.7......5.7..1.............6.8.........9.....6.8...3.........4......2........2...6.8......6....2...6.8...3............7.....4.............9....5....1................9..3.........4.........5.....2.......1.............6.........7.......6.8.

The final result is a bunch of about 4K 86-givens puzzles.

It is quite possible all discovered by Tom 86s to be very close to this configuration.
Hope this isn't a killing local minimum.
dobrichev
2016 Supporter
 
Posts: 1845
Joined: 24 May 2010

Previous

Return to Software