The hardest sudokus (new thread)

Everything about Sudoku that doesn't fit in one of the other sections

Re: The hardest sudokus (new thread)

Postby denis_berthier » Wed May 18, 2022 8:06 am

.
Hi Hendrik
Great work

1251 of the total 4726 puzzles can be solved using only Subsets, Finned Fish and the basic Tridagon elimination rule defined here: http://forum.enjoysudoku.com/the-tridagon-rule-t39859.html
Code: Select all
    1 2 118 119 120 126 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 145 150 158 159 160 161 162 168 171 173 174 179 180 181 182 183 184 187 188 210 211 212 213 223 224 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 254 255 256 257 258 259 260 261 262 263 264 267 268 269 270 271 272 273 323 324 325 326 328 330 334 337 342 343 344 345 346 347 349 361 365 366 391 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 471 472 473 474 475 476 477 478 501 502 503 504 505 506 507 509 510 511 526 529 530 531 533 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 619 620 630 633 655 656 657 658 665 666 667 668 669 670 672 673 674 675 676 677 680 698 704 742 743 744 745 746 747 748 749 750 751 752 753 754 762 763 768 769 770 771 772 773 774 775 776 777 794 795 796 797 807 808 813 814 815 817 818 820 821 822 823 857 858 859 860 861 896 901 903 904 905 906 907 908 909 910 911 912 913 914 915 916 918 944 945 948 949 950 951 952 953 954 955 956 957 958 959 973 974 976 977 978 980 983 1032 1033 1034 1049 1050 1051 1052 1053 1054 1078 1176 1202 1210 1240 1241 1246 1259 1260 1261 1264 1265 1266 1267 1268 1271 1289 1297 1301 1302 1304 1305 1312 1313 1316 1317 1319 1320 1321 1322 1323 1324 1325 1333 1334 1336 1380 1419 1420 1440 1453 1464 1465 1466 1471 1472 1473 1474 1475 1517 1521 1522 1523 1530 1531 1532 1552 1553 1554 1555 1556 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1594 1595 1596 1597 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1677 1693 1695 1696 1697 1699 1700 1701 1704 1705 1707 1718 1719 1720 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1762 1764 1864 1866 1868 1900 1922 1931 1932 1933 1934 1935 1936 1942 1950 1951 1953 1954 1955 1956 1957 1958 1959 1961 1962 1963 1964 1966 1968 1969 1970 1971 1972 1973 1974 1976 1978 1979 1980 1981 1982 1983 1985 1986 1987 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2011 2012 2075 2076 2098 2099 2100 2101 2102 2113 2114 2115 2213 2215 2216 2217 2234 2239 2240 2241 2242 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2371 2377 2379 2415 2416 2418 2419 2421 2470 2471 2472 2473 2474 2475 2476 2526 2527 2528 2529 2563 2564 2565 2569 2570 2571 2572 2573 2574 2575 2576 2579 2580 2581 2582 2596 2597 2598 2601 2613 2618 2619 2622 2623 2628 2629 2630 2631 2632 2633 2634 2635 2636 2639 2642 2643 2644 2645 2650 2651 2652 2653 2658 2659 2660 2661 2664 2665 2666 2672 2673 2674 2675 2676 2677 2678 2679 2680 2684 2685 2686 2687 2688 2689 2691 2692 2695 2696 2701 2702 2703 2704 2705 2706 2710 2714 2715 2718 2733 2737 2740 2741 2742 2743 2744 2745 2746 2747 2748 2752 2802 2803 2851 2852 2853 2854 2855 2856 2857 2858 2859 2860 2865 2873 2874 2875 2876 2877 2878 2879 2880 2881 2882 2893 2907 2911 2917 2918 3028 3029 3030 3031 3032 3045 3046 3056 3057 3058 3059 3060 3063 3065 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3122 3125 3126 3127 3128 3129 3131 3132 3133 3135 3138 3139 3141 3142 3143 3145 3148 3149 3150 3151 3152 3154 3155 3158 3159 3161 3162 3168 3170 3171 3172 3200 3231 3235 3257 3258 3259 3260 3274 3286 3287 3288 3289 3290 3291 3292 3293 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3326 3329 3330 3331 3332 3333 3335 3337 3339 3341 3343 3346 3347 3348 3350 3352 3354 3357 3362 3364 3365 3366 3368 3369 3370 3371 3372 3373 3375 3376 3377 3378 3379 3380 3381 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3443 3461 3462 3463 3464 3465 3466 3473 3486 3487 3488 3490 3491 3492 3494 3508 3509 3510 3511 3513 3514 3515 3516 3526 3527 3528 3530 3532 3534 3555 3557 3560 3561 3562 3563 3571 3572 3573 3574 3576 3577 3579 3580 3585 3586 3587 3590 3592 3593 3596 3598 3601 3603 3605 3608 3609 3610 3611 3612 3613 3621 3622 3623 3624 3625 3626 3627 3644 3648 3649 3650 3651 3652 3653 3654 3655 3661 3662 3664 3665 3666 3667 3668 3670 3672 3674 3676 3678 3686 3688 3690 3695 3696 3754 3755 3756 3757 3758 3759 3760 3761 3762 3763 3765 3772 3774 3785 3786 3787 3813 3814 3815 3816 3835 3836 3837 3838 3839 3842 3850 3859 3860 3863 3864 3872 3875 3876 3877 3878 3880 3882 3883 3885 3886 3889 3890 3902 3903 3904 3907 3908 3936 3937 3938 3939 3942 3953 3954 3957 3958 3962 3963 3965 3968 3971 3973 3976 3978 3981 3985 3987 3989 3992 3994 3997 3999 4000 4001 4002 4033 4034 4035 4037 4039 4041 4042 4043 4044 4058 4059 4076 4077 4078 4079 4080 4119 4120 4122 4124 4126 4127 4128 4130 4131 4132 4133 4134 4135 4146 4196 4197 4198 4199 4200 4201 4202 4203 4204 4205 4206 4207 4208 4209 4241 4252 4253 4254 4257 4259 4260 4261 4262 4263 4264 4265 4266 4267 4271 4272 4273 4274 4276 4277 4279 4280 4281 4286 4287 4288 4290 4291 4296 4297 4298 4299 4315 4316 4317 4318 4319 4320 4321 4341 4342 4343 4344 4345 4346 4347 4348 4349 4350 4352 4353 4355 4358 4359 4362 4377 4378 4381 4382 4384 4386 4421 4422 4423 4424 4425 4428 4429 4444 4445 4446 4447 4448 4455 4456 4468 4475 4476 4477 4479 4482 4487 4489 4491 4492 4495 4497 4499 4527 4528 4529 4530 4532 4533 4534 4535 4538 4561 4563 4564 4565 4567 4568 4569 4570 4571 4572 4573 4600 4601 4602 4603 4604 4605 4606 4607 4608 4609 4616 4617 4618 4619 4620 4621 4622 4623 4624 4625 4626 4681 4682 4683 4684 4685 4686 4687 4688 4689 4690 4691 4692 4693 4694 4696 4697 4698 4699 4700 4701 4702 4703 4704 4705 4706 4707 4725 4726


As there are many redundancies (same expanded versions ...), I didn't try any deeper analyses (e.g. withTridagon-Forcing-whips).
denis_berthier
2010 Supporter
 
Posts: 4190
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby eleven » Thu May 19, 2022 11:08 am

After all these pages about Thor's Hammer puzzles people may have got the impression, that even the hardest puzzles can be solved in a way, which can be followed without big effort. But as an example, i have never seen such a solution to my puzzle Kolk (and thousands others in champagne's list):
Code: Select all
.2..5.7..4..1....68....3...2....8..3.4..2.5.....6...1...2.9.....9......57.4...9..
eleven
 
Posts: 3150
Joined: 10 February 2008

Re: The hardest sudokus (new thread)

Postby denis_berthier » Thu May 19, 2022 2:55 pm

eleven wrote:After all these pages about Thor's Hammer puzzles people may have got the impression, that even the hardest puzzles can be solved in a way, which can be followed without big effort. But as an example, i have never seen such a solution to my puzzle Kolk (and thousands others in champagne's list):
Code: Select all
.2..5.7..4..1....68....3...2....8..3.4..2.5.....6...1...2.9.....9......57.4...9..

In what isomorphic form does this puzzle appear in your list of 26370 or in the ph2010 database? I can't find it, nor its name.
AFAIK, your list of 26370 puzzles was pattern independent, right?

Many (but not all) of the recently found puzzles, based on the TH pattern, have much easier (even sometimes really easy) solutions after applying some particular rule related to this pattern. But many of them also remain difficult.
A similar remark can be applied to puzzles built after the sk-loop pattern or other patterns - except that the corresponding elimination rule is rarely enough to make them easy to solve.
Because of the way they are generated (vicinitiy search seeded with puzzles having the desired pattern), all the pattern-generated puzzles give the false impression that they are more frequent than they really are.
Actually, the same vicinity search has been applied to seeds with no special pattern, but in this case we less easily notice that two puzzles are neighbours because there's no pattern to be seen.

What adds to the false impression of frequency in the tridagon case is the application of an additional process of (a different type of) proximity search: expanding the minimal puzzles with Singles and re-starting the search for minimals from the expanded versions - with all the advantages in terms of numbers of puzzles found and all the disadvantages in terms of redundancy.
denis_berthier
2010 Supporter
 
Posts: 4190
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby mith » Fri Jun 10, 2022 7:26 pm

Hi all, sorry for the long delay.

I cut off the depth 3 generation for a while, and let SE catch up. All 375103 expanded forms are now SE rated; there are the 3 known 11.9 forms, 94 11.8s, and a further 50k+ 11.6-11.7. I haven't yet correlated these with the minimal forms and compared to the "potentail hardest" database. I suspect there is going to be a lot of overlap with hendrik's recent list - I'll work on that this weekend. If there are any new depth 3 puzzles in hendrik's list, I'll expand and add them to the new database (along with running the minimizer, transformer, and depth_adder scripts to catch any relatedd puzzles, if any).

I have unfortunately been very busy and also ill, so I haven't made any progress on the utility scripts I'm planning, but I will try to at least get the databases up on my website in the next week.
mith
 
Posts: 996
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby hendrik_monard » Tue Jun 14, 2022 9:46 am

Hi Mith,

Glad you're back.
This Thread had vanished for a few weeks after May 19th which explains the absence of posts until your message of June 10th.
I suppose you also followed the discussion in a new thread launched by Denis about that situation:
hardest-thread-disappeared-t40014.html#p321617
Personally, I have concentrated my activities on derivatives outside the solution grid of existing puzzles, rather than mere expansions within the solution grid, as we should avoid duplicating our efforts. However my future results may still contain some expansions.
hendrik_monard
 
Posts: 96
Joined: 19 April 2021
Location: Leuven (Louvain) Belgium

Re: The hardest sudokus (new thread)

Postby mith » Mon Jun 20, 2022 3:48 pm

hendrik, to make sure I don't miss anything would you mind compiling a single list of your 11.6+ puzzles since my March 21 post (the-hardest-sudokus-new-thread-t6539-1230.html#p318907)?

Yet another illness here is slowing me down (it's silly how often we get sick since our son started kindergarten), but should make some actual progress this week.
mith
 
Posts: 996
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby mith » Tue Jun 21, 2022 12:38 am

From the list of hendrik's puzzles I put together (which is hopefully complete), I identified 488 minimals which are depth 3 and weren't already in my depth 3 minimals db (I believe I had already added some from the April post, so that's probably not a full count). Those 488 minimals belong to 249 expanded forms. I'm running all the "family" scripts on these now, as well as rating the expanded forms. (I've already found a number of related expanded forms - the count after adding hendrik's would have been 375352, and now it is up to 375655. [edit]Finished now, it's at 376258. though that's with some early duplicates I still need to remove. Final count should be 375759.[/edit])
mith
 
Posts: 996
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby mith » Tue Jun 21, 2022 4:45 pm

Ok, they are all rated now, and the duplicates are removed. I'll work on getting things in a publishable form today.

Here's a breakdown by ER - just a curiosity really, since likely *all* of these are 11.6+ with uniqueness disabled.

Code: Select all
4.5|257
4.6|11
5.6|19
6.6|331
6.7|22
7.1|75
7.2|60
7.3|15
7.6|8
7.7|49
7.8|8
8.0|1
8.3|136
8.4|80
8.5|10
8.8|3
8.9|74
9.0|522
9.1|755
9.2|1787
9.3|2040
9.4|562
9.5|19
9.6|132
9.7|45
9.8|133
9.9|52
10.0|425
10.1|610
10.2|19583
10.3|49043
10.4|103604
10.5|19791
10.6|19952
10.7|1005
10.8|189
10.9|64573
11.0|26218
11.1|8303
11.2|2171
11.3|284
11.4|11
11.5|406
11.6|23115
11.7|29169
11.8|98
11.9|3


The minimal db wasn't susceptible to the duplication bug I resolved on the expanded side; the only dupes were a couple of hendrik's that got doubled while I was copying them last night. Total count is 1794039. There are three expanded forms accounting for over a thousand minimals each:

Code: Select all
.....1.23..2.3.1....1.4256....21.64..1..653.226.4.3...125....367431.6...8963.....|2750
.....1.23..2.3.1....3.245.6...2.3.54.2..15...35.46.2.1236....1574135....8951.....|2054
.....1.23..2.3.1....3.2456....3.2.45.3..15...25.46.31.326....5174125....8951.....|1077
mith
 
Posts: 996
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby denis_berthier » Wed Jun 22, 2022 8:25 am

mith wrote:From the list of hendrik's puzzles I put together (which is hopefully complete), I identified 488 minimals which are depth 3 and weren't already in my depth 3 minimals db (I believe I had already added some from the April post, so that's probably not a full count). Those 488 minimals belong to 249 expanded forms. I'm running all the "family" scripts on these now, as well as rating the expanded forms. (I've already found a number of related expanded forms - the count after adding hendrik's would have been 375352, and now it is up to 375655. [edit]Finished now, it's at 376258. though that's with some early duplicates I still need to remove. Final count should be 375759.[/edit])

Hi mith
Happy to see you back here.
This very high count (375,759) is for expanded forms?
What about the number of min-expands - i.e. expanded forms that are minimal among expanded forms (or at least minimal among all the expanded forms present in the database)? Do you plan to publish a separate database for them?
denis_berthier
2010 Supporter
 
Posts: 4190
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby mith » Wed Jun 22, 2022 8:50 pm

Yes, the 375759 is for all singles-expanded forms. (This potentially includes forms which don't have any minimals expanding to them!)

My next project will be to write a script finding min-expands, and yes then publish an additional database with them (retaining IDs and such from the full expanded db). (The current set will already include all min-expands, since the minimizer script has been run on them - that is, the set contains all singles-expanded forms of all minimals of the set.)

In the meantime, here are the 375759 puzzles with IDs, for anyone who wants to work with them (; separated). I will eventually get this up in sqlite database form as well, along with the minimals (which I may organize first by expanded form ID).

unix format
dos format

The first 972 are the puzzles originally posted in the google sheets - this has obviously gotten a bit too big for that. :) The last column of these is for the shortened name of the SE technique for the ER step - this is missing from the first 972 because I hadn't retained it at that point, but I'll run those again at some point.
mith
 
Posts: 996
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby denis_berthier » Thu Jun 23, 2022 6:47 am

mith wrote:Yes, the 375759 is for all singles-expanded forms. (This potentially includes forms which don't have any minimals expanding to them!)

How is that possible? Expanded forms are expanded from minimal puzzles. I must be getting it wrong.

mith wrote:My next project will be to write a script finding min-expands, and yes then publish an additional database with them (retaining IDs and such from the full expanded db). (The current set will already include all min-expands, since the minimizer script has been run on them - that is, the set contains all singles-expanded forms of all minimals of the set.)

As you know, I'm mainly interested in the min-expands, for two reasons:
- in order to avoid redundant analyses, especially as the db size grows so fast;
- I think min-expands are a fundamental concept, much more interesting than ordinary minimals, especially now that expansion is systematically used to grow the database.
.
denis_berthier
2010 Supporter
 
Posts: 4190
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby mith » Thu Jun 23, 2022 3:28 pm

The expanded form database started from singles expansions of minimals - however, the correct way to read "singles-expanded form" in the current database is "singles expanded from a depth 3 puzzle, which may or may not be minimal".

This is due to the depth_adder script, which takes a given expanded form and tries every possible digit addition, checking for depth. If the depth is still 3, this new puzzle is (after singles expansion, if applicable) added to the database, but there is no guarantee that it is reachable from a minimal by singles.

If you'll recall Loki, its expanded form is 29c; however, when you applied T&E(2), you ended up with a pencilmark grid having 31 digits filled. This 31c is the "max-expand" of Loki - it is in depth 3, but no more digits can be added without reducing the depth. However, none of its four minimals single expand back up to the 31c.

Code: Select all
solution_minlex of expanded forms in the Loki family:
1.3.56....571.9...69.37......1.93..75.96.73.....51.......96..........4....5...86. (Loki and a 27c singles-expand to this 29c)
1.3.56....571.9.3.69.37......1.93..75.96.73.....51.......96..........4....5...86. (a 26c and a 27c singles-expand to this 30c)
1.3.56....571.9...69.37......1.93..75.96.73.....51.......96..........4..9.5...86. (no minimals singles-expand to this 30c)
1.3.56....571.9.3.69.37......1.93..75.96.73.....51.......96..........4..9.5...86. (max-expand 31, no minimals singles-expand to it)


The full "tree" (not really a tree in the graph theoretical sense) for this family would look like:

Code: Select all
    31c
  /     \
 30c   30c
  \     /
    29c


------

As progress on mapping out these trees and finding the min-expands, I have added the full solution grid in canonical form to the database. There are currently 14155 solution grids. 471 of these only have one expanded form associated with them (so these are necessarily both min-expand and max-expand). The most expanded forms for one solution grid is 905.

Obviously there will be a lot more min-expands than distinct solution grids, but there will also be more max-expands. Just taking that 905 as an example, there are two 37c puzzles associated with it:

Code: Select all
.234.678.4.6......78..2346..3..48..664.2.7..88..63.....7....65..6....912....628.7
.234.678.4.6......78..2346..3..48..664.2.7..88..63....37....65..6....91.....628.7


It is possible that there will be some max-expands like this where we can add one of two digits to an existing puzzle but not both without lowering the depth. However, this one is a case of two distinct trees, despite the huge overlap - the 36c intersection of these is not unique! (The 38c union solves with one x-wing and singles.)
mith
 
Posts: 996
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby denis_berthier » Thu Jun 23, 2022 3:51 pm

.
OK, thanks for the explanations. I was still with the idea that you expanded only minimals.
denis_berthier
2010 Supporter
 
Posts: 4190
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby mith » Thu Jun 23, 2022 10:51 pm

Generating the min-expands now; expecting around 73k based on the current ratio of min-expands per solution grid. [edit]Had to restart because of a really dumb bug that was skipping some. Should run faster now though.[/edit]

The script I'm using should be easy to invert for the max-expands.
mith
 
Posts: 996
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby mith » Fri Jun 24, 2022 12:37 am

63137 min-expands:

unix
dos

15606 max-expands:

unix
dos

Both files have three columns:
solution_minlex (if you want the gsf puzzle_minlex form, you'll need to cross-reference with the expanded_te3 files linked a few posts ago)
tree (this is just an ID of the solution grid, assigned in order of lowest expanded_form ID for a puzzle with that solution)
ID (ID of the expanded form)
mith
 
Posts: 996
Joined: 14 July 2020

PreviousNext

Return to General