A Day in the Life
By ReallyEvilCanine (Mon May 12, 2008 at 02:58:34 AM EST) A Day in the Life, WTF, sudoku, pie (all tags)
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.

Includes 29 graphics totaling 211KB

x-posted to da brog.

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.

A Day in the Life | 8 comments (8 topical, 0 hidden)
Simple elimination by sasquatchan (2.00 / 0) #1 Mon May 12, 2008 at 05:01:25 AM EST
or what you call row/column or easy scan elimination shouldn't yield anything on a hard puzzle.

I wrote several variations/algorithms of a program to solve sudoku puzzles (thanks to Project Euler, that someone linked to a long time ago, I quit at around 32% genius, not quite good enough at some of those mathy questions).

One of my variations did solely simple elimination, and I found from feeding it 1 star (easy) that all easy puzzles can be solved with simple elimination.

If I fed it 5 star, I didn't get a single number -- no elimination was possible.

So different rankings mean different things to different puzzlers, but I firmly believe a true hard puzzle gives you no easy numbers/low hanging fruit.

All sudoku puzzles are elimination by ReallyEvilCanine (2.00 / 0) #2 Mon May 12, 2008 at 07:18:33 AM EST
But this isn't simple elimination in that more than one number at a time is being evaluated. A "simple elimination" is the 9 in C8 due to the the 9s in F7 and J6. I've seen no method discussed which evaluates multiple concurrent possibilities.

I don't claim to be the first and only person to have noticed this but I haven't seen anyone describe it just as I never saw anyone describe my "Uniqueness" strategy. Shortly after posting that method I was sent a link to some buried Times article which I'd never seen and which was similar but not as clearly described. I also initially sent off my "discovery" to a sudoku site months before that article appeared.

the internet: amplifier of stupidity -- discordia

[ Parent ]
Here I was, interested . . . by slozo (2.50 / 2) #4 Mon May 12, 2008 at 10:08:35 AM EST
. . . thinking that you had some novel, mathematical key to solving . . . but unfortunately I haven't seen any technique I haven't firgured out/used on my own. I'm a very (in my opinion) amateur Sudoku guy, and don't spend half the time on them as I do crosswords; the more difficult Sudokus I cannot finish at all.

Maybe it's because I get too bored with numbers then, who knows . . .

I'm not good enough by ReallyEvilCanine (4.00 / 1) #7 Tue May 13, 2008 at 06:33:03 AM EST
I think if there was some mathematical method which would place everything it would have been demonstrated by now. Making a sudoku isn't the same as the 8 queens placement; it's more "9 rooks of nine colours", exponentially more complex by rather many orders of magnitude. There are 92 possible solutions to the eight queens puzzle; there are more than 6.7e21 possible sudoku solutions; removing symmetry, rotation, reflection, etc. still leaves more than 5 billion possibilities, and that's just for the plain 9x9 version.

A sudoku puzzle must (by concensus) have a unique solution which doesn't have to be guessed at. Many people do employ guessing and back-tracking, and my strategies are attempts to do away with such inefficient nonsense. Guessing shouldn't be necessary in an exercise which itself is a demonstration of logic.

the internet: amplifier of stupidity -- discordia

[ Parent ]
Mmm, yeah, I guess . . . by slozo (2.00 / 0) #8 Tue May 13, 2008 at 06:48:26 AM EST
. . . I was just surprised that I had all the tools, but that it was still really that difficult for me (the harder puzzles).

I'm glad that you didn't take my comment in the wrong way, because I certainly didn't mean to make a negative commentary on your sudoku knowledge - rather, I am just a little shocked that that was all there was to solving them. Shit, I can't say I would've had the patience to write that diary, that's for sure . . .

[ Parent ]
Bragging Rights by ReallyEvilCanine (4.00 / 1) #9 Tue May 13, 2008 at 07:32:03 AM EST
I've come up with two original techniques. Yay me. These fuckers are a bitch to write not because I have to solve a bajillion puzzles to find really good examples, but because I then have to solve them each two or three times, make sure I'm not overlooking something which could've been found by a simpler, pre-existing technique (which happened the first time I tried to write up Group Cut), and only then create all the graphics. The write-up itself is easy and with FireFerret, so is uploading the GIFs.

That's really all there is to solving the damned puzzles: some logic, although with some of the really difficult puzzles like the weekly "mind-bending" Killer Sudoku they have at killersudokuonline.com, it's seriously contorted logic. I haven't solved one of those fuckers yet.

the internet: amplifier of stupidity -- discordia

[ Parent ]
Hmm by Slightly Foxed (2.00 / 0) #5 Tue May 13, 2008 at 02:41:18 AM EST
At the point in the first puzzle when you are using Group Cut, you say "The remaining numbers are 1, 2, 5, 7 and 8, and only the 7 isn't cancelled out in 6th column." I don't see that it is clear that the 5 is cancelled out at this stage.

7s in B4 and H8, only leaving E9 open by ReallyEvilCanine (2.00 / 0) #6 Tue May 13, 2008 at 03:07:56 AM EST
I don't see any certain placement of a 5 at that stage either.

the internet: amplifier of stupidity -- discordia

[ Parent ]
A Day in the Life | 8 comments (8 topical, 0 hidden)