Building a Simple Sudoku Solver in Python with numPy

A 10 minute project that gets you thinking about basic algorithms

Jack C

Published in

CodeX

6 min readApr 17, 2021

[If you want to just see the final algorithm, I’ve linked to my full notebook at the end of this article].

Sudoku is about as widespread as a puzzle can get, it even has its own world championship would you believe?

It’s a puzzle that can range from super simple to “pull your hair out” frustrating in difficulty.

For the uninitiated — the rules are as follows:

You start with a 9x9 grid (as above), with some numbers populated
You must fill all of the empty squares in the grid with numbers from 1–9

The bit that makes it tricky is that the following rules must be followed:

No numbers can be repeated in any row
No numbers can be repeated in any column
No numbers can be repeated in any 3x3 sub grid*

A *sub grid is one of the 9 non-overlapping 3x3 grids as shown below, separated by the thicker black lines.

So by the end you’ll have a 9x9 grid with all of the numbers from 1–9 repeated exactly 9 times: 1 in each row, 1 in each column, and 1 in each sub grid.

The beauty of this puzzle is that, assuming it’s been designed properly, there is only 1 solution and that solution can be reached through logic alone without any guesswork.

An opportunity to automate

If it’s a problem that can be solved with logic alone, then there’s no reason we can’t use programming to take the fun out of puzzle solving!

What do we need?

A way of representing a Sudoku board as a matrix (fancy way of saying represent it as rows & columns of numbers)
A way of checking the possible numbers each empty cell can take
A way of filling in the cell when there is only one possible number

Let’s get started!

We begin by making a 9x9 grid of 0’s (where 0 represents an empty cell).

Let’s take a quick look at the output.

It sort of does the job, but it could be neater — and being able to see the 3x3 sub grids would be very helpful.

Why don’t we make a function to make the board look a bit nicer?

Now let’s take a look with this new function.

There are probably libraries out there to make this look even nicer, but this will do for now.

Getting the initial board set up

I’ve used a random puzzle as an example here, but feel free to use either your own puzzle — or a more creative way of getting the initial board set up.

Now for the fun bit!

The logic

When solving any problem that involves logic it helps to write down what you’re trying to do on paper before writing any code.

In this case, we want to:

Go through each empty cell (0) from the top left
Set possible values for that cell as a list of numbers from 1–9, the first time we check it
Check all numbers in the same row, removing any numbers from our list of possible values that match
Do the same as the above for numbers in the same column
Do the same as the above for numbers in the same sub grid
Repeat steps 1–5 for the remaining empty cells
If the board is solved (no 0’s remaining), then finish, otherwise repeat steps 1–6 excluding step 2

Checking numbers in rows & columns in a matrix is simple to do, but checking numbers in a sub grid takes a bit more thought.

Sub grids

We need to be able to take any cell and figure out which sub grid it sits in.

For example, the cell in row 4 and column 3 sits in the second sub grid down from the top left.

We can represent a sub grid as a 3x3 matrix of the numbers contained within it.

To get this 3x3 matrix a cell falls into, we need to be able to round up the row and column positions of that cell to the next largest multiples of 3.

In the example above, the next largest multiple of 3 for the row position (4) is 6, and the next largest multiple of 3 for the column position (3) is 3.

Then we can simply take these end positions, and subtract 3 from each to get the starting positions for the sub grid.

For example, the sub grid above could be represented by board_init[3:6, 0:3], remembering that Python indexes (counts) from 0.

Let’s make a function that can do this rounding up to the next largest multiple of 3.

Let’s take the row index — 3 (again, row position 4 means row index of 3 in Python) and see what it would do:

Take index + 1 (4)
Divide it by 3 (1.333…)
Round it up to the nearest integer using ceil(2)
Multiply it by 3 (6)

Unique values

Now that’s out of the way, we can get to the core of our logic — getting a list of the unique values in the row, column, and sub cell shared with a given cell.

Don’t worry about it picking up the 0’s here, as we handle those in a later step.

For our previous example, we’d expect this:

The unique values:

Row: 5,6,7,8
Column: 1,5
Sub cell: 1,2,3,5,8
Overall: 1,2,3,5,6,7,8

For this cell we’d want to store 4,9 as the only possible values, given they’re the only numbers from 1–9 that don’t appear in our row/column/sub cell unique list.

If we find a cell that has only one possible value, we want to write that value to the cell.