Friday, May 18, 2007

Solving Greater Than Sudoku Puzzles

I'm in a surprisingly good mood. Not only has the the idiocy:competency ratio been fairly low this past week, I've resolved a couple difficult problems. Then there's Citrix, and even that front is looking up. Best of all, I'm on a four-day weekend. Unfortunately once I post this there's work on the doghouse to be done involving hammers, drills, anchors and heavy, unwieldy objects.

EDIT: Sorry about the crappy formatting. Blogger, dontchaknow. It looks good in Preview but dies in Firefox in actual display. I'll see if I can't make it look nicer.

Ever since my post about solving difficult sudoku puzzles with my uniqueness method sudoku searches in the the referrer logs have jumped considerably and are about 20% of all hits now, many of them looking for help solving "greater than sudoku" puzzles. I couldn't find any help myself when I first tackled them but I've gotten pretty good. Here now a primer for solving "greater than sudoku" puzzles.

If you want to play along, the puzzle which will be solved is Greater Than #374, a medium level puzzle from Killer Sudokuo Oline. Go print it out. I'll wait.

Warning: this entry is long and contains around a meg of ~20KB GIFs

Note the key for referring to blocks and numbers:





















Greater Than Sudoku Puzzle #374

















Greater Than sudoku puzzles only show the relation between the numbers. Therefore the only way to begin solving them is to start with the limits, 1 and 9.



Here we start by looking for the 1s which have to be the lowest boxes. In the block A we have two candidate squares 2 and 7 which are smaller than all their neighbours.


















Working our way down the column we find three candidates in the block D and only one in block G.















Every square except 5 in block G is larger than something else so there's one possible square which can have a value of 1: G5.
















With this 1 in place, the rules of sudoku say that no other square in this one's row or column can have the same value.
















The 1 in G5 negates the candidate 1 in square A2, leaving only A7 to hold a 1 for that block

















The known 1 in square A7 means that the candidate in D4 must be invalid since they share a row. that leaves D3 as the 1. Moving on to the middle column, we mark all possible candidates for the 1 again.














With only 1 candidate in block B (B4), we take out the two candidates in that fourth column, and D3 negates another candidate in the fourth row, leaving only 1 possible position for both block B and E. Block F still has two remaining.














We'll leave those two blocks and move on.


















Sudoku rules force the 1 in block C to be in the top row and only C2 is smaller than any other cell in that row. Likewise, only the bottom row of block F can contain a 1 and the smallest square there is F9.














These 1s in blocks C and F force the 1 to be in the left column of block J, and the 1 in G5 means it can only be the upper or lower square, just as in block H















Since only one of those squares in J was smaller than all others, J7 it is, forcing block H to H3.

















Right. The 1s are done. Now for the 9s. For no particular reason I'll mark the candidates across the top row. The 9s ,ust by definition have the largest value. If any square is larger than a candidate, that candidate can't be a 9.

There are only two candidates in block A, both along the top. These negate the candidates in B3 and C3, leaving only one possible choice in each.















Working down the left column we get stuck with D2 and D7 matching G2 and G7. Not much help.

















In the middle column we have three potential candidates but B5 negates candidate E8, leaving only E4 and E6. Continuing to check, mark candidates and remove them based on sudoku rules, we're left with only one candidate 9 in each block.














So we fill them in.


















Now it's time to do either 2s or 8s. Since all the 1s and 9s are filled in, it doesn't matter much which one we go after first. However, 2 is more absolute than 8 since it can only be larger than 1 and is therefore the smallest number to deal with, whereas 8 tends to be more ambiguous, being smaller than 9 but larger than everything else.












In block A it looks like there are three candidates for the next smallest number, A2, A4 and A8. However, while A4 is smaller than all surrounding squares other than 1, A8 is larger than A5. Since 2 can't be larger than anything else, A8 is nixed.













We see the same thing in block D that we saw in block A: D6 has to be larger than something other than 1 so it's disqualified as a 2.
















Since there are only two complimentary candidates in blocks A and D, only the right row of block G can contain a 2 and it has to be the smallest one, G6.















Working through the same strategy we mark all the possible candidate 2s across the board.

















We can remove some of these easily. Only the left column of block B contains the possible candidates so E7 is cancelled, leaving candidates only in its right column. This forces out candidate H9 leaving only H2. That, in turn, negates J2 leaving J8.













Up top we have complementary candidates in blocks B and C. Since there's no 2 in the middle row of either of these blocks, there must be one in block A.















Once we have A4, all the rest of the wrong candidates can be weeded out. It's time to go to town on the 8s.
















Working through all the boxes with the same strategies of complementary candidates, we find all the 8s easily.
















The 3s aren't quite as easy,


















We're in luck: block J only has one candidate: J2. This allows us to wipe out most of the other candidates.
















A couple people I showed this to were stuck here. It can be easy to overlook the fact that in block E only the bottom row has candidates, negating D9. That makes D4 a 3 and negates G4, forcing G9, which then forces H4 and finally E9.














Next up: 7s. Seeing a pattern here?


















Sevens are now the largest number we can have. Nothing (except the already-positioned) 8s and 9s can be greater than it. The top row has only one candidate in block C which then gives us blocks A and B.














Same-old, same-old. Block G was the key with the 7 in G1, negating D1 and forcing D5, and so on.
















7s done. Now it gets a bit tricky. The remaining cells can only be 4, 5 or 6.

















As we start filling in 4/5/6 in each cell, the relationships come into play. In block A, A1 could be any of the three since even 4 is greater than both 3 and 1. Squares A5 and A8 are directly related; one of them must be greater than the other. Therefore A5 can only be 4 or 5 since we have nothing greater than a 6 to fill in that square, and A8 can't be a 4 since it would have to be greater than a number other than 1, 2 or 3.


This is the same reasoning that reduced the possibilities in block B. Block C is special. One of the three candidate squares must be greater than both the others. It can only be a 6.




That leaves only 4 and 5 as possible values both within that block and also in that column.

















Since there are only two candidate squares for a 6 remaining in block J and they have a relationship, we know where the 6 has to go.
















Standard sudoku rules say that since we now have the complementary pair of 4/5 in J1 and J3, that row can't have either of those numbers elsewhere.















G3 is a 6.


















This blocks out the right column of block D.


















D1 is a 6.


















Since there's a 6 nailed down in the leftmost column, the 6 in A1 is void.

















Same standard progression. Only A8 can be a 6 so B9 can't be, forcing B2. Since no more dominoes will fall at this point, we need to look where the rest of the 6s could be placed.















The 6 in D1 takes out the top row for the middle row of blocks, leaving only two candidates in block F with a clear relationship. The rest of the 6s can now be placed.















The rest of the 6s are placed and there's only 4 and 5 to contend with. In almost every block they're dissociated, except in D where they have a relationship.















That greater than sign forces the 5 into D6 and the 4 into D9.

















Now that we've got one 4 and 5, the rest should fall into place.


















Finito.















That's pretty much how all the "Greater Than" sudokus work. At higher levels there are more open candidates, and techniques learned from normal, extremely difficult sudokus (like uniqueness) are required, but that's it in a nutshell. This was a "Moderate" puzzle. If there's a demand I can do this for a difficult one, minus a lot of the baby steps.


Graphics done with paint.net which was only mildly infuriating at times.
Preparing this for blogger with the tiny edit window was the real pain.

Labels:

5 Comments:

Blogger AAhelp pulled out a crayon and scribbled:

I'm started to get pretty hooked with this. You're worse than a drug dealer sometimes.

19 May, 2007 08:40  
Blogger armando pulled out a crayon and scribbled:

This comment has been removed by a blog administrator.

26 June, 2007 00:37  
Blogger Davo pulled out a crayon and scribbled:

Hi!, I choose to make a Greater Than Sudoku Game for computers (with solver, gaming and everything), for a School Proyect. And I was wondering if you know a way of making random maps, so that the solution its unique. It would help a lot. Thanks!!

12 November, 2009 05:17  
Blogger Russ Williams pulled out a crayon and scribbled:

Good tutorial! One thing was bizarre though:

>> Since all the 1s and 9s are filled in, it doesn't matter much which one we go after first. However, 2 is more absolute than 8 since it can only be larger than 1 and is therefore the smallest number to deal with, whereas 8 tends to be more ambiguous, being smaller than 9 but larger than everything else.

I'm confused whether that's a joke or you're serious with this "absolute/ambigous" concept... of course the situation with 2 and 8 is symmetrical: we can just as well say "8 is more absolute than 2 since it can only be smaller than 9 and is therefore the largest number to deal with, whereas 2 tends to be more ambiguous, being larger than 1 but smaller than everything else."

13 March, 2011 08:45  
Anonymous Anonymous pulled out a crayon and scribbled:

saw your blog, whats the tip to solving greater than sodoku with only one number clue filled but the greater than less tahn clues are incomplete and sometimes cross the 3x3 boundaries...

04 May, 2012 07:39  

Post a Comment

Links to this post:

Create a Link

<< Home

In compliance with $MegaCorp's general policies as well as my desire to
continue living under a roof and not the sky or a bus shelter, I add this:

DISCLAIMER:
The views expressed on this blog are my own and
do not necessarily reflect the views of $MegaCorp, even if every
single one of my cow-orkers who has discovered this blog agrees with me
and would also like to see the implementation of Root Cause: 17-Fuckwit.