A simple way to find extreme sudokus
In my High clue tamagotchis thread (unfortunately almost lost by the forum crash) i could show, that with a simple method and a few tricks it is possible to find much more minimal 39's on a PC than Intel managed with parallel processing on a super computer. After that i wondered, if the same method could be applied for finding extremely hard sudokus either, and it was.
There is only one significant difference between Havard's work and mine. We both worked up from low clue to high clue puzzles with {-1+2} (replace one clue by two ones and look, if you can get a unique puzzle) and eventually broadened our sets with {-n+m}, n,m being up to 3 or 4. While (as i think) Havard did it linearly (one swap of big sets after the other), i did it in a loop. This has the advantage, that you have much quicker feedback, so that i could experiment, tune and improve the process, while the gotchi already was running and producing results.
It was always clear to me, that i could not be the first one, who used this method. But only recently a mathematician pointed me to the Genetic Algorithm heuristic. It turned out, that my gotchis are something like school examples for it (the funny thing is, that i remembered then to have read about it earlier, but i had found it little attractive and rarely successful at that time).
However i will stick to my own words, when describing it, but it will be easy e.g. to replace "expand" my "mutation" to see the correlation.
"Real" mathematicians dont like such heuristics. They are only vaguely defined and it depends on trial&error, luck, intuition and the skill of the creator, if they give good results. A main disadvantage also is, that the results cannot be used for statistical investigations (e.g. you cannot say something serious about the quality of results, statistical probabilities, barriers etc.).
On the other hand those who had most successfully searched for extreme sudokus all have used the same basic concept of neighbourhood search, with the same disadvantages, from Gordon Royle to ano1, Havard to blue, tarek to coloin. The point is, that extreme sudokus are clustered like the mountains on earth. Near high peaks you have the best chances to find higher ones.
Preferences
The basic operations of a gotchi are to expand, evaluate and filter a set to get the next generation.
Expansion is done with neighbourhood search, for sudokus {-n+m} is the simplest way.
Evaluation of course depends on the target function. For min/max. clue search a puzzle is the better, the less/more clues it has, for hardest sudokus the better the rating is.
Filtering for min/max. clues mainly is already done by removing all duplicates and invalid puzzles in the {-n+m} calculation, for the hard sudokus search i had to find other fast methods, the most important one already had been implemented in Brian Turner's bb-solver (thanks again for this great program), nameley that the puzzle cant be solved with cell forcing chains (STEP 1).
This concept was all i needed to start the gotchis and find much with little effort and a very good fun/frustration ratio. But of course there are other requirements i needed:
- public programs like Brian's bb-solver, dukuso's suexg and gsf's sudoku. Those guys did the main work i needed for fast solving, generating and canonicalizing puzzles.
- a PC, which is rarely shut down, where i could run the gotchis in the background.
- some C/C++ knowledge to write the additional tools i needed, partly by modifying the bb-solver for my purposes. (This did not take me more than 2 weeks each - and was not done in a way i could present)
- some basic knowledge in scripting (batch processing). This is important to be able to make changes on a running gotchi. When you have a script, which calls the scripts expand, evaluate and filter cyclically, you can alter each of them at any time without stopping the program. This is very useful for experiments and improvements. Most useful for me have been the unix commands cp, mv, cat, grep, fgrep, sort, uniq and cut for all the (sudoku) file operations i needed.
- patience
you will not find a 39 or 11.9 in a dayGoing live
A gotchi is "living", as long it runs (cyclically) and produces something of more or less worth. When you have a living gotchi, you can start to optimize it, mainly by scaling the filters or introducing new ones, but also by making it more complex or improving the expand function.
At the beginning you will use weak filters to get a good starting population (e.g. some 1000 sudokus) and then make them harder for good results. (Of course you can also try more than one starting gotchi with different methods.)
Most important is, that the gotchi does not become too thin or fat. In the first case it might die and you have to restart, in the second one you will have to wait too long for the next generation, where you have the chance to see, where it is going (less than one generation a day normally turned out to be as waste of time). However, when you dont have time for it for a week or two, its no problem, when it produces a big, but less worthful set - this is one of the advantages, also bad gotchis produce useful information.
There is an "inbuilt" nice property for the sudoku problems, when you have managed to keep a minimum and maximum gotchi size. Small sudokus with puzzles in less useful areas will automatically run faster through the space, because the next generations are quicker reached.
This is, how i started the gotchis for the 2 problems:
Starting the high clue gotchi
It was easy for the high clue search. Just start with random puzzles (in my case 28 clues) and do {-1+2} as long as you can find (n+1) clue puzzles, the next generation.
The first problem was, that the number of puzzles exploded up to about 31 clues. My first way to filter them was to make a random selection, later i found, that taking the puzzles with high "eleven weights" lead to better results.
The second was, that the air became thin with 35 clues. No problem, i added a {-1+1} to get a fatter generation. One or two {-1+1}'s for the 36 clue puzzles and i had my first 37 generation (in fact i made 2 of them, with about 1000 puzzles each), the starting set of the gotchi.
Starting the hard sudokus gotchi
In the hard sudokus search i had the advantage, that i could test possible filters with the known "hardest sudokus", given in champagne's ER list with 488 puzzles. None of them could be solved with the "STEP 1" method in the bb_solver (just comment out STEP 2 and GUESSING to see it). But it was clear, that my chances to find such puzzles in random sets were bad. So i had to find a weaker and scalable filter. A quick idea was to count the candidates after basic solving methods (which are also implemented in the solver), which i improved then by evaluating, how much of them could be eliminated with STEP 1 and how much bivalue cells and strong links the grid has. Then i used this trivial rating: # candidates - 3*# eliminations - 4*# bivalues - 3*# links. This is far away from being a good rating, and there will be hundreds of better/quicker ones, but it was fast enough and had some correlation to a serious rating. The hardest known had values of about 150 to more than 200, random puzzles less than 0 - thats good enough for a gotchi's weak filter. (Since at that time i already was quite familiar with the bb-solver, the modifications i needed to count the possible eliminations were done in a day).
Then i started with a set of some 10000 24 clues and a first filter value 0, expanding them with {-1+1} and raising the filter value, until i had found some 1000 STEP 1/filter 140 puzzles. This took some days, maybe a week, then i had my first set of ER 10+ puzzles (the big majority of "STEP 1 puzzles" have ER > 10 also).
Basics
On this way i created a lot of files, most of them i did not not need again, e.g. the "29 clues" or "filter 50" files. So i used different ways to "clean up". Some of them i removed manually, some i overwrote with the next generation, and when i lost the survey, i restarted in a new directory.
When the gotchi is running well then, only the "all" and "current generation" files will remain, containing e.g. the sets of the 37+ sudokus found, the 37 clue puzzles not yet expanded with {-2+2}, and the expanded puzzles of the current generation, pure, canonicalized, with duplicates removed etc. In another directory the current sets of 28+ puzzles working up to 37 to be added to the "high clue gotchi".
Similar with the "hard sudoku" gotchi, where i have the best rated puzzles for 24 down to 21 clues, the weak filter sets needed to recognize duplicates, all ER and q2 rated puzzles and a few more beside of the generation sets.
Beside of the danger, that the gotchi becomes too big, there is the one, that the files become too big. When you look for 17 clues, you can start with an 18 clue, look with {-2+1}, if there is a 17 clue below, and expand it with {-1+1} for the next generation. ano1 has found out, that you can find about 900 mio 18 clues (maybe the half of all exiting ones) and more than 90 % of the 17 clues this way (if you have enough time and CPU). But its not trivial to deal with such big data sets.
When i tried to get more 37's, i noticed, that its faster for me to do a {-2+1}{-1+1}{-1+2} than a {-2+2} to get new ones. But the problem was, that my 36 sets would become that big, that e.g. the test for duplicates would have become more and more costy.
So instead i did it this way then: i made a {-2+2} to all puzzles with {-1+1} neighbours (because they seemed to be in a "denser" region), and if there were less than a lower limit of say 1000, i added the ones with highest "weight" (the average number of solutions a puzzle has, when you remove a clue - the higher it is, the better are the chances on average, that a n+1 clue puzzle is "near").
High clue gotchi
This already describes almost all, i used for the high clue search gotchis. The "bottom up" gotchi was rather slow and needed about 5 days to find about 1000 new 37's. Those were stored in a file and added to the "high clue" gotchi's new generation set. This one tried a {-1+2} on each 37 to find 38's. On all 38's i made {-2+2}, and then up to {-3+4} to find 39's, also {-2+1} to get more 37's. The 39's were tried to expand with {-3+3}.
A half year after i had finished, dobrichev had this nice idea to look at the complement of a puzzle in its solution grid. All its solutions must have a valid puzzle in the original cells (one being the original puzzle). Since the complements of high clues have relatively few givens, you often can find new puzzles this way, and it was easy to implement and fast. In some seconds CPU he could find 27 new 39's (82 known before). I also "dobbed" my sets and added that to the "expand" parts. So (starting with the dobbed set) i could more than double my set of 37's in 2 weeks without doing any {-2+2} operation on them (and found 10 more 39's). This shows, that good ideas also for gotchis are the essential thing for success.
As you can see in my thread, blue did it better later, he found much more 39's than me in shorter time - and did not use a gotchi. But he was so friendly to say, that my puzzles were a big help to achieve that
Hardest sudokus gotchi
Now back to the hardest search. The 24 clue gotchi grew fast, and i could raise the filter value to 150. I found many 1000 "STEP 1" puzzles each day.
Now my goal was to find puzzles with high Explainer rating, which is the best accepted public one. It has the disadvantage, that rating a hard puzzle takes minutes. The fastest public filter i had was gsf's q2 rating, which i used for the first weeks to select the puzzles for ER. The correlation between the ratings is not good, but obviously there is some. So i found the first ER 11+ puzzle in less than 2 weeks.
The next steps were to go down to 23 and 22 clues. I took the highest q2 rated puzzles and those with highest filter values and made a {-2+1} to get the starting set for 23 clues, later i did the same for 22. Surprising was, that i had to lower the filter values to 140 and 135 resp. to keep the lower clues gotchis running. But then they developed fine with even more "STEP 1" puzzles daily and - harder puzzles. Since there was such a flood of new puzzles, i needed more (and quick) filters both for selecting the ones for rating and reducing the size of the gotchi generations. Also i could stop the 24 clue gotchi, because i did not expect the hardest there.
An easy to implement filter in the bb-solver was to extend the one cell forcing chains (using basics on the way) to 2 cells in the same unit, which dont have more than 2 different candidates (starting with the possible combinations). This filter eliminates about 70% of the puzzles.
Another filter i made - again by modifying the bb-solver, had the intention to filter out some relatively easy "set techniques", which are not implemented directly in the Explainer. I made some experiments, which showed, that the hardest puzzles even can resist any technique, which does not make use of at least one cell of each box. That means, that if i fade out a box and the six lines connected, i cannot eliminate a single candidate in the reduced grid - each one finds a partial solution in the 21 other units. This filter eliminated more than 90 % of the "STEP 1" puzzles (and a part of the known 11+), but kept some puzzles, the other filter would have eliminated (so it maybe of worth to find hard puzzles for other ratings).
In the 23 clue space it turned out, that the gotchi was living fine, when i only took the puzzles, which passed one of the filter plus some 1000 with the best weak filter value. In the 22 space this would reduce the STEP 1 sets drastically, so i take all STEP 1's of the current generation, when the number of filtered puzzles is below a limit. This gotchi is additionally feeded with the 23 clues' non minimal puzzles and the {-2+1} expanded puzzles, which had been selected for rating.
Both filters are about 10 times faster than q2, so - to save time - i only q2 rated filtered puzzles to select those with high rating (>98000) for the Explainer rating then. This gave me puzzles with an average ER of more than 10.6 and more than 10% have an ER above 11.
The last step then was to go down to 21 clues also a few weeks ago. This was done easily with copy/paste and adjusting the parameters (here i needed weaker conditions again to keep it running).
Much could be improved in this gotchi version, but since i am a lazy person, in the moment i am happy to have found about as much new hard puzzles as known before, and leave it alone.
