You are viewing onigame

onigame - March 20th, 2006 [entries|archive|friends|userinfo]
onigame

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

March 20th, 2006

(no subject) [Mar. 20th, 2006|01:24 am]
A few months ago, I wrote a long entry here about the "Sudoku Sledgehammer". It caused a little bit of discussion, but the problem that most people reported is that it could really use a few more examples. So, during the last Gathering for Gardner, I was preparing some images for this entry, when Ed Pegg, Jr. looked over my shoulder and said that I should present them at the Gathering, and he graciously gave up some of his presentation time for it. Quite a few people came up to me afterwards thanking me for an interesting presentation. (I think it was mostly because it was short.)

Anyway.

The example I'll use is the final puzzle from the World Sudoku Championship:

(I'm going to assume that you know what a Sudoku puzzle is and what the rules are.)

Bit of a note on how the WSC worked. About 100 participants had one day of solving multiple Sudoku puzzles, and the top 9 were chosen to be in the playoffs the next day. Each round of playoffs lasted 15 minutes, and at the end of the 15 minutes, the player with the lowest "score" (correct squares minus incorrect squares) was eliminated. This went down until the field was of size 3, and then the last puzzle determined the final ranking.

Incidentally, the best Sudoku solver in the world (in my opinion) was eliminated in the penultimate round, by a puzzle that was (in my opinion) too difficult to really be a good gauge of logical ability. (Puzzle competition organizers tend to think that one really difficult puzzle is a better gauge of ability among top players than several medium-level ones. I think that's a mistake; all that happens is that the top players realize that their best chance of solving it in a short amount of time is to start guessing when they get stuck.)

But I digress. Anyway, when most beginners (especially computer-oriented ones) encounter a puzzle, they tend to create something like:

Each of those little numbers I'm calling a Placement. For instance, the upper-left corner, being empty, can contain a 4, 6, 8, or 9. (I've done the "obvious" and eliminated 1, 2, 3, 5, and 7 already.)

If you look at any "How to Solve Sudoku" book or website, you'll see that it tries to teach you lots of different rules on the sorts of deductions you can make regarding these puzzles. One of my discoveries (or rediscoveries, although I don't know of anyone else who has mentioned it) is that almost all of these rules are part of a very general rule, which I call the Sledgehammer.

Here's a method to visualizing the Sledgehammer:

Here we have a Venn diagram with 9 elements and 4 sets. We're trying to solve a constraint-satisfaction puzzle by removing elements, and the constraint we have is that there is exactly one element in each set.

In other words, try to pick some items in that diagram above such that each loop has exactly one item in it.

Try it now.


You'll find that there are several solutions (3, in fact), but they all end up with two stars. The square and triangles are never used. A more general statement might be:

Suppose we have two "Premises" (the red loops), which don't share any elements in common. Suppose we have two "Conclusions" (the green loops), which can share elements in common. Finally, suppose that all the elements in red are also in green (in the example, the stars and square). Then, we can conclude two things:

  • All the non-red green elements (in the example, the triangles) are not in the solution.
  • All elements in more than one green loop (in the example, the square and one of the triangles) are not in the solution.
Why? Well, the elements in red loops already account for two symbols in the solution, and so...
  • ...anything non-red chosen would end up having more than two elements chosen for only two green loops; and
  • ...any "double-counted" elements would result in some green loop with too many elements.
Note that the number two was arbitrary; we can replace the two with any other number and it will work just fine.

Let's see how this applies to some deductions in our Sudoku puzzle.

Here's probably the most basic rule, sometimes called a "Single." The cell labeled J doesn't contain 1, 3, 7, or 9 (because of the row), and it doesn't contain 2, 4, 5, 6 (because of the column). Therefore, we know it must contain an 8.

The relevant set diagram looks like this:

In this diagram, "A5" means "5 goes into the cell labeled A", "B5" means "5 goes into the cell labeled B", and so on. Each one of those is a Placement (defined above).

The first four tall loops are "Column-based Rules". For instance, the first one, containing A5 through J5, can be thought of as the rule "there is exactly one 5 in the column ABCDPQRSJ."

The next four tall loops are "Row-based Rules". For instance, the last one, containing E1 through J1, can be thought of as the rule "There is exactly one 1 in the row EFGHJKLMN."

There are also "Region-based Rules", but not in this example.

All the other loops are "Cell-based Rules". For instance, the bottom loop, containing J5 through J8, means "there is exactly one digit in cell J". The small loop at the top containing only A5 means "there is exactly one digit in cell A" -- normally it would contain A1, A2, A3, A4, A6, A7, A8, and A9, but we've eliminated those since it was a given that cell A contained a 5.

Now, let's look at a Premise-Conclusion pair:

The Sledgehammer rule applies here; there's one Premise (in red), one Conclusion (in green), and all the red is part of the green. Therefore, we can eliminate all the non-red green elements. Doing this for all the vertical pairs results in:

Now, the last horizontal set has only one element left. Whenever that happens it means that we have determined a Placement that must be in the solution, so we can write 8 into the space labeled J.

Let's look at a different basic heuristic:

This heuristic is sometimes called a "Naked Single." The 7 in cell A and the 7 in cell E mean that a 7 cannot be in cells B, C, D, or G. Since F is the only unoccupied cell left in the bottom Region, a 7 must go into cell F.

Here's what the set diagram looks like:

There's much more of a variety of Rules here. I've gotten a bit lazier here and didn't bother writing out all the Placements in the BCDE row and the ABG column, although I did write out all the Placements in the "F has a digit" Rule.

Looking for Premise-Conclusions:

Here we have two Premises (in red) and two Conclusions (in green). Note that in this particular case we could've chosen them separately, but it doesn't really matter; we can easily remove the non-red green elements:

At this point we could just write 7 in the F cell, but just to be completist I'll point out that the sledgehammer also can draw an "obvious" conclusion that once we know a 7 goes in F, nothing else can go in there:

Okay. Now it's time for a medium-level heuristic:

This heuristic is called Pointing Pairs by some. It goes: Look at the right Region. Because of the 2 in A and the 2 in E, we know that the 2 can't go in C, F, or G, so that means the 2 must be in B or D. That means that the 2 in that column is in B or D, so a 2 cannot be in H, L, or N in the lower-right Region. Also, because of the 2 in A and the 2 in K, there cannot be a 2 in J, M, or P. Therefore, the 2 in the lower-right region must be in Q.

That's quite a mouthful. Let's look at the set diagram:

I'm not going to explain the sets this time; you should be able to figure them out for yourself. Here's a Sledgehammer coloring:

This allows us to eliminate C2, F2, G2, J2, L2, M2, and P2.

As an aside, it's worth pointing out that often after applying Sledgehammer for a while, you'll end up with identical sets:

Here the two purple loops are identical, and really don't need to be both drawn to clutter up our diagram. (If you ever read my source code that implements the Sledgehammer and wonder what the "Enslave" function is supposed to do... now you know.)

After cleaning up our diagram it's pretty easy to see another Sledgehammer application:

And after eliminating H2 and N2, we're done.

In the actual compeition, if you had paused time and looked at all three finalists' grids at the 5-minute mark, you would've seen this:

You see, at this point, we were all stuck! There's no obvious way as to how to proceed; certainly none of the medium-level heuristics were getting us anywhere. (Except for placing an 8 in cell U ... forgot that one when I was making the diagram.) Faced with possibly stiff competition and only 10 minutes left, each of us guessed; with the championship determined by the luckiest guesser.

Ah, but if only any of us had seen this set diagram:

Note here that to simplify the diagram a bit, I've removed the trivial Placements from the Cell Rule sets. for example, there's a set at top center with D6 and D9; properly, it should also have D1, D2, D3, D4, D5, D7, and D8, but since those digits can be eliminated from D by Row, Column, and Region Rules, I've not bothered to draw them in.

You may want to stop here and check the loops to make sure you understand each of them.

As it turns out, there are three advanced deductions you can make here:

The top one is known as an X-Wing: Since there's a 9 in D or Z (because of the column), and a 9 in H or CC (because of the column), you can deduce that there's no 9 in E, F, G, AA, or BB.

The middle one is known as an Hidden Pair: Since the 1 in the top Region can only go in C or F, and the 6 can only go in C or F, we can deduce that no other digits can go in C or F.

The bottom one is known as Naked Pair: Since cell A can only be 2 or 6, and cell V can only be 2 or 6, we can eliminate 2 and 6 from all the other cells in the column.

You may be a bit surprised to see that these three rules, while all very different in the Sudoku grid, look amazingly similar in the set diagram. That illustrates the main power of the Sledgehammer theory -- that it shows that most of these heuristics are actually the same once you realize the symmetric relationships between the different constraints.

Anyway, let's apply the Sledgehammer, eliminate some Placements, and look for some more applicable Premise-Conclusion groups:

These three are much simpler to explain. They're all Pointing Pairs.

Note that the fewer loops are involved, the simpler the heuristic tends to be to explain. Anyway, eliminating another round leads to:

Up to now, we haven't been able to reduce any loop down to just one element, so we haven't been able to write anything in. But here, finally, we have a complex three-ring Premise-Conclusion group (a Naked Triple), allowing us to eliminate the B4 Placement and finally prove that cell K must contain a 4!

After that, the rest of the puzzle should be easy, so I won't solve it here. (Well, you may want to take a note that during that complex process we also eliminated AA6 and AA9.)


I hope this gives a much better feel for how the Sledgehammer concept works. Please drop me an e-mail (onigame at gmail.com) if you have any questions, suggestions, ideas for making it easier, etc.

One more thing worth mentioning: Although almost all known Sudoku heuristics can be stated as a Sledgehammer situation, and Sledgehammer heuristics can solve almost all Sudoku puzzles, not all of them can be. Usually those that cannot are those that are meant when solvers talk about "puzzles that require guessing" or "puzzles that cannot be solved by logic alone. I hope to explore those sorts of situations in a later blog entry.

Good luck, and have fun!

Link22 comments|Leave a comment

navigation
[ viewing | March 20th, 2006 ]
[ go | Previous Day|Next Day ]