The New Sudoku Players' Forum

by **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.

by **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

by **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!

by **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

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 | +-------------------+-------------------+-------------------+

by **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!

by **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+

by **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

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.

The New Sudoku Players' Forum

Pencilmark Sudoku

Re: Pencilmark Sudoku

Re: Pencilmark Sudoku

Re: Pencilmark Sudoku

Re: Pencilmark Sudoku

Re: Pencilmark Sudoku

Re: Pencilmark Sudoku

Re: Pencilmark Sudoku