Solving sudoku
See also - Sudoku solver | Introduction to sudoku
Sudoku has been described as “the crossword without words” and has a large following across the world. The idea of the puzzle is very simple - you are presented with a grid such as below…
…and are given the instructions…
“Fill the grid so that each row, column and 3 x 3 box contains the numbers 1 to 9”
Each Sudoku puzzle should have one, and only one solution. Whatsmore, sudokus from good sources (such as The Times newspaper in the UK and websudoku.com) are solvable by logic alone (i.e. no guessing involved). However, sudokus from other sources may require guesswork.
Personally, I see solving sudoku as all about narrowing down possibilities through logical processes, until ultimately you know that a certain square can only take one possible number. For this reason, I disapprove of of sudokus that require guesswork to reach a solution.
Below I present a guide on how I and my program go about solving Sudoku puzzles, complete with examples. All the Sudoku grids are genuine puzzles taken from The Times newspaper.
Understanding what the rules imply
When reading what follows, always remember the instructions for Sudoku…
“Fill the grid so that each row, column and 3 x 3 box contains the numbers 1 to 9”
Since each row, column and 3 x 3 box consists of nine squares, it follows that you cannot have the same number more than once in any row, column, or 3 x 3 box.
Also, a little terminology:
A square refers to a 1 x 1 square that can take 1 number
A row refers to a horizontal arrangement of 9 squares
A column refers to a vertical arrangement of 9 squares
A 3 x 3 box or just a box refers to a 3 x 3 box made up of nine squares.
So a sudoku grid can be divided in several different ways, as below:
“Fill the grid so that each row, column and 3 x 3 box contains the numbers 1 to 9”
Each Sudoku puzzle should have one, and only one solution. Whatsmore, sudokus from good sources (such as The Times newspaper in the UK and websudoku.com) are solvable by logic alone (i.e. no guessing involved). However, sudokus from other sources may require guesswork.
Personally, I see solving sudoku as all about narrowing down possibilities through logical processes, until ultimately you know that a certain square can only take one possible number. For this reason, I disapprove of of sudokus that require guesswork to reach a solution.
Below I present a guide on how I and my program go about solving Sudoku puzzles, complete with examples. All the Sudoku grids are genuine puzzles taken from The Times newspaper.
Understanding what the rules imply
When reading what follows, always remember the instructions for Sudoku…
“Fill the grid so that each row, column and 3 x 3 box contains the numbers 1 to 9”
Since each row, column and 3 x 3 box consists of nine squares, it follows that you cannot have the same number more than once in any row, column, or 3 x 3 box.
Also, a little terminology:
A square refers to a 1 x 1 square that can take 1 number
A row refers to a horizontal arrangement of 9 squares
A column refers to a vertical arrangement of 9 squares
A 3 x 3 box or just a box refers to a 3 x 3 box made up of nine squares.
So a sudoku grid can be divided in several different ways, as below:
The elimination method
This method is the simplest application of the rules that were clarified above. Look at the grid below…
This method is the simplest application of the rules that were clarified above. Look at the grid below…
As I said earlier, solving Sudoku is all about narrowing down possibilities through logical processes, until ultimately you know that a certain square can only take one possible number.
Look at square A. It is in the ninth column. From the rules, we know that no number can appear in any column more than once, so we can immediately deduce that square A cannot take an 8, 1, 3, 4 or 9.
Similarly, square A is in the fourth row. For the same reason, we know that square A cannot take a 9, 7, 8 or 4.
Again, square A is in the middle-right 3 x 3 box. Hence we deduce that square A cannot take a 4, 1, 7 or 3.
Putting all this together, we find that square A cannot contain a 1, 3, 4, 7, 8 or 9. Therefore we know that the only values square A can take are a 2, 5 or 6.
This may not seem like much use at the moment, but from assuming that A can take any value, we have narrowed it down to three possibilities.
You may find it useful to write a small “256” in square A when solving the puzzle, which you can erase when you find out for definite which number goes in square A.
Using this method, can you work out what squares B and C could take?
Answers
B could take a 2, 3, 5 or 9
C must take a 1.
You will notice that in the case of square C, we have found out for definite what number belongs there.
In the sudoku solver program, the elimination method is applied to every square. This gives the program now a set of possible numbers for every empty square.
The last in place method
Look at this grid…
Look at square A. It is in the ninth column. From the rules, we know that no number can appear in any column more than once, so we can immediately deduce that square A cannot take an 8, 1, 3, 4 or 9.
Similarly, square A is in the fourth row. For the same reason, we know that square A cannot take a 9, 7, 8 or 4.
Again, square A is in the middle-right 3 x 3 box. Hence we deduce that square A cannot take a 4, 1, 7 or 3.
Putting all this together, we find that square A cannot contain a 1, 3, 4, 7, 8 or 9. Therefore we know that the only values square A can take are a 2, 5 or 6.
This may not seem like much use at the moment, but from assuming that A can take any value, we have narrowed it down to three possibilities.
You may find it useful to write a small “256” in square A when solving the puzzle, which you can erase when you find out for definite which number goes in square A.
Using this method, can you work out what squares B and C could take?
Answers
B could take a 2, 3, 5 or 9
C must take a 1.
You will notice that in the case of square C, we have found out for definite what number belongs there.
In the sudoku solver program, the elimination method is applied to every square. This gives the program now a set of possible numbers for every empty square.
The last in place method
Look at this grid…
Can you work out what square X must be?
Answer
Square X has to be a 9.
Consider the top right 3 x 3 box, and notice that the second row has a 9 in it. Therefore, if we want to put a nine somewhere in the top right 3 x 3 box, it cannot go in the second row…
Answer
Square X has to be a 9.
Consider the top right 3 x 3 box, and notice that the second row has a 9 in it. Therefore, if we want to put a nine somewhere in the top right 3 x 3 box, it cannot go in the second row…
Similarly, there is a 9 in the third row…
And there is also a 9 in the ninth column…
So square X must take a 9, as there is nowhere else we could place a 9 in the top-right 3 x 3 box.
With some experience, picking this method up becomes second nature when doing puzzles by hand.
This method can also be applied to rows and columns by seeing if there is only one place in a row or column that a certain number can be placed. Can you work out what square X in the grid below must be?
With some experience, picking this method up becomes second nature when doing puzzles by hand.
This method can also be applied to rows and columns by seeing if there is only one place in a row or column that a certain number can be placed. Can you work out what square X in the grid below must be?
Answer
Square X must be a 2.
This is because we cannot put a 2 into any other square in the second column, as there are other 2’s “in the way” as illustrated below…
Square X must be a 2.
This is because we cannot put a 2 into any other square in the second column, as there are other 2’s “in the way” as illustrated below…
Using the same principle, can you work out what square X must be below?
Answer
Square X must be a 6.
This is because X is the only place in the third row in which it is possible to put a 6. The grid below illustrates why...
Square X must be a 6.
This is because X is the only place in the third row in which it is possible to put a 6. The grid below illustrates why...
Normally, using the elimination and last in place methods, it is possible to solve the puzzles graded 'easy' or 'mild' by The Times newspaper. However, for the 'difficult' and 'fiendish' puzzles, read on…
The box overlap method
This method relies on hypothesising on what would happen if you were to place a number in a certain place. It does not involve guessing!
Look at this grid. It is a half-solved Sudoku puzzle…
The box overlap method
This method relies on hypothesising on what would happen if you were to place a number in a certain place. It does not involve guessing!
Look at this grid. It is a half-solved Sudoku puzzle…
Using the elimination method, in each empty square we can write the values that the square could take…
Now I am going to highlight all the squares that could take a 6 in yellow…
Look carefully at the bottom middle 3 x 3 box and the fifth column. In the bottom middle 3 x 3 box, there are only two squares in which we could place a six. Both of these squares also happen to be in the fifth column.
Now here comes the hypothesising. Imagine that any of the squares that are in the fifth column but not in the bottom middle 3 x 3 box were to take a six. If this were the case, we would have a six in place for the fifth column. However, this would also mean that it becomes impossible to place a six in the bottom middle 3 x 3 box.
Confused? Look at square X below.
Now here comes the hypothesising. Imagine that any of the squares that are in the fifth column but not in the bottom middle 3 x 3 box were to take a six. If this were the case, we would have a six in place for the fifth column. However, this would also mean that it becomes impossible to place a six in the bottom middle 3 x 3 box.
Confused? Look at square X below.
Imagine what would happen if we put a six in square X. The boxes in dark yellow on the grid below show where we would no longer be able to place a six if square X were a six.
If you look at the bottom middle 3 x 3 box, you will notice that there is nowhere left for the 6 to go.
Therefore the conclusion is simple – we can’t place a six in square X, as this would make it impossible to put a six in the bottom middle 3 x 3 box.
For exactly the same reason, we can apply the same conclusion to squares Y and Z in the grid below…
Therefore the conclusion is simple – we can’t place a six in square X, as this would make it impossible to put a six in the bottom middle 3 x 3 box.
For exactly the same reason, we can apply the same conclusion to squares Y and Z in the grid below…
This method further helps to narrow down the possibilities, which is what solving Sudoku is all about.
Look at this next grid. It is the same grid, only this time I have highlighted the places where we could place a 9. Can you work out, using the method described above, where we cannot place a 9?
Look at this next grid. It is the same grid, only this time I have highlighted the places where we could place a 9. Can you work out, using the method described above, where we cannot place a 9?
Answer
You cannot place a nine where the seventh row and the eighth column meet, because this would make it impossible to place a nine in the bottom left 3 x 3 box.
This method can also be applied by looking at rows and columns (as well as 3 x 3 boxes). Below I have highlighted all the places where we could place a 1…
You cannot place a nine where the seventh row and the eighth column meet, because this would make it impossible to place a nine in the bottom left 3 x 3 box.
This method can also be applied by looking at rows and columns (as well as 3 x 3 boxes). Below I have highlighted all the places where we could place a 1…
Look at the first column. There are two places in it where we can place a 1. Both of these places are also in the bottom 3 x 3 box. Therefore, it follows that in order to place a 1 in the bottom left 3 x 3 box and the first column, a 1 must be placed in a square that is both in the first column and in the bottom left 3 x 3 box.
Just to clarify, look square X below.
Just to clarify, look square X below.
If we placed a 1 there then this makes it impossible to place a 1 in the first column. Therefore we cannot place a 1 in square X. Again, this eliminates another possibility, helping us to solve the Sudoku puzzle. Now, can you find, using the method described above, three places where we cannot place a number 4? (Below, I have highlighted the places where we could place a 4 for clarity)…
Answer
We cannot place a 4 in the squares marked X, Y and Z in the grid below, because this would make it impossible to place a 4 in the seventh row (and also make it impossible to place a 4 in the bottom middle 3 x 3 box).
We cannot place a 4 in the squares marked X, Y and Z in the grid below, because this would make it impossible to place a 4 in the seventh row (and also make it impossible to place a 4 in the bottom middle 3 x 3 box).
That’s the impossible placement method sorted. Now its time to move onto my final method – which is probably the most effective one for solving harder puzzles – the one that Wayne Gould has called “divide and conquer”…
The divide and conquer method
This method is my favourite for two reasons – it is very effective at solving the more difficult puzzles, and it is one of the most logical, but very simple methods (once you’ve mastered it, of course!)
Look carefully at the the half solved puzzle below. The squares highlighted in grey are the important ones.
The divide and conquer method
This method is my favourite for two reasons – it is very effective at solving the more difficult puzzles, and it is one of the most logical, but very simple methods (once you’ve mastered it, of course!)
Look carefully at the the half solved puzzle below. The squares highlighted in grey are the important ones.
In the sixth column, we have two spaces where we could either place a two or a nine. Note that we can only place a two or a nine in the two the highlighted squares.
Therefore one of these squares must be a 2 and the other must be a 9. As both these squares are in the sixth column, we now know that we cannot place a 2 or a 9 in any other square in the sixth column. This allows us to eliminate 2's and 9's from the squares highlighted below in yellow…
Therefore one of these squares must be a 2 and the other must be a 9. As both these squares are in the sixth column, we now know that we cannot place a 2 or a 9 in any other square in the sixth column. This allows us to eliminate 2's and 9's from the squares highlighted below in yellow…
This has helped to narrow down the possibilities, helping us on our way to solving this Sudoku puzzle.
The method above will probably solve the majority of the fiendish puzzles. But to solve the hardest ones, this method has to be extended to looking at three squares in a row/column/3 x 3 box.
Look at this grid as an example.
The method above will probably solve the majority of the fiendish puzzles. But to solve the hardest ones, this method has to be extended to looking at three squares in a row/column/3 x 3 box.
Look at this grid as an example.
We have three squares in the ninth row which must take three numbers (2, 3 and 6) between them. Therefore no other square in the ninth row can take these numbers, leaving us with the grid below...
…which has narrowed down the possibilities, helping us to solve the puzzle.
Don’t forget that this method was applied to a row in the example above (specifically the ninth row), but the method can of course also be applied to columns and 3 x 3 boxes.
However, to fully solve the puzzle used in the last example, we need to extend the divide and conquer method to four squares. The squares we need to consider are highlighted below...
Don’t forget that this method was applied to a row in the example above (specifically the ninth row), but the method can of course also be applied to columns and 3 x 3 boxes.
However, to fully solve the puzzle used in the last example, we need to extend the divide and conquer method to four squares. The squares we need to consider are highlighted below...
Here we have four squares in the top right 3 x 3 box containing a total of 4 different numbers. Thus each of these squares will contain one of the four numbers (1,3,6 or 8), and so no other square in the 3 x 3 box can take a 1, 3, 6 or 8. This reduces the puzzle to…
…which should, with all of the methods explained, now make this puzzle solvable!
Guessing
As I mentioned at the start, puzzles from some sources may require you to guess in order to reach a solution. When this happens, you will reach a point at which you can make no more logical deductions to solve the puzzle.
From here, you will then need to pick a square, randomly guess which value it could take, and make more logical deductions based on that guess. You will then either solve the puzzle (in which case your guess was correct), find you have square not able to take any value from 1 to 9 (in which case you know your guess was wrong), or reach a point where you have to guess again (in which case you repeat the procedure).
The sudoku solver program handles puzzles that require guessing by going though every single possibility, which also allows it to determine whether a puzzle has one or more solutions.
Solutions
Three genuine Sudoku puzzles from The Times newspaper were used in this guide. Their solutions are listed below. The numbers in bold blue type below are the original puzzle clues.
Puzzle number: 67
Rating: Easy
Guessing
As I mentioned at the start, puzzles from some sources may require you to guess in order to reach a solution. When this happens, you will reach a point at which you can make no more logical deductions to solve the puzzle.
From here, you will then need to pick a square, randomly guess which value it could take, and make more logical deductions based on that guess. You will then either solve the puzzle (in which case your guess was correct), find you have square not able to take any value from 1 to 9 (in which case you know your guess was wrong), or reach a point where you have to guess again (in which case you repeat the procedure).
The sudoku solver program handles puzzles that require guessing by going though every single possibility, which also allows it to determine whether a puzzle has one or more solutions.
Solutions
Three genuine Sudoku puzzles from The Times newspaper were used in this guide. Their solutions are listed below. The numbers in bold blue type below are the original puzzle clues.
Puzzle number: 67
Rating: Easy
Puzzle number: 83
Rating: Fiendish
Rating: Fiendish
Puzzle number: Unknown
Rating: Fiendish
Rating: Fiendish
Page last updated on 28th July 2009 at 16:31 UT
This page copyright* 2006-9 Matthew Skues
*Excludes the actual sudoku puzzles (but not the images) on this page
*Excludes the actual sudoku puzzles (but not the images) on this page
