How to Solve Sudoku with Python

Nov 2 2022

Sudoku puzzles can range from criminally easy to extremely difficult. With python however, we can solve (most) sudoku puzzles within seconds. In this article, we’ll develop an algorithm to solve a sudoku puzzle.

Representation

For this problem we’ll need two main components. Firstly, a way to represent our crossword puzzle. Ideally, we’ll need a data structure with a quick access and modification time. We’ll use a 2d array for this project. Let’s get this setup in python:

grid = [
    [0,0,0, 0,0,0, 0,0,0],
    [0,0,0, 0,0,0, 0,0,0],
    [0,0,0, 0,0,0, 0,0,0],

    [0,0,0, 0,0,0, 0,0,0],
    [0,0,0, 0,0,0, 0,0,0],
    [0,0,0, 0,0,0, 0,0,0],
    
    [0,0,0, 0,0,0, 0,0,0],
    [0,0,0, 0,0,0, 0,0,0],
    [0,0,0, 0,0,0, 0,0,0],
]

This will initialise our empty grid, with zeros in every square. That’s our representation pretty much sorted, so we can move onto actually solving a given crossword puzzle.

Utility functions

We’re going to create some utility functions which will greatly help our solution down the line. Each of these will perform checks for the standard rules of sudoku.

Lets start by checking whether a number is in a given row. This is very simple, as we have each row stored within our grid array.

def inRow(num, row):
    return num in grid[row]

Now, we can check columns. This will be slightly more tricky, but still fairly straightforward. We just need to check the same column in each row, and return True if we find it.

def inColumn(num, column):
    for item in range(9):
        if grid[item][column] == num:
            return True
    return False

Finally, we need to check whether a number exists already within a given square. We first calculate the square to check, and then check all locations within that square. Add import math to the top of your python file, and add the below function.

def inSquare(num, row, column):
    # Get correct square
    startRow = 3 * math.floor(row / 3)
    startCol = 3 * math.floor(column / 3)

    # Check every value in square
    for i in range(startRow, startRow + 3):
        for j in range (startCol, startCol + 3):
            if grid[i][j] == num:
                return True
    return False

Now these are done, we need a function to determine whether we can place a number in a certain position. We will create a possible function to do this.

def possible(num, row, column):
    return not(inRow(num, row) or inColumn(num, column) or inSquare(num, row, column))

We check to see whether the number is already in the given row or column, and return True if it is not present.

With these three utility functions, it is fairly straightforward to solve the sudoku.

Solving the puzzle

We will now create our recursive solve function to complete the sudoku. We iterate through each square in the grid, checking whether we can place any number between 1 and 9 in the location. If there are no possible numbers to place in this location, we backtrack and try a different number.

def solve():
    for i in range(9):
        for j in range(9):
            if grid[i][j] == 0:
                for num in range(1, 10):
                    if possible(num, i, j):
                        grid[i][j] = num
                        solve()
                        grid[i][j] = 0
                return
    for item in grid:
        print(item)
    exit()

solve()

When we have found a solution, we output the solution and exit the program. Without this, the program would find all possible solutions, which could take some time…

With that, our program is complete! We have successfully written a program to solve any sudoku puzzle. Feel free to expand this algorithm, and build a fleshed out Sudoku Solver.

Full code

For the full code, check Github or see below:

import math

#Example sudoku 
grid = [
   [0,0,6, 0,4,0, 0,9,7],
   [0,4,0, 7,3,0, 0,1,0],
   [0,1,7, 0,9,2, 0,3,0],

   [6,0,0, 0,7,0, 0,8,0],
   [1,0,5, 0,6,0, 9,0,3],
   [0,2,0, 0,1,0, 0,0,6],

   [0,5,0, 9,8,0, 1,6,0],
   [0,9,0, 0,5,6, 0,7,0],
   [8,6,0, 0,2,0, 3,0,0],
]

# Check whether the number is already in the current row
def inRow(num, row):
    return num in grid[row]

# Check whether the number is already in the current column
def inColumn(num, column):
    for item in range(9):
        if grid[item][column] == num:
            return True
    return False

def inSquare(num, row, column):
    # Get correct square
    startRow = 3 * math.floor(row / 3)
    startCol = 3 * math.floor(column / 3)

    # Check every value in square
    for i in range(startRow, startRow + 3):
        for j in range (startCol, startCol + 3):
            if grid[i][j] == num:
                return True
    return False

# Check whether a number is possible
def possible(num, row, column):
    return not(inRow(num, row) or inColumn(num, column) or inSquare(num, row, column))


# code to actually solve the puzzle
def solve():
    for i in range(9):
        for j in range(9):
            if grid[i][j] == 0:
                for num in range(1, 10):
                    if possible(num, i, j):
                        grid[i][j] = num
                        solve()
                        grid[i][j] = 0
                return
    for item in grid:
        print(item)
    
    exit()
    
    

solve()