How the first super hard Sudoku were discovered
Sudoku hardness was intensitvely discussed in forums and starting in 2005. To compare hardness of Sudoku a commonly agreed rating-methods are essential. The follwing ratings are/were popular
- Sudoku Explainer 1.1 (SE) - latest version 1.2.1
- Ravel Minimal Step (RMS)
- AI Root
In the community mid 2006 there was an agreement, that Sudoku above SE 9.0 + rate are hard Sudoku. They can usually not be solved by humans and logic. Also it was found, that less than 1 in 100.000 randomly created Sudoku were hard. The first DE 10.0 + puzzle was already found by a community member - "Ocean".
Then a race for the hardest Sudoku was opened in October 2006 by an outsider. AI Escargot sudoku puzzle became the most difficult known sudoku puzzle in the world, and one of the most famous, in October 2006. It was the first that could not be solve by SE and the orignal program had to be amended. Escargo was created by Arto Inkala (AI).
As already mentioned this homepage only reflects to the SE scale. The key argument for this is, that SE is using pure logic, whereby most other ratings use some kind of trial-and-error. Not everybody will agree to this point of view. Therefore I give a brief summary for the others rating methods to explain.
- Suexrat9 is an advancement of Suexrate. Suexarte counts Knuth DLX nodes. The "Dancing Links" are a very clever way to do backtracking. It's non-trivial. However DLX has a non ploynomional calculation time and is not logic in the here used definition
- GFSR uses depth first and/or breadth first tree search with constraint propagation to prune the search for the next best move (forms of forward checking). There are space/time tradeoffs between depth/breadth first search and the constraints used. See also Backdoors or Magic Cells. The common characteristic for all constraints, here and elsewhere, is that they avoid trial and error. Its fine for a computer to guess and backtrack but a definite breach of puzzle manners to require a human to do so.The last sentende somehow hides that the overall method (depth first and/or breadth first tree search) itself is trail and error and at least need exponentiell calculation time in extreme cases
- RMS was outdated after the invention of the AI Escargo and did not not widespread any more
- AI Root hasn't found a wide range of acceptance in the community and AI root is rarely used except by Inkala himself. When you read the discussion 5 years later it, you may feel that Inkala was an outsider in the community and some might have felt that it was injustice that not a proven member made the breakthrough in hardness of sudoku *)
- basic conflicts - there are only N-1different candidates in N cell in the area
- fish conflicts - when eliminating number from N rows/columns, it will disappear also from N+1columns/rows.
- unique conflicts - this pattern means multiple solutions, all numbers in the pattern exist exactly two times in every area, row and column. If there are only one candidate in the cell, any virtual candidate can be added.
Encountering any of those would indicate that the puzzle is not uniquely solvable. So, if you encounter them as a consequence of “what-if”, you use your eraser and go back to try untried alternatives.
Inkala writes in December 2006 : "At the
most difficult point, a reasoning web of at least eight links is required in
order to solve it by deductive logic. So all eight of those links, or things
affecting each other, must be considered at the same time at the most difficult
point of solving the puzzle." ... and he continues in descibing his Sudoku generator program: "It took several months to create AI
Escargot. I began the project in the summer of 2006, and finished it three
months later. First I ruled out more than 99.99 percent
of all possible Sudoku. Then I went through more than a billion Sudoku
puzzles. " and further:
"What happened next was what I had anticipated: AI Escargot motivated other makers of difficult sudoku puzzles to continue the work. ... I still intend to continue searching for the most difficult sudoku puzzle in the world. This is like a race, resembling the one to find the largest known prime number."
I assume not all members of the community will have liked his last sentences. However Inkala couldn't keep rank 1 for more than a few month. Then his record was pulverized by a new class of puzzles like Easter Monster and Golden Nugget and the ranking program SE had to be amended another time.
Let's say it's not very difficult if you compare it with Golden Nugget and Easter Monster and more hoax than a progress in hardness.