 |
Path: physics insights > misc >Sudoku Puzzle Examples
|
See the main Sudoku page for information on the analysis and construction of these puzzles.
| NB -- In the unlikely event
that there are any "repeat visitors" to this page, please note
that the level rating scale has been revised, with level 4
split into two levels, and the old level 5 moved up to level
6. I have also updated the page to include difficulty
ratings ("stars" ratings) for the puzzles. I have also
added a number of new puzzles, toward the bottom of the
page. If you solve every puzzle on this page then you
have too much time on your hands. |
Most of these are level 4 or 5 puzzles. I have never seen a level 4 or 5 puzzle in a daily paper, and I have never seem a level 5 puzzle from any commercial source.
It is worth noting, in passing, that level 4 and 5 boards (which can be solved by use of logic) are considerably harder to create than level 6 boards (which can only be completed using guesswork, and are hence essentially unsolvable). Among randomly generated boards, the latter seem far more common than the former. In other words, producing impossible to solve sudoku puzzles is easy; it's making difficult ones which is hard.
When this page was first written, the "solver level" of each puzzle was given, but they were "unrated" in terms of human difficulty. Since then, I've worked over my solver script's "stars" calculation to use more detailed information about "high level" boards. Consequently, in addition to the level ratings, I can now provide a "difficulty" rating, on a scale running from 1 to 6 stars. The solver's difficulty scale, which was only well defined for low-level puzzles when I first put it together some years ago, was designed to mimic the stars ratings provided by the Conceptis puzzles which I found in the Boston Globe and Ottawa Citizen. For level 1 and 2 puzzles it comes pretty close. For the higher solver level puzzles, its ratings may a little lower than they should be. So, a Level 4 or 5 "4 star" puzzle may be a bit harder than you might expect, and a level 5 "5 star" puzzle may be a great deal harder than you (or I) might expect. In particular, there is substantial variation in how difficult its "4 star" boards are.
The stars scale runs up to six stars because the level 4 and 5 puzzles (and some of the harder level 3 puzzles) are substantially more difficult than the "5 star" puzzles one sees in the papers, and I wanted to reflect that in the rating. So, it's supposed to be more or less comparable to the common "1 to 5 stars" scale, with the extra star reserved for puzzles which just don't fit inside that scale.
In many cases, the "feel" of a level 4 or 5 puzzle is rather different from a level 2 or 3 puzzle. The common 5 star newspaper puzzles are just kind of hard all the way through -- you need to work to find each new value to fill in. The higher level puzzles, on the other hand, tend to seem easy at first, with a number of simple moves ... and then one gets to the tricky bits and it suddenly starts feeling like there's no solution at all. It's often possible to identify exactly when and where the level 4 or 5 move (or moves) became necessary, just because one tends to be stuck there for quite a while before finding the way forward.
The names I've given these puzzles are not exactly catchy. The 'b' suffix reflects the fact that I've hand-rotated some of the boards to look a little better after the generator got done with them.
Click on the puzzle to go to the image, which can be conveniently printed. (Sorry, no slick online-puzzle interfaces here!)
In most cases, I've done the puzzle by hand before putting it on this page. My subjective impression of the difficulty of each one I've done is given just below it. I was surprised to find that the subjective difficulty of puzzles at one solver level varied substantially from one to another, even though they all required about the same level of effort from the solver program; this is reflected, albeit imperfectly, in the recently added "stars" ratings.
These first two level 4 boards were more or less an accident. I found them looking through a list of old boards I'd generated a couple years ago, and never did anything with.
Board 17b -- 4 stars: ****
This is a level 4 board.
Solver's solution to 17b, with possibly descriptive output, is here
This seemed unexpectedly easy; here's my hand solution.
The solver made just one level 4 move in the course of solving it.
Board 23b -- 6 stars: ******
This is a level 5 board.
Solver's solution to 23b here. The solver made 4 "exotic" (level 4) moves in the course of solving it.
When I did it by hand, there were 16 easy moves, and then the bottom fell out. I was reduced to annotating it.
Here's my hand solution. It's a mess, but it's solved.
At the point where things got tough I switched to pencil and red ink.
Board 30 is the first of the boards I generated specifically to be level 4 or 5 boards, for use on this page.
Board 30b -- 5 stars: *****
L4 board.
Solver's solution to 30b is here. The solver needed just one level 4 move to complete it, so I didn't expect it to be all that hard to do by hand.
I was wrong.
What I didn't realize (until I looked more closely at the solver output) was that, first, there were only seven easy moves before the fun began, and second, that the solver had needed five level 3 moves in addition to its one level 4 move ... and level 3 moves can be tricky on a relatively bare board, which is what you've still got after the first seven moves.
So, once again, I was reduced to annotating the board.
And here's my hand solution.
As in board 23b, at the point where I started annotating I switched to a red pen for the values.
After the boards above were generated, I decided I really wanted more transparency into what the solver was doing. The difference in difficulty between board boards 17 and 23 was striking, despite the fact that the solver called them both "level 4" boards when they were generated. (That was before I split level 4, of course.) So I worked it over a bit so that it reports what it does a little (very little) more clearly, and only uses the minimum number of "advanced" moves. Along the way I fixed some bugs which were causing the "interior multiset" step to fail every time (didn't make any difference to what it can solve, but it changed the operation counts it produces).
By that time I'd realized that there was a large difference between a board which requires just one "advanced" move which come when the board is nearly full, and one which requires a string of "advanced" moves very early in the solution. So I wrote a little script which runs the board creator repeatedly, examining the output each time, until it gets the kind of board it wants. I've generated a handful of boards with it.
Board 39b -- 6 stars: ******
Level 4. This was generated by running the board generator repeatedly, under the control of another script, until it produced the sort of board I was looking for. I expected it to be hard ... and it is.
The solver's solution for Board 39b is here. The solver found only 5 "easy" moves before it had to resort to stronger measures. It needed 3 level 3 moves, and 2 level 4 moves, to complete the board.
With a lot of struggling, I managed six moves before I had to annotate the board (one more than the solver's count of 5 easy moves). Here's my hand solution. As usual, my initial moves are in black, but after I annotated I switched to a red pen for the values.
Board 31b -- 5 stars: *****
The solver's solution for Board 31b is here.
Level 5 board. With the solver finding 13 "easy" moves at the beginning, I actually expected this to be relatively simple, and thought I might do it completely without annotation. Hah!
I did indeed make the first 13 moves without much trouble, but then stuck completely on the 14th move.
I switched to Plan B and annotated the board ... and was still stuck for quite a long time.
The 14th move involves 9 cells, all with different possibility lists, and it took me a very long time to spot it.
After that, however, it was clear sailing.
Here's my hand solution.
Around this time, I got the itch to make "prettier" boards. I went through several rounds of changes to the puzzle builder script, teaching it to build within a given pattern, and adding the ability to backtrack and retry if the final board didn't fit within the bounds of the pattern.
It also was given the ability to "build to" a particular solver level, with backtrack and retry from the last point where it had to make a decision if the final level wasn't what was wanted. The goal was to get boards of a particular level which had a particular pattern. Up until this time, the board builder would fill in squares until it had a completely determined puzzle, and then would go back and try blanking out each cell in turn and see if it still had a fully determined puzzle. The "optimization" pass, in which unnecessary squares were cleared, was generally necessary to get anything tougher than a level 1 or 2 board. However, that pass also made producing a board with a particular pattern a lot harder, as whatever the pattern was after the board was first built, it would be shot full of holes by the time the optimizer was done with it.
The builder still can't generate "symmetric" boards on its own -- it must be given a pattern to work with -- but, when run under the build_sudoku_to_spec script, it can produce reasonably high level boards which have an exactly specified layout. (Of course, not all layouts work well. In particular, it turns out that fewer than about 25 cells filled in, or more than about 35 cells filled in, often results in a pattern from which it's hard to create a reasonably high level board.)
This next series of boards was built with the new versions of the builder and driver scripts, and is rather more symmetric than the preceding set.
Board 53b -- 4 stars: ****
The solver's solution for board 53b is here.
This is a level 4 board. I got stuck at move 12, and annotated.
It seemed harder than expected for a "4 star" board.
Board 55b -- 4 stars: ****
The solver's solution for board 55b is here.
This is a level 4 board. It should be about as hard as board 53b, according to the ratings. However, in fact it seemed surprisingly easy; I completed it without annotation. It seems clear that the ratings produced by the solver script are not perfect (or there are some peculiarities in how I solve them by hand which make some boards much harder for me than others).
And now we have two puzzles which I attempted to lob into the gap between "really hard" and "impossible". As previously mentioned, creating an "impossible" (i.e., level 6) puzzle is easy -- they pop out all the time when boards are optimized. Creating a hard one that's not quite impossible takes a lot more computer time. Trying to make them symmetric at the same time cuts the yield by an awful lot. So, these were optimized, and some symmetry lost, in an effort to get the difficulty up.
Board 98c -- 6 stars: ******
The solver's solution for board 98c is here.
This is a level 5 board. It's hard. I annotated before I started it.
Board 97a -- 6 stars: ******
The solver's solution for board 97a is here.
This is a level 5 board, and it lived up to its expectations. It was, like, really hard. I tried it without annotating, and filled in one cell, and got stuck. When I fully annotated it, I turned up four more cells which I should have been able to get without annotation, at least in principle, but hadn't. That matches what the solver found (1 level 1 cell, then 4 level 2 cells, and then over the cliff we go). But from there on it was a hard slog involving serious searching for sets of values which spanned subsets of the cells.
After all the time I spent solving the earlier "really hard" puzzles, I think it's going to be a while before I tackle more very high level boards. So,this next series of mixed level 4 and level 5 boards are ones I have not personally hand-solved.
Several of these were done using the same pattern, which turned out to be easy to build boards from. Consequently, they look very similar, but rest assured that they're entirely different puzzles.
As always, the solver's output is given after the board.
Board 90a -- Level 4, and 4 stars: ****
The solver's solution for board 90a is here.
Board 91a -- Level 5, and 4 stars: ****
The solver's solution for board 91a is here.
Board 92a -- Level 5, and 4 stars: ****
The solver's solution for board 92a is here.
Board 93b -- Level 4, and 4 stars: ****
The solver's solution for board 93b is here.
Board 94a -- Level 4, and 4 stars: ****
The solver's solution for board 94a is here.
Board 95a -- Level 5, and 5 stars: *****
The solver's solution for board 95a is here.
Board 67a -- Level 4, and 5 stars: *****
The solver's solution for board 67a is here.
Finally, in case those aren't hard enough for you, here's one impossible one.
Board 71a -- Level 6, and 6 stars: ******
The solver's solution for board 71a is here.
This one is "stupid hard". The solver went 5 levels deep in guessing in order to solve it!
I haven't tried it, and don't plan to. If you decide to attempt this, I'd suggest scanning and printing a fresh copy of your work each time you need to guess, to that you can back up without too much pain.
That's it for now. Developing these things is fun, but it takes a lot of time, so I think I'll be putting all this aside for a good long time at this point.
|
|
Page created on 5 March 2013, and last updated on 28 April 2013