Solving Sudoku

a work in progress

One step beyond...

I’m assuming that you understand the basics of Sudoku and can dice ‘n slice a puzzle looking for rows/columns with given numbers than lock out options in other cells. This is a great start but many puzzles need stronger tools to unlock so, in increasing complexity, let’s look at a few other techniques. The first thing you need to do is write in mini option options: I recommend using a formal shape for these options so that you can “see” a shape forming as you reduce options. These graphics provide that but you might prefer a layout that doesn't place the 5 in the middle. A definition to start with: so we are on the same wavelength, I shall define the cell R1C1 as the cell in row 1 counting down and cell 1 counting from left to right, ie top left. As so on.

Index

Locked Options
Naked Pairs
Hidden Pairs
X-Wings
XY-Wing
XYZ-Wing
XY chain
Colours
3D Medusa
Swordfish
Unique Rectangles
Nice Loops
Aligned Pair Exclusions
Alternating Interference Chains
Jigsaw - Law of Leftovers
Killer
Software

Locked Options 1

Often a number option within a box is restricted to one row or column. Since one of these cells must contain that particular option, the option can safely be excluded from the remaining cells in that row or column outside of the box. Here we see 5's locked in R8C9 and R9C9 thus 5 cannot be in R4C9, R5C9 and R6C9:

Locked Options 2

Often a number option within a row or column is restricted to one 3x3 box. Since one of these cells must contain that specific option, the option can safely be removed from the remaining cells in the 3x3 box. Here we see 8's locked in R7C2 and R9C2 thus R9C1 cannot be an 8:

Naked Pairs

If two cells in a group - that can be a row, column or box, contain an identical pair of options and only those two options, then no other cells in that group could be those values. Thus those 2 number options can be removed from other cells in the group. In the example below:

Naked Triplet and Naked Quads

I have yet to see a naked quad. The same idea that applies to Naked Pairs applies to Naked Triplet and Naked Quads. A Naked Triplet occurs when three cells in a group contain no number options other that the same three numbers. But the cells which make up a Naked Triplet don't have to contain every option of that triplet. If these number options are found in other cells in the group they can be removed. In the example in row 1, we have 1, 4 and 8 locked in the green cells. Thus these number options can be removed from the pink cells:

and another example:

A Naked Quad occurs when four cells in a group contain no options other that the same four options.

Hidden Pairs and Triplets

These are harder too spot that naked pairs/triplets as you have to see past the other mini number options that hide the pair/triplet. If two cells in a group contain an identical pair of number options and no other cells in that group contain those 2 options, then other number options in those two cells can be removed. In this example, 3 and 6 only exist in R6C7 and R6C8 so none of the other numbers (1, 4 & 5) can be in those cells and can be removed.

If three number options are restricted to three cells in a given group, then all other options in those three cells can be removed. Therefore, all other options can be excluded from those three cells. I'll include an example as soon as I find a good one. Hidden triplets are usually very hard to spot but then again they're not often needed to solve a puzzle.

Hidden Quads

Again if four number options are restricted to four cells in a given group, then all other options in those four cells can be removed. I’ve yet to see a Hidden Quads, which is good news since I imagine they are nearly impossible to spot.

X-Wing

Now we are heading into more esoteric territory; let’s start with the X-wing. Firstly, these names are somewhat whimsical; this is the easiest to visualise. The X-Wing requires 2 rows (or 2 columns) containing just 2 cells with a single number option in each row, and these number options must share the same 2 columns forming a rectangular cross - hence the name X-Wing. Equally, 2 columns with just 2 cells containing this number option in each column sharing 2 rows also form an X-Wing. These 4 cells are the only possible cells for the correct number options in these 2 rows/ columns. Think about it: if the correct option is top left, it can’t then be top right or bottom left, so must also be bottom right and vice versa. If you are working with a row with just 2 number options, any number options in the column outside the X-Wing can safely be removed. Let’s look at this:

The bright green cells form the X-Wing since rows 3 and 4 both have only two cells with number option 8's and they form a rectangle (ie sharing columns 1 and 9). Note: green cells represent the 'true/false' options. Thus, other option 8's in columns 1 and 9 (highlighted pink) can safely be removed as these columns contain green 'corner' cell. Consider if R3C1 is an 8, R3C9 and R3C4 are not, so R4C9 must also be an 8. And vice versa. So, no other cell option in column 1 or 9 could be an 8.

Finned X-Wing

This section is tricky so you might wish to skip it until you may mastered some of the techniques below. It's not too hard to follow the logic using the Pattern Overlay Method but I don't intend to try to explain it here so search the web. If you can form an X-Wing by ignoring the finned cells, then you may eliminate any other cells in the finned X-Wing box aligned with the X-Wing other than the fins. I'll post an example when I find a good one!

You can extend this logic to the Sashimi which is an X-Wing with a missing corner cell.

XY Wing

Now let’s look at the XY wing. Unfortunately this is not really an extension of the X-Wing (that’s a Swordfish) but an extension of the Triplet. Review the Triplet first. What we are going to do now, is take the Triplet out of a single row/column. We will “anchor” one pair of the Triplet in one group such as a single box or row/column; usually a box. Take a look at this:

XY Wings aren’t easy to spot. What we are looking at here are the green cells where 2, 4 and 7 are locked. As you can see 4/7 and 2/7 are also locked in one box. 4/7 becomes the root of this X-Y wing as the 2/4 in column 4 and 2/7 branch off it. Thus the 2 green cells with the 2 in them are branch cells. These 3 number options are bound to these 3 cells. Now comes the tricky part. Any other cell containing the branch cell number option (in this case 2) that can “see” both branch cells cannot contain a 2. This removes all 2 number options in pink cells. Why is R5C4 not removed? It can see the branch cell in R4 but not the one in R5. Similarly R8C1 and R6C3. This is actually a great example because the next move is also an X-Y wing. Can you see it?

XYZ Wing

This is the logical extension of the XY Wing. Three cells may contain only 3 different numbers between them, but which fall outside the confines of one row/column/box, with one of the cells (containing XYZ) being able to see the other two; those other two having only one number in common (XY, YZ). Since one of the three cells must contain the common number, any extraneous cell that sees all three cells of the XYZ triplet cannot contain that number. Delete than number option.

XY Chain

Again, a logical extension of the XY Wing. This time we are going to form a chain:

I think this is slightly counter-intuitive as the chain doesn't seem to close (the next example is more comfortable). It doesn't really matter where you start as long as you follow a chain of cells containing linked pairs. Here we start in R6C5 with 47 then follow the 7 in the chain to R4C5 then the 6 to R4C8 then the 9 to R2C8. Here we stop as the free number is now a 4; back where we started. The exploit here is to remove the 4, the common number, in any cell that can see the cells at both ends of the chain, in this case the 4 in R6C8. Here's another example that can be grasped on 2 levels. Firstly try chaining starting at R6C7 around the green cells:

Or view it as a lock-out ring. It doesn't really matter where you start; let's pick R6C5 5/2 and go anti-clockwise - 5/6, 6/1 then 1/2. Any number option interrupting this chain cannot contain the value embedded within the chain. Thus R6C6 cannot contain 1. Try it: if you place 1 in R6C6, you force R6C7 as 2, R6C5 as 5, R7C5 as 6 and now R7C6 has no options.

Colours

Next we are going to look at Colours. This is a technique working with locked pairs that “flows” around the grid. The technique is used to eliminate number options. There are 2 forms. Rather than explain it myself, I shall use an explanation sent to me by Ruud: <quote>Colouring is a pattern recognition technique.

A strong link exists when there are only 2 number options for a row, column or box. In the solution, one is true, one is false, but they cannot both be true or both be false.

Let's take this grid state and look at the number options for digit 5, coloured green. First identify all the strong links in this grid. I've drawn them here, and highlighted only those candidates that are part of one or more strong links.

There are 3 clusters (known as chains or strings) with unique paired links.

A cluster with only 2 or 3 nodes is useless unless you are multi-colouring. (Andy: I haven’t got to grips with this yet so you’ll have to wait for an explanation, guys!) So the cluster with 5 nodes, at top right, is the most promising one.

Start at any node and simply apply alternating colours - or you can use alternating A/Bs - to the nodes, giving this:

Now the blue colours indicate a conflict in the right hand column. This invalidates all blue nodes in the cluster, because either all blue nodes are correct, or all green nodes. Blue is not, so green is. Remove the blue candidates and continue. There is a second type of colouring.

The first type deals with inconsistencies within a cluster. The same colour appears twice in a row, column or box. The second type eliminates number options that can 'see' both colours of a chain.

Here is a number options grid which has a huge cluster of strongly linked options for digit 8:

I've already applied the blue and green colours. There is no need to make a choice from multiple clusters. Notice that 12 of the 21 "8" options are part of the cluster.

Now there is absolutely nothing wrong with this cluster. Every row, column or box contains at most 1 green and 1 blue cell.

Remember what we learned first about colour clusters. Either ALL green cells or ALL blue cells contain digit 8. There is no third option.

Therefore, any cell that can 'see' both a green and a blue cell cannot contain digit 8. This grid contains 4 such cells. I marked the target cells in pink.

If you were a computer solver, you would eliminate those candidates and check the grid for singles. But you're not. You are human. You can recognize patterns. You can see that a green cell is the only candidate left in box 3. This implies that the green candidates are true and the blue ones are not. This allows you to place an 8 in the 5 green cells.

This type of colouring is actually more common than type 1. The chains may not always be so huge and the yield so high, but colouring is a great technique.</quote> Original thread

3D Medusa

No, I didn't invent the name, I don't think there's anything 3D about it though I can see the nod to Medusa's hair. Here we are going to extend the ideas from both XY chains and Colours simultaneously. That might sound fairly horrid but work through this before you despair, it's not that bad.

First let me define my box colouring convention. Any locked pair will be alternately coloured green/blue. Thus a pair of 4s in any row will be coloured one green, one blue. A pair of numbers in a single cell, where the option must be one or the other, will be coloured one green, one blue. We will now start at 47 in R2C2 and work around. Ignore the red box at R3C1. With the 4 in R2C2 green and the 7 blue, we link to a blue 4 at R2C8 and a green 7 at R2C9. The 4 links to a locked 4 at R1C7 becoming green. The 7 at R2C9 links, in the cell, to a 2 becoming blue. The green 4 at R1C7 links down to a blue 4 at R9C7, then across to a green 4 at R8C1. The blue 2 at R2C9 links down to a green 2 at R8C9. The green 2 then links across to a blue 2 at R8C1 which links, in the cell, to a green 4.

So what? From an uncontroversial 47 start in R2C2, we have a position where we have forced two green 4s in box 7 at cells R8C1 and R9C1. There cannot be two 4s in any single box so ALL green 4s can be removed from the puzzle.

This includes the green 4 at R7C8 that I have yet to mention, which is a consequence of both the blue 4 at R9C7 and the green 2 at R8C9.

Swordfish

The Swordfish pattern is an extension on the "X-Wing" above; an X-Wing limited you to just 2 rows/columns. We will extend that to 3 rows/columns. While this technique is easy to “see” in an example, you will find it much harder to find in the wild. Quite honestly, I've yet to build the confidence to use it; tentacles seem to lie everywhere and it's not obvious which arm belongs to which body. Given a number option, a Swordfish pattern is formed by three rows each containing no more than three cells with the number option and all sharing the same three columns, thus you extend the 2x2 X-Wing with one more row/column. These cells form a grid of nine cells which are the only possible locations for correct number options. Any number options within the structure containing 3x3 grid (except the number option intersections themselves) can safely be removed. Obviously an extension of this to a 4x4 (or more) structure exists but I struggle to see the Swordfish so have yet to find a higher level grid. In the example below, consider the number options for 5:

Three columns (4, 5 & 8) have option 5 in no more than three cells (2 cells for the top row and 3 each for the other 2 rows), and these cells all share just 3 rows (one, four & nine); now we have a Swordfish. I’ve coloured these cells green. Other cells with option 5 within this structure (highlighted pink) can be removed. Note, as we see here, there does not have to be 3 cells in each row (or column), often there's only two.

Unique Rectangles

The basis of Unique Rectangles is that they contain what is sometimes referred to as a potential deadly pattern which sounds pretty serious but simply means that we are going to take advantage of the fact that ALL well built Sudoku puzzles have a unique solution. So any pair of candidates appearing in cells in just 2 columns, 2 rows and, critically, 2 boxes cannot be true as this option offers 2 non-unique solutions. There are 4 types of Unique Rectangles (and a couple of subsets). A Type 1 Unique Rectangle is illustrated below. The three cells marked in green contain 5/7. The fourth corner marked with a pink square also contains 5/7 and two other candidates. If the 3/6 were removed from that cell we would have a Deadly Pattern. This cannot be allowed to happen so it's safe to remove 5 and 7 from that cell.

The methodology is simple - once you get your head around the basic idea! Assume R5C6 is 5. That forces R5C4 to be 7, R2C6 to be 7, and R2C4 to be 5. This is where the term deadly pattern comes in; you can swap the 5's and 7's and the puzzle still solves. For the Sudoku to be valid, R5C6 cannot be 5. Assume R5C6 is a 7; same logic.

So R5C6 can't be a 5, and can't be a 7 - it must be either 3 or 6.

I'll look briefly at Type 2 puzzles to introduce the terms roof/floor and leave you to research the other types on-line. Simply the uppermost candidate cells are the roof cells, the lower candidate cells, the floor. Here we have an example with the green cell candidates as 2/9. You can see that an extra 8 exists in the roof cells as well as the the 2 blue cells immediately below the roof. Since from the Type 1 discussion, we know that 2/9 cannot be unique in the roof, otherwise the puzzle solution would not be unique, the 8 candidate must remain in the roof so cannot be a candidate in the blue cells immediately below the roof. Nor in the pink cell R2C3.

Type 3 URs use the fact that the roof contains usually 2 extra numbers, one in each cell, These 2 numbers also appear as a locked pair in their own cell separately aligned with the roof. Thus the logic says that to break the UR, either of the extra numbers must be retained thus forcing the other extra number in the locked cell. Therefore all other copies of that extra number can be removed from the roof line. Example to follow when I find one.....

Moving on to type 4; you will have noted that type 2 and 3 did not involve removing numbers from the roof cells. Type 4 does. Back in type 2 UR, we introduced the idea of roof/floor; now we need to exploit this. The 2/8 in row 9 below are classically locked. Crucially we also see 2 locked in row 6 with some 8s floating. Note that in box 5, the 2s can only occupy the pink cells, no other. Obviously one of those cells must be a 2. Logically if we were to retain the 8s, we would end up with the deadly pattern so we can remove 8s from the pink cells.

There is a type 4b UR where for the first time, the floor cells are not in the same box. So you can only look for the locked pair in their common row/column. Here's a great example of a type 4b but you will (probably) need Colours and a Swordfish before you get to the UR:

Finally Hidden Unique Rectangles. I think I like these the best! If any four UR cells contain a pair of base options and 3 of the cells contain other options as well, then one of the base options can be removed from the cell diagonally opposite to the cell with just 2 options if the other option form 2 strong links along both column and row. Thus option 1 can be removed from the pink cell below.

Nice Loops

I'm now going to cover a logical trick that to me seems to lie somewhere between Chains and Colours. Elsewhere this is variously called (Dis)continuous (alternate) nice loops and X-cycles. My wife calls these Impossible Circles. Look at this:

What you see here looks like the start of a chain looking across row 8 and column 1 or maybe the use of colours with the pairings of 3s but doesn't really work. But we can use it by using a weak chain. Start with the 3s in row 8 - if R8C4 isn't a 3, R8C3 is. So R7C1 isn't a 3, so R3C1 is. So the pink square, R3C4 isn't. Equally if R8C4 is, obviously R3C4 isn't. This example follows Rule 3, see below. How do you find these? Usually having looked for Colours and Chains, you have a sense of where locked pairs lie in rows/columns. So if you have 2 otherwise independent locked pairs with an end in the same box, this could be your break.

There are 3 rules. Rule 1 states that where you have a continuous chain of linked pairs, all options outside the chain that lie within the unit (box/column/row) of the links with weak inference, may be removed. Rule 2 states that for a discontinuous chain (one that does not comprise solely strongly linked options), where two links are strong inference pairs, an option can be defined at the cell where they meet. Rule 3 states for a discontinuous chain, where two links are weak inference pairs, an option can be removed from the cell where they meet.

Let's look at a couple more examples from a single puzzle. The first exploit here is the harder one but logically I will put it first; you might be better off jumping to the second then reverting. The first example loops around locked pairs of 3 from R7 C4 > R7C1 a weak link to R5C1 > R5C5 > R4C6 > R3C6 > R3C7 > R2C7 a weak link to R2C4. The test point is the weak link that joins 2 strong links at R2C4:

Things now get easier with row 5 & 7 in play and a weak link at R6C4.

Here's a neat puzzle with a few examples:

Now we can extend this idea to grouped X cycles. Take a look at this:

I think this technique is hard to spot but using this puzzle, we'll reach a harder one. Note that 8 is a locked pair in column 1 and row E. Consider what happens at the intersection; if you like a potential X-wing at/around A5 (R1C5). If R1C1=8 (blue) then R5C1≠8 (pink) and R1C4-6≠8 (pink) so R2C5=8 (yellow). Yet if R1C1=8 then R1C5≠8 ergo R5C5=8. But R2C5 was already an 8. So R1C1≠8. Cool technique but hard to see.

Aligned Pair Exclusions

To me, these seem to be an extension of the XY or XYZ concept, though a tad harder to spot. The trick is to find a group of cells that contain the same number of value options. In the example below, in box 7 at R7C3, R9C2 and R9C3 and Box 9 at R7C9 we have 4 cells that contain just 3, 7, 8, 9 (green):

The trick here is to understand the effect that will have on any cell that can see all 4 cells which, here, is limited to R7C1 (pink). Simplistically test the values in R7C3 and their effect on our pink cell. It fast becomes obvious that these 4 linked cells exclude 8 from the pink cell.

Another example:

This is a cracking example though how much use this is as a technique, I'm not sure about as (for me) it involves too much pencil work. Consider the possible options, and interactions, of the green and blue cells. The green cells of the option pairing of 22, 23, 82 and 83. Clearly 22 is not viable. If the options of either 82 or 83 is taken, pink cell R2C1 cannot contain an 8. If the green cells are 23, then R3C1 is just 79. Now consider the blue cells: vertically, we have 78, 79, 86, 69 - a perfect locked set! In this case, pink cell R2C1 cannot be an 8. Hence whatever the outcome of the aligned green pair of cells, the pink cell cannot be an 8 which nicely yields as 25 pair in column 1.

I know there's way more to APEs but I have only really just got to grips with this little. Perhaps these are easier to see than Nice Loops - not sure?

Alternating Interference Chains

Technically pretty much anything up from X-wings, XY wings, chains, etc are subsets of AIC. OK, that doesn't help? But now we need to look at AIC in their involved sense. An AIC is basically a combo of the chain concept 34-49-91-15-53 (and similar) and locked pairs. What we are going to do is interleave the 2 methods. This may hurt:

We start at R3C3 (green) with 46 or more specifically 6, move down one, as per a chain to 65 (pink) then shift mode to a locked 5 pair across to R4C9 (blue) then again on locked 5 pairs through R1C9 (pink) to R3C7 (blue, highlighted). Obvious, eh? OK, now we step across to the 6 out of the 569 combo (blue, highlighted) so that we can link back to R3C3 (green). And then? Consider the weak link: has to be the 569 cell. What if R3C7 were a 6? Then R3C3=4. The 6 forces R1C9=5 which forces R4C9≠5 which forces R4C3=5 yet given R3C7 is already a 6, there is no 6 in column 3. So R3C7 cannot be a 6. Cool, eh?

OK, move ahead with that puzzle, where does it get you? Here:

Great! Even with this highlighted, I think it's a bit of a mystery. Start at R1C2 with 1 (yellow, along with 1368) then step as a locked pair to R1C1≈1 (pink). Easy. Now weak link to the R1C1≈5 (pink) then across to the locked R1C9≈5. Time to get weird; drop down through a weak link to R4C9≈5, then across the locked link to R4C3≈5 (orange) then the chained link in the same cell to 6, then one left to the locked 6 in R4C2 (green). Tired yet? Now we head back up to the locked 6 link at R1C2 (yellow). So what? How do we look at this? Again consider the weak link: R1C2=1368. If R1C2=1, life indeterminate. If R1C2=6, then R1C1=1, R1C9=5, R4C9≠5, R4C3=5, so R4C2=6 but that's where we started with a 6 at R1C2 thus yielding two 6s in column 2. Thus R1C2≠6.

Let's try another example of an AIC:

First, yes, I know the 1 at R3C2 and 5 at R7C1 come out easily but it makes no difference. Moving on to the AIC; what we are looking for it locked pairs, whether these are a locked pair of numbers on a line/column or an either/or pair in a single cell. Starting at R9C1 with the 9, we move across the row to the 9 at R9C6 which links to a collocated 8. That 8 links to a locked pair at R8C6 then again across to an 8 in R8C7 then up to an 8 at R2C7. We then switch to a collocated 4 in R2C7 then drop to a locked 4 pair at R3C7. Finally across to a further locked 4 pair at R3C3 which, in turn, links with a collocated 9 at R3C3. Follow the logic around then chain and you will see that either R9C1 or R3C3 is a 9 so the 9 in the pink R3C1 is removed.

A test

For those of you who feel that you've cracked X and XY wings, here's a little test: