Sudoku

A Sudoku is a logic puzzle. The rules are simple. You have a 9 by 9 grid which is split into 9 equal sized boxes (3 by 3). In each row, column and box you have to write the numbers 1 to 9 (in any order). No mathematics is involved, so it is similar to a magic square puzzle but not the same.

You can't have the same number twice in a row, column or box. When the puzzles are created you are given some numbers to start with. Using these numbers you have to work out where the other numbers go.

For instance say I had a 2 in the top row of the grid and a 2 in the next box one row down. This means that the 2 can only go in the third box, along the bottom row.

It maybe easier to understand with a diagram:

I have a 2 in the top row and in the middle row. This means the 2 has to go where I've put the stars:

??2 | ?6? | ?89
?45 | ??2 | ?7?
?7? | ?56 | ***

Sudoku software can be found at www.sudoku.com. The software is sold by Pappocom (a one man software company run by Wayne Gould).

Sudoku puzzles can also be found in the Times Newspaper.

Note: There's a little mistake in the diagram. See if you can spot it.

Sudoko -- sometimes written Su Doko -- is the latest craze in newspaper puzzles in the UK. It was imported from Japan by The Times and quickly began to appear in most UK Newspapers. Of these, The Guardian claims its puzzles are superior since they are generated by hand and not, as they claim the others' are, by computer. Indeed, the Guardian's G2 suppliment on May 13, 2005 has a Su Doko puzzle on every on of its twenty pages.

The puzzles are simple in concept, but often very difficult to complete. They comprise a 9x9 grid organised as nine 3x3 grids with some of the squares containing a digit (1-9). The aim is to fill every square with a digit (1-9) such that each 3x3 grid, horizontal and vertical line contains each digit exactly once.

Let's have a look at an example starting grid:

-------------------------------------
|   :   :   | 9 :   : 8 |   :   :   |
|   :   : 4 |   :   :   | 6 :   :   |
|   : 9 :   |   : 3 :   |   : 7 :   |
-------------------------------------
| 9 :   :   | 2 :   : 4 |   :   : 6 |
|   :   : 1 |   :   :   | 5 :   :   |
| 3 :   :   | 8 :   : 6 |   :   : 2 |
-------------------------------------
|   : 6 :   |   : 7 :   |   : 3 :   |
|   :   : 8 |   :   :   | 2 :   :   |
|   :   :   | 1 :   : 5 |   :   :   |
-------------------------------------

Be aware, that they are not always -- in fact, not usually -- symmetrical like this. I chose this one because it looks nice.

The first square we can easily fill is the centre one. Initially any number could be in any square, so this square could contain any of these numbers:

1 2 3 4 5 6 7 8 9

It cannot be 2, 4, 6 or 8 since those numbers already exist in that 3x3 grid.

1 2 3 4 5 6 7 8 9

It cannot be 3 or 7 which already exist on that vertical line.

1 2 3 4 5 6 7 8 9

Finally, it cannot be 1 or 5, which already exist on that horizontal line.

1 2 3 4 5 6 7 8 9

The only number is 9, so we can safely enter that into that square on the grid.

-------------------------------------
|   :   :   | 9 :   : 8 |   :   :   |
|   :   : 4 |   :   :   | 6 :   :   |
|   : 9 :   |   : 3 :   |   : 7 :   |
-------------------------------------
| 9 :   :   | 2 :   : 4 |   :   : 6 |
|   :   : 1 |   : 9 :   | 5 :   :   |
| 3 :   :   | 8 :   : 6 |   :   : 2 |
-------------------------------------
|   : 6 :   |   : 7 :   |   : 3 :   |
|   :   : 8 |   :   :   | 2 :   :   |
|   :   :   | 1 :   : 5 |   :   :   |
-------------------------------------

There is another number we can fill in from the starting grid. If we look at the center horizontal section, the middle and right-hand 3x3 grids have sixes in, but the left one doesn't. The 6 in this section cannot be on the top or bottom row since there are already sixes on those horisontal row, and cannot be on the middle vertical row either. The right-middle square already has a 1 in, so the 6 must be on the left middle square. I've tried to illustrate this below; it may look a little confused but I hope you understand the meaning.

-------------------------------------
|   :   :   | 9 :   : 8 |   :   :   |
|   :   : 4 |   :   :   | 6 :   :   |
|   : 9 :   |   : 3 :   |   : 7 :   |
-------------------------------------
| 9 :~#~:~~~|~2~:~~~:~4~|~~~:~~~:~6~|
| 6 : # : 1 |   : 9 :   | 5 :   :   |
| 3 :~#~:~~~|~8~:~~~:~6~|   :   : 2 |
------#------------------------------
|   : 6 :   |   : 7 :   |   : 3 :   |
|   :   : 8 |   :   :   | 2 :   :   |
|   :   :   | 1 :   : 5 |   :   :   |
-------------------------------------

Not all parts of the puzzle are this easy, of course; there may not at a particular point be a definite next step. The only solutions in this case must be found by logically following possible paths, backtracking if a problem occurs. Feel your brain groan as you metally recurse through logical pathways.

Now you have learned the basic rules of the puzzle it should be a simple matter to complete the rest. I feel I must warn you, however. These puzzles do look easy at first glance, but you ofen find yourself overlooking something and don't realise you've gone wrong until much later.

Solution to the demonstration puzzle

If you've decided to try out the example above, and see if you could complete it, here's the solution for you to check your result not, of course, to cheat with!

-------------------------------------
| 7 : 5 : 6 | 9 : 4 : 8 | 1 : 2 : 3 |
| 1 : 3 : 4 | 5 : 2 : 7 | 6 : 8 : 9 |
| 8 : 9 : 2 | 6 : 3 : 1 | 4 : 7 : 5 |
-------------------------------------
| 9 : 8 : 7 | 2 : 5 : 4 | 3 : 1 : 6 |
| 6 : 2 : 1 | 7 : 9 : 3 | 5 : 4 : 8 |
| 3 : 4 : 5 | 8 : 1 : 6 | 7 : 9 : 2 |
-------------------------------------
| 5 : 6 : 9 | 4 : 7 : 2 | 8 : 3 : 1 |
| 4 : 1 : 8 | 3 : 6 : 9 | 2 : 5 : 7 |
| 2 : 7 : 3 | 1 : 8 : 5 | 9 : 6 : 4 |
-------------------------------------

Sudoku puzzles can trace their lineage from the magic square (carrés magiques) of 18th century mathematical genius Euler, via latin squares, through American and then Japanese versions in the 80s (from which the name arises- roughly translated, it means solitary number), to their current surge in popularity in the UK, fuelled by publication in most of the quality newspapers (having first appeared in late 2004, however, in the Daily Mail).

For a month or so now, a few of my fellow students have been whiling away time in our own mathematical square, plugging away at Suduko grids from brightly coloured Japanese puzzle collections (combined circulation of dedicated Sudoku books in Japan is around 600,000 a month). Since I like to fuel the illusion that I know a thing or two about numbers, but am in fact generally rubbish at puzzles, I avoided attempting any until earlier this week when I spotted a bunch in The Independent- the next thing I knew, I'd lost my Wednesday afternoon.

Of course, I mangled the first one horribly, so sat down to approach the second one in a more systematic fashion. The simplest trick, as described by Sir Norris above, is to find cells which, through a combination of pressures from the row, column and 3*3 block, can only take a single value. After getting bored with pencilling in possibilities, I knocked together a Maple worksheet that generated lists of possible values for each cell. The best case of this brute force approach is when singletons appear- by plugging those back in and repeating the process, I solved the elementary problem from the Indie entirely mechanically. Which, although a triumph for my feeble coding skills, wasn't particularly enlightening with regards to the subtleties of Sudoku. So I fed the most difficult problem in, and was rewarded with not one cell that was completely determined. Now I had a challenge :)

Some advanced Sudoku tactics

Possibly ruining all the fun, and listed in order of desperation- the further you get in this list, the more fiendish the original puzzle.

So, having carried out the entirely routine steps of identifying potential values (either through fancy computing or writing extremely small in pencil), and assuming that wasn't sufficient to solve the grid, we're in a position to apply some logic. The hope here is that through reasoning, we can reduce or eliminate entirely the need for guesswork and backtracking. Of course, a lucky guess will speed things up, so a combination of reason and intuition make for a true sudoku master. These methodical steps seem like an ideal starting point for a full-fledged solver program, should any of you coders fancy a distraction.

Effective singletons

-------------------------
|(4,5) :    3    :       |
|  2   :         :       |
|      : (4,5,9) : (4,5) |
-------------------------

Here the values 2 and 3 are given, and we've worked out the options for three cells of interest. If we figure out which of (4,5) the top left cell is, then we get the bottom right for free. But we immediately know the value of the (4,5,9) cell, which may help us determine entries elsewhere if we're currently stumped by the (4,5) choice. This is because whichever the top left cell turns out to be, 4 or 5, the bottom right cell will be the other, 5 or 4. So really, no other cell in this block can be a 4 or a 5, so the (4,5,9) entry is in fact the singleton (9).

This works just as well in a row or column, but the block was a bit easier to display in ascii art. Furthermore, larger cases are theoretically possible- cells with the options (3,4,5), (3,4,5), (3,4,5), (3,4,5,6) force the 6 for the last cell; or (1,2), (1,2), (3,4), (3,4), (1,2,3,4,5) forces the 5 in a cell that seemed to have unassailably many options. But such intricate cases require more cells to be just-so, and hence are rarer.

The importance of once-and-only-once

So far, the approach of identifying singletons or effective singletons has relied on the fact that a given number may appear only once in the row/column/block- we generate lists of potential values by eliminating the ones that have been 'used up' by already making an appearance. But we have a two way condition- each value needs to appear precisely once. So instead of looking for cells that can only take a single value, we look for values that can only occupy a single cell. Here's another block to illustrate.

---------------------------
|(4,6) :    3    : (1,7,9) |
|  2   :  (1,4)  : (7,8,9) |
|(7,9) : (4,5,9) :  (4,5)  |
---------------------------

In this complicated looking list of options, we can in fact determine two of the values. The top left cell has to take the value 6, since no other can; and similarly the 8 must lie in the middle of the third column.

Proof by contradiction

Suppose all the singletons,both immediate and effective have been identified, and furthermore any forced choices from the second strategy above have been made. You've scanned all the affected rows, columns and blocks in light of these changes, and have no more such cases to consider. So a guess is needed. What makes a good gambit? Chances are, what you do have are several chains of cells who's fates are linked, as described earlier. A (4,5) choice may be linked to another such choice in a column- but also be connected to a (3,5) in its row. Now, if it turns out to be a 4, then we don't get any information about the (3,5) pair- but if it's a 5, we determine that (3,5) is really a 3. So, you may have some luck in considering one of the cases from a particularly popular pair. Chose one option, and chase it around the grid. If it generates a contradiction somewhere (two 3's in the same block, for instance), then it can't be a valid choice- so you know it's the other one from the original pair. But beware- absence of contradiction is not sound grounds to assume that your choice was correct, unless of course you finish the puzzle in the process of following its implications. It could just be that you haven't reduced enough cells to get the contradiction, rather than there not being a contradiction at all; and then you'll come unstuck later. The validity of a choice is only certain once you've found counterexamples to the validity of all the other choices- this, in simpler fashion, is what we've been doing from the start in dismissing possibilities.

Sudoku Variants

Sudoku seem to be spreading across the puzzle pages of Britain's quality compacts and broadsheets, and inevitably different papers will introduce gimmicks, such as the Daily Mail's Sudoku-X (which uses rectangles and places a condition on diagonals). The Independent seems particularly keen, having tried letters in place of numbers (with one of the rows or columns yielding an actual word), and on Saturdays offering a Super Sudoku version, which ups the ante to 16X16, 4 subgrids (in hex), clearly making it even harder to keep track of a comprehensive list of possible values, either in your head or on paper! They even ran a national tournament (I qualified for regionals but was moving that day. Oh well.) However, the tried and tested 3X3 version will probably emerge as the staple, since the amount of time it consumes can be tweaked to more or less manageable cases, whilst the super is always going to while away a weekend. Sticking with the format but changing the character set, the debutante has pointed out that Sidduroku, substituting hebrew letters for numerals, will 'fuzzle the brain'!

Complexity

Research at the university of Tokyo has shown that solving n-by-n belongs to the NP-complete class, which is (roughly) one where a solution is easily checked for validity but becomes exponentially more difficult to compute as n grows. There are, for instance, 5524751496156892842531225600 different 9-by-9 latin squares possible- but the additional sudoku requirement on the internal 3-by-3 boxes carves that number down considerably. Reminiscent of the eternity puzzle, specifying the position of numbers in the grid can actually make things harder for the solver since it reduces the number of possible solutions. This is partly how it is possible to adjust the difficulty of a sudoku grid.

themanwho has put a solver online which implements some of the above strategies, removing the donkey work and leaving the interesting stuff (if any; it cheerfully ripped through a maximum difficulty problem from the Independant I tried with it.) It also makes my maple version look shambolic. You can find it here.

I found Wntrmute's tactics quite similiar to what's going on in my troubled head solving the damn sudoku of the day, but I noticed one thing missing... The tactic I usually leave to the super-duper complicated puzzles, just before the guessing part of "proof by contradiction".

I call it by its lame title:

A row's safe value

It goes like this. Suppose we've tried all the other tactics over and over again. Now we have, in some box, a value that can only populate two or three cells, which happen to be on the same row or column.
I'll demonstrate:

---------------------------
|(1,4,6):    3    : (1,7,9) |
|   2   : (4,6,8) :  (7,9)  |
|(1,4,8): (4,5,8) : (1,5,7) |
---------------------------

You can see here that 5 could only exist in the two right cells of the bottom row. This could happen for many reasons, but what's important right now is that you can conclude that no 5s could exist in the same row... Eliminate the options of the other cells in this row and it might be the trick to finding your next number.
The same goes for 7 and 9 in my almost-impossible example.

This one tactic helped me solve some serious sudoku puzzles without having to take guesses. So there you go. Off with your Sudoku.

Solving a SuDoku Puzzle - Step By Step

Before starting, visit this URL and download the sudoku puzzle; we'll solve it together!
http://www.timesonline.co.uk/article/0,,18209-1739363,00.html

Above, several noders have provided nice examples on the rules of sudoku puzzles, as well as a few examples on how to fill in a square or two on a grid. This writeup serves to demonstrate how to solve, from beginning to end, a sudoku puzzle.

You see, my mother is a big fan of word and letter puzzles, such as crosswords. When I got into a big sudoku kick earlier this year, I attempted to show her how to solve one, yet she didn't really seem to understand what was to be done, or what techniques to use. The big reason is that her thought processes are generally less logical and more organic in nature.

My solution was to take a relatively simple example and show her step by step how to deduce additional squares, all the way to the end of the puzzle. She read through this a time or two and was then able to start solving the puzzles. Before long, she was nearly as skilled as I am at solving sudoku puzzles.

So, without further ado, here is the solution to a sudoku puzzle from beginning to finish. I have chosen to solve the "mild" difficulty puzzle from the August 18, 2005 edition of the London Times as an example. This puzzle is available at http://www.timesonline.co.uk/article/0,,18209-1739363,00.html; you are advised to print yourself out a copy, get out a pen, and solve along with me.

Su Doku: August 18, 2005
The London Times Online
No. 306 - Rating: Mild

-------------------------------------
|   : 1 : 3 |   :   :   | 4 : 8 :   |
|   :   :   | 4 :   : 2 |   :   :   |
| 9 :   : 7 |   :   :   | 2 :   : 6 |
-------------------------------------
| 3 :   :   |   : 2 :   |   :   : 5 |
|   : 2 :   | 7 :   : 1 |   : 6 :   |
| 8 :   :   |   : 4 :   |   :   : 3 |
-------------------------------------
| 4 :   : 5 |   :   :   | 6 :   : 8 |
|   :   :   | 1 :   : 5 |   :   :   |
|   : 8 : 2 |   :   :   | 5 : 3 :   |
-------------------------------------

The first thing to look for when starting a sudoku puzzle are each set of three rows (the first, second, and third rows; the fourth, fifth, and sixth rows; and the seventh, eighth, and ninth rows) and each set of three columns (again, the first, second, and third columns; the fourth, fifth, and sixth columns; and the seventh, eighth, and ninth columns). What you're looking for are numbers that appear in two of the members of the set, but not the third.

Let's go through each set of rows and columns one at a time.

In the first set of rows:
2 appears in the second and third rows, but not in the first
4 appears in the first and second rows, but not in the third

2 is a potential candidate to put onto the grid. We can see above that a 2 already occurs in the second set of columns (more specifically, the second row of the sixth column) and the third set of columns (more specifically, third row, seventh column). I've bolded these above to make it more clear.

-------------------------------------
|   : 1 : 3 |   :   :   | 4 : 8 :   |
|   :   :   | 4 :   : 2 |   :   :   |
| 9 :   : 7 |   :   :   | 2 :   : 6 |
-------------------------------------

Thus, a 2 cannot be placed in the second or third row, because there is already a 2 in that row, and also, a 2 cannot be placed in the second or third small square, because there is already a 2 in each of these small squares. Let's then X out all of the squares we cannot place a 2 in. Note: you would NOT actually X out all these squares if actually solving a puzzle. This is to help you visualize the eliminated squares.

-------------------------------------
|   : 1 : 3 | X : X : X | 4 : 8 : X |
| X : X : X | 4 : X : 2 | X : X : X |
| 9 : X : 7 | X : X : X | 2 : X : 6 |
-------------------------------------

That leaves only a single possible square where a 2 could be placed in the first row, so we can add that to the grid.

-------------------------------------
| 2 : 1 : 3 |   :   :   | 4 : 8 :   |
|   :   :   | 4 :   : 2 |   :   :   |
| 9 :   : 7 |   :   :   | 2 :   : 6 |
-------------------------------------

Let's repeat the process with the 4 that appears in the first and second rows, but not in the third:

-------------------------------------
| 2 : 1 : 3 |   :   :   | 4 : 8 :   |
|   :   :   | 4 :   : 2 |   :   :   |
| 9 :   : 7 |   :   :   | 2 :   : 6 |
-------------------------------------

-------------------------------------
| 2 : 1 : 3 | X : X : X | 4 : 8 : X |
| X : X : X | 4 : X : 2 | X : X : X |
| 9 :   : 7 | X : X : X | 2 : X : 6 |
-------------------------------------

-------------------------------------
| 2 : 1 : 3 |   :   :   | 4 : 8 :   |
|   :   :   | 4 :   : 2 |   :   :   |
| 9 : 4 : 7 |   :   :   | 2 :   : 6 |
-------------------------------------

Much like when the 2 was placed, you can observe that there can't be a 4 in the first or second row, nor the second or third small square. This leaves only one place you can put the 4; the second square in the third row.

In the second set of rows:
3 appears in the fourth and sixth rows, but not in the fifth
2 appears in the fourth and fifth rows, but not in the sixth

Putting the 3 on the grid is as simple as before. Taking the middle three rows...

-------------------------------------
| 3 :   :   |   : 2 :   |   :   : 5 |
|   : 2 :   | 7 :   : 1 |   : 6 :   |
| 8 :   :   |   : 4 :   |   :   : 3 |
-------------------------------------

-------------------------------------
| 3 : X : X | X : 2 : X | X : X : 5 |
| X : 2 : X | 7 :   : 1 | X : 6 : X |
| 8 : X : X | X : 4 : X | X : X : 3 |
-------------------------------------

-------------------------------------
| 3 :   :   |   : 2 :   |   :   : 5 |
|   : 2 :   | 7 : 3 : 1 |   : 6 :   |
| 8 :   :   |   : 4 :   |   :   : 3 |
-------------------------------------

... we can easily place a 3 in the very center square. Now, let's try placing the 2...

-------------------------------------
| 3 :   :   |   : 2 :   |   :   : 5 |
|   : 2 :   | 7 : 3 : 1 |   : 6 :   |
| 8 :   :   |   : 4 :   |   :   : 3 |
-------------------------------------

-------------------------------------
| 3 : X : X | X : 2 : X | X : X : 5 |
| X : 2 : X | 7 : 3 : 1 | X : 6 : X |
| 8 : X : X | X : 4 : X |   :   : 3 |
-------------------------------------

Hmm... there are still two possible places that we could put the 2 in the sixth row. Can we get another clue? Let's look at that whole column, leaving the "imaginary" X's in place.

-------------
| 4 : 8 :   |
|   :   :   |
| 2 :   : 6 |
-------------
| X : X : 5 | 
| X : 6 : X |
|   :   : 3 | <-- we want to put a 2 in this row
-------------
| 6 :   : 8 |
|   :   :   |
| 5 : 3 :   |
-------------

In the leftmost column, you'll see a number 2 in the third row above. Let's put Xs in the entire leftmost column as well:

-------------
| 4 : 8 :   |
| X :   :   |
| 2 :   : 6 |
-------------
| X : X : 5 | 
| X : 6 : X |
| X :   : 3 | <-- we want to put a 2 in this row
-------------
| 6 :   : 8 |
| X :   :   |
| 5 : 3 :   |
-------------

And we're left with only one possible square to put that 2 into!

In the third set of rows, there's nothing of note, so let's look at where we're at (solutions we've added are in bold):

-------------------------------------
| 2 : 1 : 3 |   :   :   | 4 : 8 :   |
|   :   :   | 4 :   : 2 |   :   :   |
| 9 : 4 : 7 |   :   :   | 2 :   : 6 |
-------------------------------------
| 3 :   :   |   : 2 :   |   :   : 5 |
|   : 2 :   | 7 : 3 : 1 |   : 6 :   |
| 8 :   :   |   : 4 :   |   : 2 : 3 |
-------------------------------------
| 4 :   : 5 |   :   :   | 6 :   : 8 |
|   :   :   | 1 :   : 5 |   :   :   |
|   : 8 : 2 |   :   :   | 5 : 3 :   |
-------------------------------------

Let's try adding more numbers using the columns.

In the first set of columns:
4 appears in the first and second columns, but not in the third
3 appears in the first and third columns, but not in the second

Neither of these make it possible for us to add a number. With the 4, we know it has to go in the middle three squares of the third row. Since they're all empty and the only additional clue we can get is that it can't go into the bottom square in that row, we have to skip it. Here's a grid with Xs indicating squares where you can't put the 2 along with that little region in bold to help you visualize this.

-------------------------------------
| 2 : 1 : 3 |   :   :   | 4 : 8 :   |
| X : X :   | 4 :   : 2 |   :   :   |
| 9 : 4 : 7 |   :   :   | 2 :   : 6 |
-------------------------------------
| 3 : X :   |   : 2 :   |   :   : 5 |
| X : 2 :   | 7 : 3 : 1 |   : 6 :   |
| 8 : X : X | X : 4 : X | X : 2 : 3 | <- no new 4 in this
-------------------------------------         row because of
| 4 : X : 5 |   :   :   | 6 :   : 8 |         the 4 in the 5th
| X : X :   | 1 :   : 5 |   :   :   |         column
| X : 8 : 2 |   :   :   | 5 : 3 :   |
------------------------------------- 
  ^   ^
  there can't be another 4 in this column
   because of the 4 in the seventh row
      |
      |
      there can't be another 4 in this column
       because of the 4 in the third row

A similar problem occurs with the 3. We can only say that it goes in the second column in one of the bottom three squares, but that still leaves us with two possibilities and we can't reduce it any more than that.

In the second set of columns:
1 appears in the first and third columns, but not in the second
4 appears in the first and second columns, but not in the third
2 appears in the second and third columns, but not in the first

We can't put the 1 in for the same reason we couldn't put the 4 and the 3 in the first set of columns: there are two empty squares left that are possibilities. Can you see why? The possible squares are marked with a 0 below.

-------------------------------------
| 2 : 1 : 3 |   :   :   | 4 : 8 :   |
|   :   :   | 4 : 0 : 2 |   :   :   |
| 9 : 4 : 7 |   : 0 :   | 2 :   : 6 |
-------------------------------------
| 3 :   :   |   : 2 :   |   :   : 5 |
|   : 2 :   | 7 : 3 : 1 |   : 6 :   |
| 8 :   :   |   : 4 :   |   : 2 : 3 |
-------------------------------------
| 4 :   : 5 |   :   :   | 6 :   : 8 |
|   :   :   | 1 :   : 5 |   :   :   |
|   : 8 : 2 |   :   :   | 5 : 3 :   |
-------------------------------------

With both the 4 and the 2, we have more success. First, the 4:

-------------
| X : X : X |
| 4 : X : 2 | <- there can only be
| X : X : X |         one 4 in each
-------------         small square
| X : 2 : X |              |
| 7 : 3 : 1 | <--------/
| X : 4 : X |
-------------
| X : X :   |
| 1 : X : 5 |
| X : X :   |
-------------
  ^   ^
  there can only be one 4 in each column


-------------------------------------
| 2 : 1 : 3 | X : X : X | 4 : 8 :   |
|   :   :   | 4 : X : 2 |   :   :   |
| 9 : 4 : 7 | X : X : X | 2 :   : 6 |
-------------------------------------
| 3 :   :   | X : 2 : X |   :   : 5 |
|   : 2 :   | 7 : 3 : 1 |   : 6 :   |
| 8 :   :   | X : 4 : X |   : 2 : 3 |
-------------------------------------
| 4 : X : 5 | X : X : X | 6 : X : 8 | <- only one 4 in this row
|   :   :   | 1 : X : 5 |   :   :   |
|   : 8 : 2 | X : X : 4 | 5 : 3 :   |
-------------------------------------

As you see, we can thus place a 4 in the bottom row of the sixth column. How about the 2?

-------------
| X : X : X |
| 4 : X : 2 |
| X : X : X |
-------------
| X : 2 : X |
| 7 : 3 : 1 |
| X : 4 : X |
-------------
|   : X : X |
| 1 : X : 5 |
|   : X : 4 |
-------------

-------------------------------------
| 2 : 1 : 3 |   : X : X | 4 : 8 :   |
|   :   :   | 4 : X : 2 |   :   :   |
| 9 : 4 : 7 |   : X : X | 2 :   : 6 |
-------------------------------------
| 3 :   :   |   : 2 : X |   :   : 5 |
|   : 2 :   | 7 : 3 : 1 |   : 6 :   |
| 8 :   :   |   : 4 : X |   : 2 : 3 |
-------------------------------------
| 4 :   : 5 | 2 : X : X | 6 :   : 8 |
|   :   :   | 1 : X : 5 |   :   :   |
| X : 8 : 2 | X : X : 4 | 5 : 3 : X |
-------------------------------------

And we can put the 2 into the seventh row of the fourth column.

In the third set of columns:
2 appears in the first and second column, but not the