# Solving sudoku - the Python way

Updated: Nov 20, 2020

__Sudoku__ can be a relaxing and sometimes infuriating puzzle. If you find yourself stuck with a particularly nasty challenge, you can always use a little __Python__ to help you out.

## A brief history

Sudoku first became popular in Japan in 1984 - the name __S____udoku__ is abbreviated from the Japanese 'suuji wa dokushin ni kagiru', which means the numbers must remain single. Similar puzzles appeared in French newspapers around 1895. This was not __Sudoku__ as we recognise it today but it did start the ball rolling. It was 1979 when modern __Sudoku__ appeared in __Dell Magazines__ with the pseudonym of the Number Place.

For anyone who isn't familiar with __Sudoku__, each puzzle is a square grid of 81 cells, divided into nine blocks of nine cells each. Some cells have an integer in them between 1 and 9, and others are left blank. Your goal is to fill in the grid, so that each row, column and smaller 3×3 block, do not contain the same number. Figure 1 shows the basic format of a __Sudoku__ puzzle. Each puzzle must have a single, unique solution.

## The mathematics of sudoku

There are 6, 670, 903, 752, 021, 072, 936, 960 possible __Sudoku__ combinations. Or 6 sextillion (yes there is a name for it) or 10^21 for those that prefer a more concise representation. As a comparison...

The mass of the Earth is quoted as 5.98 sextillion metric tons.

There are around 6 sextillion cups of water in every ocean on our planet.

The volume of the Earth is a little over 1 sextillion cubic metres.

We can reduce this number to 5, 472, 730, 538 by removing symmetries that produce equivalent puzzles. The smallest number of starting clues that a unique puzzle can contain is 17. A computer performed a __brute-force check__ to show there were no 16 clue puzzles. There is an interesting paper __here__ for anyone who would like the read more.

## Solving sudoku with Python

The code for solving a Sudoku puzzle can be found here: __https://github.com/Wibbo/sudoku__.

Simply create a starting grid by defining a list of lists that contain the starting clues. A zero marks each empty cell.

```
sudoku_grid= [[4, 0, 0, 0, 5, 0, 8, 0, 0],
[0, 1, 8, 0, 0, 0, 7, 0, 0],
[0, 0, 3, 0, 0, 4, 0, 0, 0],
[9, 6, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 5, 0, 0, 3, 0, 0, 0],
[0, 7, 0, 0, 0, 8, 0, 6, 0],
[0, 0, 1, 6, 0, 0, 0, 0, 4],
[0, 0, 0, 5, 0, 0, 0, 1, 3],
[0, 0, 0, 8, 0, 0, 0, 0, 0]]
```

The code snippet below shows the main algorithm. The cell_is_empty() function on line 8 returns True if there are any remaining empty cells. If it returns False, then the puzzle is solved; we check for this on line 10.

Line 13 begins a loop that checks if the current number in that loop is valid for the cell we are checking. Line 16 assigns our number to the current cell if it is unique for its row, column and grid. Line 19 recursively tests our solution to see if it is now solved. We set the current cell to zero if the number is not unique and continue with our loop.

```
01 def solve_sudoku():
02 """
03 The top level function for solving the sudoku puzzle.
04 :return: True if solved, False otherwise.
05 """
06 # Check the current state of the sudoku grid.
07 # Return false when an empty cell is found.
08 row, col, cell_status = cell_is_empty()
09
10 if not cell_status:
11 return True
12
13 for i in range(1, 10):
14 # Check if we can assign the current number.
15 if not number_already_exists(i, row, col):
16 sudoku_grid[row][col] = i
17
18 # Now go round and do it again.
19 if solve_sudoku():
20 return True
21
22 # In this case, the number does not fit.
23 sudoku_grid[row][col] = 0
24
25 return False
```

## Closing thoughts

This short post defines and describes how to solve __Sudoku__ puzzles using __Python__. The algorithm uses recursion although it can be written iteratively to avoid it. In a future post we'll use __Python__ to generate __Sudoku__ puzzles of varying difficulty.

Do you have a problem that you need a little help with? Please click below to find out more.