Writing a Sudoku Solver in Python

2 Sep 2018 • Programming

Pretty much every free newspaper you find comes with a sudoku puzzle. Depending on the difficulty it might take you a considerable amount of time to solve them. As a result I wanted to write an algorithm which could do that for me within seconds.

Let’s try to solve the following sudoku: sample sudoku

Strategy

One might be tempted to think that the easiest way to solve a sudoku similar to how we solve a sudoku by hand. But as it turns out there is an algorithm that is easier to implement.

Our strategy is simple. We will write a brute-force algorithm which will try all numbers from left to right, top to bottom until we get to a point where the rules of sudoku are being broken, we then backtrack until we are at a point where we can insert a different number and continue the routine again. This might sounds very complex, but the following animation taken from wikipedia shows how our algorithm is going to work in a very straight-forward way.

Programming the brute-force algorithm

Getting started

To start, we must find a way to represent a sudoku on a computer. I have decided to use a two dimensional array where every row is a subarray of the sudoku. Furthermore, we have to find a way to represent empty fileds which have to be filled, for simplicity I just filled them with zeros. Therefore, our example from above will look like the following.

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

Moreover let’s write a function which will display the sudoku in a pretty way in the console: Since every print statement issued in python comes with a \n newline token, I have decided to first create the whole string of the sudoku and then print it to the console.

def pretty_print(sudoku):
    print_string = ""
    print_string +=("- - - - - - - - - - - - - \n")
    for row_number, row in enumerate(sudoku):
        print_string += ("| ")
        for column_number, number in enumerate(row):
            print_string += (str(number) + " ")
            if (column_number+1)%3==0:
                print_string += ("| ")
        if (row_number+1)%3==0:
            print_string += ("\n- - - - - - - - - - - - - \n")
        else:
            print_string += ("\n")

    print(print_string)

Building our algorithm

We start with a function called solve() which takes the sudoku, a column number and a row number as arguments. Its goal is to solve the sudoku starting from the supplied row and column and working towards the end. This might sounds very strange, why do we need to supply a row and column number? The answer is simple, we are building a recursive algorithm which calls itself to find the solution to the next cell.

This is the full code of our function but we will take a closer look at it below:

def solve(sudoku, row, column):
    if column == 9:
        column = 0
        row += 1
        if row == 9:
            return (True, sudoku)

    if sudoku[row][column] != 0:
        return solve(sudoku, row, column+1)

    for f in range(1,10):
        if legal(sudoku, f, row, column):
            sudoku[row][column] = f
            success, sudoku_plus_one_step = solve(sudoku, row, column+1)
            if success:
                return (True, sudoku_plus_one_step)
    sudoku[row][column] = 0
    return (False, sudoku)

First, in the following piece of code we check if we are currently in the last column of a row. If we are we must advance to the next row. But if we are already in the last row, there is no place to go, what happens now? Recalling how the algorithm works we know that if the last cell has been filled with a number that fits, all numbers before that one must also fit, therefore we have successfully solved the sudoku. In this case we return a tuple with a Boolean value indicating whether we have been successful and the filled sudoku.

if column == 9:
    column = 0
    row += 1
    if row == 9:
        return (True, sudoku)

Now we must find the cells that need our attention. We have defined earlier that all cells filled with a zero, need to be filled, this implies we can skip all cells which don’t contain a zero. We do this in a recursive way, by calling the solve method on the next cell.

if sudoku[row][column] != 0:
        return solve(sudoku, row, column+1);

We can then move on to filling the cell, we know that the number we are looking for must be between zero and nine. We do this by constructing a loop which tries all numbers. The function legal() checks if the number in the specified cell is allowed in the sudoku, if it is we add it to our sudoku and call the solve function on the next cell. If it is not we move on to the next number.

If we were successful in filling the next cell we return the sudoku we have obtained from solving the next cell since it will be the finished sudoku. Why? Since the next cell will call the solve function on the next cell too until we have filled the last cell. This is the magic of recursion.

If we are not able to successfully fill the next cell, we move onto the next number in our for loop.

for f in range(1,10):
    if legal(sudoku, f, row, column):
        sudoku[row][column] = f
        success, sudoku_plus_one_step = solve(sudoku, row, column+1)
        if success:
            return (True, sudoku_plus_one_step)

There are two things that are still missing. What happens if we can’t solve the sudoku from our current cell? This indicates that we have made a mistake in a preceding cell. To handle this we set the current sudoku cell to zero and return that we were not successful.

    sudoku[row][column] = 0
    return (False, sudoku)

This concludes our solve function. However, we are still missing a function which can tell us if a given number is allowed in the sudoku or not. This will be taken care of in the next section.

Writing a function to check if a value is allowed in a cell

The rules of sudoku are very simple and are listed below:

For every 3*3 square drawn with bold lines, every number from 1 to 9 can only appear once.
In every row, every number from 1 to 9 can only appear once.
In every column, every number from 1 to 9 can only appear once.

We must now write a function in python which can check that these rules arent broken. Again, you can find the full code right here and the explanation below:

def legal(sudoku, value, row, column):
    for k in range(9):
        if(value == sudoku[k][column]):
            return False

    for r in range(9):
        if(value == sudoku[row][r]):
            return False

    rowShift = (row//3)*3; # -> this uses integer division
    columnShift = (column//3)*3; # -> this uses integer division

    for k in range(3):
        for r in range(3):
            if value == sudoku[rowShift+k][columnShift+r]:
                return False
    # no violation found, return true
    return True

Our function takes the sudoku as an array, the value we are trying to place in the sudoku, as well as the values coordinates, the row and column.

First, we check that our number doesn’t appear more than once in our column by checking all cells in our column. The exact same thing is done with the rows.

Now we come to the more complex part, we define the rowShift and columnShift variables, these variables define the edges of the 3*3 square in which our cell lies. We then check if our number is already in the 3*3 square.

After passing all these test, we know that the variable we are trying to insert is indeed not violating any sudoku rules.

This concludes our simple alogrithm.

Transforming it into a complete program:

In order to solve a sudoku we can now write the following small script:

import time

start_time = time.time()

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

success , solved_sudoku = solve(sudoku,0,0)

print("Sudoku has been solved:" if success else "Not able to solve the sudoku")
pretty_print(solved_sudoku)

print("Solved in %s seconds." % (time.time() - start_time))

Making it faster:

If you feel like the sudokus are not being solved fast enough there is a very simple trick which will give you a 10 to 20 fold increase in speed. We put our sudoku into a numpy array. This allows us to use the speed provided by numpy’s native implementation.

import time
import numpy as np

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

start_time_no_numpy = time.time()

success , solved_sudoku = solve(sudoku,0,0)

print("Sudoku has been solved:" if success else "Not able to solve the sudoku")
pretty_print(solved_sudoku)

print("Solved in %s seconds without numpy" % (time.time() - start_time_no_numpy))


start_time_with_numpy = time.time()

np_sudoku = np.array(sudoku)

success , solved_np_sudoku = solve(np_sudoku,0,0)

print("Sudoku has been solved:" if success else "Not able to sovle the sudoku")
pretty_print(solved_sudoku)

print("Solved in %s seconds with numpy" % (time.time() - start_time_with_numpy))

Where to go from here:

If you would like to learn more you can get more information at the following links:

Have any feedback?

Please feel free to send me a mail! I would love to hear from you.