Monday, May 12, 2008

Solving a Difficult Sudoku: The "Group Cut" Method

It's been a year since I posted a new method for solving sudoku puzzles. Maybe it's just me but the hardest puzzles seem to have gotten a lot harder over the past year or two and some friends have agreed. Over the past six months I've come up with another method to retaliate: the "Group Cut". Being able to solve the hardest sudoku inside 10 minutes, I decided to make things more difficult and stopped writing helper numbers in unknown squares. That led to my discovery of this method which I use on around a quarter of all sudokus I solve these days.

Thanks to a three-day weekend (today's Pfingsten, dontchaknow) and having gotten many other things out of the way I was able to put in the necessary time to make the graphics and write this up, ensuring the method was necessary for solving the puzzle rather than just useful due to oversight.

This method is a more holistic approach but it has nothing to do with newage stupidities like crystals, perfumes and furniture arrangement. Rather, I'm using the word "holistic" in its dictionary sense: approaching the puzzle as a whole rather than as a series of discrete digits. Read on and see what I mean. I promise that there's nothing about "chakras", "chi", "energies" or any such similar nonsense.

As in previous explanations, I order each block of nine squares with a letter and each individual sqaure in the block with a number:



You can play along by grabbing yourself a copy of this puzzle from websudoku.com, a site I'm happy to plug because they allow unlimited free access and keep things simple. This time we're going to use Evil Puzzle 9,725,408,088:



The first thing we do is run through the rows & columns to pick off the easy prey:



That's seven boxes out of the way. A second round of row & column scanning from 1-9 places a 1 in H2 (G5 & B6 block the other possibilities) as well as in A9. The 1 at G5 and the blocked right column of block D mean that the 1 must be in the right column of A1, This then places the 1 in C1.



It's time to do a little deduction. We still have no 2s but the 3s in G8 and H5 force a 3 in J1 or J3. Now using the Double Pairs technique we see in block C there are also only possibilities in the outer columns so a 3 must appear in the middle column of block F. Due to D6 it can only be in F8.





That, in turn, places a 3 in E2.



The 6s in B1 and C5 along with the 1 in A9 force A7 to be a 6 and that's where everything comes to a grinding halt.



You have two choices: 1) Fill in every box with a load of candidates and try to fish out some pairs and triplets...



OR, 2) employ "Group Cut".



In this case the 4-6-9 in the sixth row and fourth column combine to leave only thee possible spaces in block E. These can then only be 4, 6 and 9.





The remaining numbers are 1, 2, 5, 7 and 8, and only the 7 isn't cancelled out in 6th column.



A look at the remaining two squares in this column show that the top can only be 4 or 9, tripling with the 4-6-8 we already have in E3 & E6, so H3 must be a 5 which means H5 is a 6.



Once this 6 is in place G7 has to be a 6.



From here on out it's a simple matter of elimination. Check the row, column and box of the number you just filled in and unless another group cut is necessary (possible), everything should fall into place relatively quickly.

We just added a 6 in box G and only 2, 5 and 9 are available. A 5 in H3 covers the top row of box G so G6 has to be a 5, putting a 2 in A6 and completing that column.



With the 2 filled in A6, only A2 and 5 are unfilled and the 5 in C3 determines which is which.



That leaves 2 & 4 in the top row in B2 & 3. B3 has to be the 4 and so B2 is 2.



The 4 in the sixth column determines the 4-6-9 in block E.



And so on. The puzzle is effectively done.

Here's another example if this first one wasn't clear enough, this time with evil-level puzzle 8601687531.



This time, Group Cut can be employed even before the first rounds of row and column scanning.



There are only five open squares in block D and the 2, 5 and 4 in the left column of block A cancel out two of them, leaving three. These must then be 2, 5 and 4.



The only possible numbers left for block D are 1 and 8 which already have complements in block F.



With the 1 and 8 in place, Column 1 is complete in blocks A and D, leaving only a 3, 6 and 7 available for the left column of block G. Since there are 3s in both blocks H and J, G4 must be a 3.



There are also 4s in blocks H and J which force a 4 into square G5.



So without having even scanned the rows and columns for single digits 1-9 we already have some numbers filled in.



And we can use Group Cut again because the right-most row of block J does the same thing as before to block F, placing the 3, 7 and 4.



And that's about it. If this is still unclear, add a comment.

Labels:

1 Comments:

Anonymous Anonymous pulled out a crayon and scribbled:

This is awesome. I have Sudoku installed on my phone (Treo 680) and I play it often when I'm bored. I'm not even close to reading the whole post but I can already tell this will make the game a lot more interesting. Thanks. BTW, I've been a long time reader ... your stories are great.

20 May, 2008 16:27  

Post a Comment

<< 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.