Search

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 Sudoku 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.


18 views