Building a Sudoku Solver and Generator in Python (1/3)

Note, this article was originally uploaded to Medium.

Introduction

In this 3-part tutorial, I will show you how you can create your own sudoku ‘engine’ which is capable of solving and generating sudoku's in pure Python with no external libraries. Please keep in mind that the algorithms I will show you today are very greedy and not the fastest approach. If you want to create a fast sudoku solver/generator then consider using a faster programming language such as C. This tutorial is meant for those who have a basic understanding of Python but try to follow along anyways. Click this link to check out the Github repo!

Here are a list of contents for the next 3 parts of this tutorial:

1. Introduction and creation of the solver (Here)
2. Starting the generator 1
3. Finishing the generator 2

Note

These are the average times it took to generate a sudoku at each difficulty level over 100 sudokus generated*:

• Easy (0): 0.221s
• Medium (1): 2.107s
• Hard (2): 20.466s

* These times were recorded on my PC (Ryzen 5 3600X cpu, 24GB DDR4 ram, RX590 gpu) and might differ to the times you experience on your computer.

What is sudoku?

Sudoku is a logical-thinking game where you need to fill a 9x9 grid with numbers according to 3 strict rules:

1. There is a 9x9 grid, each must be filled with a number ranging from 1–9
2. You cannot have the same number twice in a single row or column
3. You cannot have the same number in the same internal box (3x3 section)

In the diagram on the left, you can see a 9x9 sudoku board split up into 9 internal boxes.

If you are trying to place a number in the centre-most square, then that number cannot exist in the green boxes (row), the pink boxes (column) and the blue boxes (internal box).

If this is your first time encountering sudoku, I highly recommend you play a few games here to familiarise yourself with the game and how it works.

Creating the main program

The first thing we need to do is create a method of representing a sudoku board with an easy-to-understand way for the computer and for us humans. A board can be represented by a 2D array within python using lists. This makes it very easy for us to change and edit the individual cells on the board as we can simply call the index values of the cell we want to edit.

A board can also be described as a string, this makes it convenient to pass around and even save to files if needed for later use. The string will be the whole sudoku board where the start of the string will be the top left of the board and work its way from left-right and eventually downwards to the bottom right of the board. In both cases, empty squares will be represented by a 0.

We will start by importing the two required built-in modules, copy and random. Then we can start creating a class which will represent the sudoku board, this is where everything will be ‘housed’:

# sudoku.py

import copy
import random


class Board:
    def __init__(self, code=None):
        self.__resetBoard()

        if code:
            self.code = code

            for row in range(9):
                for col in range(9):
                    self.board[row][col] = int(code[0])
                    code = code[1:]
        else:
            self.code = None

Here in this code snippet we create the Board class as well as the magic init method, this is automatically called instantly when a new object is created. Inside the init method, we will first create an empty board by calling the private resetBoard method. Private methods are notated by the double underscore in front of their names. If a board code is passed in as a parameter, then the board will be populated based on the code inputted.

The next method to implement is the resetBoard method. This is relatively simple as it simply assigns the board attribute of our Board class to an empty 9x9 list filled with zeros depicting empty squares:

# sudoku.py

def __resetBoard(self): # resets the board to an empty state
    self.board = [
        [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],
    ]

    return self.board

We also need a way to convert a board into a code, therefore we are going to implement the boardToCode method next with an optional input_board parameter:

# sudoku.py

def boardToCode(self, input_board=None): # turn a pre-existing board into a code
    if input_board:
        _code = ''.join([str(i) for j in input_board for i in j])
        return _code
    else:
        self.code = ''.join([str(i) for j in self.board for i in j])
        return self.code

In this simple method, we iterate through each object in each inner list of our board, convert it into a string and append it to the end of an empty string.

Final thoughts

That was part 1 of 3 of my sudoku solver and generator series, in the next part we will be discussing how to solve a sudoku board using recursion. If you have any thoughts, tips or questions then please feel free to leave a comment below!

Click here for part 2.

Thank you for reading part 1! 💖