8 2 5 |4 3 7 |1 6 9 E1 E2 E3| E4 E5 E6| E7 E8 E9 .
Finnish mathematician Arto Inkala described his as "the most difficult sudoku-puzzle known so far" and his as "the most difficult puzzle I've ever created." My program solves them in 0.01 seconds each ( will bedefined below):
7 9 1 |5 8 6 |4 3 2 F1 F2 F3| F4 F5 F6| F7 F8 F9 .
Itdidn't work for my friends (although my wife has since independentlykicked the habit without my help), but at least one stranger wroteand said this page worked for him, so I've made the world moreproductive.
Theresults were starkly bimodal: in 27 out of 30 trials the puzzle tookless than 0.02 seconds, while each of the other 3 trials took just about190 seconds (about 10,000 times longer).
But squareshave names like , not .
If Iimplemented a possibility as a Python or Iwould need to use , which is lessefficient.) The alternative is to keep track of each change to and undo the change when we hit a dead end.
Therefore, will be a dict with squares as keys.
Simple: first make sure we haven'talready found a solution or a contradiction, and if not, choose oneunfilled square and consider all its possible values.
So agrid where is and is empty would be represented as .
It makes sense when each step inthe search is a single change to a large data structure, but iscomplicated when each assignment can lead to many other changes viaconstraint propagation.
Here is the code to parse a grid into a dict:
In fact, it turns out that to solve this particular puzzle we needto look at only 25 possibilities and we only have to explicitly searchthrough 9 of the 61 unfilled squares; constraint propagation does therest.
We could implement this as , but we can do morethan just that.
Suppose we have avery efficient program that takes only one instruction to evaluate aposition, and that we have access to the next-generation computingtechnology, let's say a 10GHz processor with 1024 cores, and let's saywe could afford a million of them, and while we're shopping, let's saywe also pick up a time machine and go back 13 billion years to theorigin of the universe and start our program running.
Unfortunately, that will notalways be the case.
Forvariable ordering, we will use a common heuristic called , which means that we choose the (or one of the)square with the minimum number of possible values.
We could code that strategy in a few lines by adding an test to .
Coding up strategies like this is a possible route, but would requirehundreds of lines of code (there are dozens of these strategies), and we'dnever be sure if we could solve puzzle.