You are viewing onigame

onigame - [entries|archive|friends|userinfo]
onigame

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

[Mar. 20th, 2006|01:24 am]
Previous Entry Share Next Entry
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!

LinkReply

Comments:
[User Picture]From: xsg
2006-03-21 06:22 am (UTC)

(Link)

I really enjoy your posts.

I still haven't figured out hypersets, however. Could you enlighten me, please.
From: north_lu
2006-03-21 12:03 pm (UTC)

May I introduce this artical in my blog??

(Link)

Nice, it explains so many skills with a single sledgehammer method. May I translate this article into Chinese, and copy this from here in my blog??(Of couse, I'll note the original....or, do you have Chinese version?? Because my English is very poor, it is anticipated that I'll make a lot of mistakes when translating this article.)

This is my blog website:
http://popblog.tvbs.com.tw/blog/puzzles/
[User Picture]From: onigame
2006-03-21 12:33 pm (UTC)

Re: May I introduce this artical in my blog??

(Link)

Sure! Let me know when you translate it and I can point out
any errors in translation.

By the way, my name is 黃煒華, not 黃維華.
From: north_lu
2006-03-21 09:05 pm (UTC)

Re: May I introduce this artical in my blog??

(Link)

Sorry....
The name I copied from 蘋果日報...
and I forgot to note it's just a temporarily traslative name in that newspaper.

And thank you, I'll try my best to translate ....
[User Picture]From: motris
2006-03-22 09:55 pm (UTC)

(Link)

Excellent post - while I was not completely clear on the Sledgehammer from your earlier entry, your diagrams here make it much more obvious what is going on as you 'hammer your way through a sudoku. Indeed, it is exciting to me to see that the "X-Wing" is really just the same kind of basic "sledgehammer" logic as a hidden/naked pair as, in my solving (and as I discussed with you in Lucca), I have never considered seeing an X-Wing too hard whereas seeing a Y-wing is more challenging until you get used to looking for it.
[User Picture]From: okelay
2006-05-01 11:00 pm (UTC)

(Link)

i like sudoku, but that's just way too complicated
i'd rather use the old fashioned way. simply check which numbers are missin g and which you haven't used.
From: (Anonymous)
2006-12-14 06:58 am (UTC)

I agree

(Link)

I mean, it's obvious that you put a lot of work into this theorem, but by the time I made sense of the material I'd be bored of playing Sudoku.
From: louisebysir
2008-07-11 09:13 pm (UTC)

(Link)

That's the master list, all right, but it's too unwieldy when you just want to call your spouse, your boss, or your lawyer.
From: debbielutyq
2008-07-16 10:40 pm (UTC)

(Link)

That's the master list, all right, but it's too unwieldy when you just want to call your spouse, your boss, or your lawyer.
[User Picture]From: ciphergoth
2006-05-13 11:07 am (UTC)

(Link)

This is very neat. How does your software search for suitable sets of loops meeting the constraints which define when Sledgehammer is applicable? Thanks!
[User Picture]From: nemomori
2006-06-13 04:41 pm (UTC)

Application in mental deduction

(Link)

Amazing article (I was linked to it by my girlfriend.)

However, I have to question how feasible it is for mental deduction of Sudoku puzzles. It would seem that the tremendous amount of comparative sets one would have to hold in ones mind would make it a very ardous task. Do you find yourself actually using this technique when attempting to solve the puzzles without scratch paper?
From: (Anonymous)
2006-06-17 07:02 pm (UTC)

hello

(Link)

Wow! Cool design! Webmaster respect!
From: (Anonymous)
2006-07-05 07:31 pm (UTC)

Sudoku Conditions

(Link)

The diagrams are nice, but I can visualize the sledgehammer better with sets. It is the reduction contitions that I'm curious about. I've come up with 4 that I'll post here, but I'm sure they are not complete. Is there a complete set of conditions for solving Sudoku's (No guessing)? or Are there puzzles that require guessing? How would someone argue that guessing is required?

The conditions I use, which are primarily generalizations of things found in your nice article:

Every cell has a set of available numbers. If a cell contains a “given number” then its available set is the set containing the “given number”. A “unit” is a row, column, or one of the 9 special squares (called boxes below). If a cell does not contain a “given number”, then its initial available set is the subset of {1, …, 9} which are not “given numbers” in any of the 3 units containing that cell. There are at least four conditions which allow numbers to be removed from an available set:
• If a number n is contained only in the available sets A1, …, Ak of unit U and these sets are also available sets of unit V, then n can be removed from all other available sets of unit V. If k = 1, then A1 can be set to {n}.
• Transversal Condition: If a number n is contained in at most k available sets within each of k nonintersecting units (rows/columns/boxes), and all of these available sets are contained in k other nonintersecting units (rows/columns/boxes), then n can be removed from every other available set in these units.
• Pigeon Hole Condition: If A1, …, Ak are available sets of a given unit containing exactly k different numbers, then these numbers can be removed from the other available sets in that unit. If k=1, then this number is the entry for the cell corresponding to that available set.
• Odd-Path Condition: Let n be fixed and consider the graph that has the available sets as vertices and two available sets are adjacent if, within some unit, n is contained in only these two available sets. If there is an odd path joining available sets contained in the same unit, then n can be removed from all the other available sets of that unit.
From: indymag1
2006-08-10 09:48 pm (UTC)

Summary of Analysis

(Link)

Going through this I felt the need to go back and say to myself, how would I come to the conclusion of knowing that 4 is in cell K if I were just trying to solve the puzzle without getting into set theory. Here are the steps:

1) 1 and 6 are a hidden pair in C, F -->
2) In the same region, 2 is in L or N -->
3) Via L-N pointing pair, in the first region 2 is in A or B.

4) A and V can both only be 2 or 6 -->
5) Via naked pair for the column, T cannot be 6 -->
6) For the T Region, 6 must be R, S (or U if the 8 is left out)
7) Via R-S pointing pair, in the first region 6 is in A or D

8) Using step 1, in the second region 9 is in L,M -->
9) Via L-M pointing pair, 9 is not in K
10) Via X Wing, 9 is in D or H -->
11) 9 is not in E
12) Via step 9 and step 11, 9 is in D or B.

13) Via steps 3, 7, and 12 the numbers 2,6,9 form a hidden triple for cells A, B, D (no other numbers can go into those cells) -->
14) 4 must go into K since A,B,D,E,J are not available.


[User Picture]From: onigame
2006-08-11 12:14 am (UTC)

Re: Summary of Analysis

(Link)

That's right. But in your system, you need to know the terms "pointing pair", "naked pair", and "X-Wing" -- but in the set-theoretic approach, all three of those are the same technique.
From: indymag1
2006-08-11 12:20 am (UTC)

Re: Summary of Analysis

(Link)

lol. I didn't know those terms either. I just learned them from your entry.

Terrific analysis.
From: (Anonymous)
2007-02-03 06:03 pm (UTC)

Interesting post

(Link)

Your article is very informative and helped me further.

Thanks, David
From: (Anonymous)
2008-01-14 02:31 pm (UTC)

Nice post

(Link)

Interesting article. it explains many skills with a single method.I am sure that with some practise and experience anybody can be an expert at the game. It can be a bit tricky and frustating at first but slowly everybody learns the ropes. I am trying to cover some aspects on web based sudoku which can be seen here

http://web-suduko.blogspot.com/
From: viktoriacipy
2008-03-17 02:58 am (UTC)

(Link)

Old message, but nice to reread it..
From: (Anonymous)
2008-08-23 06:30 pm (UTC)

Hello

(Link)

I'm new here, just wanted to say hello and introduce myself.
From: (Anonymous)
2008-09-23 01:46 am (UTC)

well done

(Link)

thank you, brother
From: (Anonymous)
2008-09-28 12:14 pm (UTC)

thank you

(Link)

nice work, dude