Skip to content

A Sudoku solver using Python

During this week I was working on one of Project Euler’s problems. The meat of the problem was implementing a Sudoku solver. After much work, I was finally able to program a solver that recursively tried filling the empty cases and tracked back when necessary. In this post we will see how to implement a simple version of the solver.

Note: This solver is a simplified implementation. It will take too long to solve difficult Sudoku puzzles. For a more efficient solution based on this one, see here.

Setting up the Sudoku grid

Sudoku: What is it?

If you’re not familiar with it, Sudoku is a mathematical puzzle where you have a 9×9 grid partially filled with digits from 1 to 9. The grid is also divided into nine 3×3 sub-grids. The goal is to fill the grid’s empty cases, having each digit between 1-9 appear only once in each row, column and 3×3 sub-grid.

Using Numpy for the grid

For the 9×9 grid, we will use Numpy arrays (the experience I got using Numpy to implement a tic-tac-toe board came in handy here). We will use as input a string of digits. Empty cases will be denoted by 0 and each line of the string will represent a row of the grid. That means we will have 9 lines of 9 digits each. As an example, we will work with:

puzzle = """043080250
            600000000
            000001094
            900004070
            000608000
            010200003
            820500000
            000000005
            034090710"""

We can populate the 9×9 Sudoku grid with the following function:

def create_grid(puzzle_str):
    # Deleting whitespaces and newlines (\n)
    lines = puzzle_str.replace(' ','').replace('\n','')
    # Converting it to a list of digits
    digits = list(map(int, lines))
    # Turning it to a 9x9 numpy array
    grid = np.array(digits).reshape(9,9)
    return grid

Which will return the grid as expected:

>>> grid = create_grid(puzzle)
array([[0, 4, 3, 0, 8, 0, 2, 5, 0],
       [6, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 1, 0, 9, 4],
       [9, 0, 0, 0, 0, 4, 0, 7, 0],
       [0, 0, 0, 6, 0, 8, 0, 0, 0],
       [0, 1, 0, 2, 0, 0, 0, 0, 3],
       [8, 2, 0, 5, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 5],
       [0, 3, 4, 0, 9, 0, 7, 1, 0]])

Dividing into sub-grids

Part of the analysis has to do with checking the values of each sub-grid. We can group the values of each 3×3 sub-grid as follows:

def get_subgrids(grid):
    subgrids = []
    for box_i in range(3):
        for box_j in range(3):
            subgrid = []
            for i in range(3):
                for j in range(3):
                    subgrid.append(grid[3*box_i + i][3*box_j + j])
            subgrids.append(subgrid)
    return np.array(subgrids)

This will return the following sub-grids for our original puzzle:

>>> subgrids = get_subgrids(grid)
array([[0, 4, 3, 6, 0, 0, 0, 0, 0],
       [0, 8, 0, 0, 0, 0, 0, 0, 1],
       [2, 5, 0, 0, 0, 0, 0, 9, 4],
       [9, 0, 0, 0, 0, 0, 0, 1, 0],
       [0, 0, 4, 6, 0, 8, 2, 0, 0],
       [0, 7, 0, 0, 0, 0, 0, 0, 3],
       [8, 2, 0, 0, 0, 0, 0, 3, 4],
       [5, 0, 0, 0, 0, 0, 0, 9, 0],
       [0, 0, 0, 0, 0, 5, 7, 1, 0]])

See that we’re dividing the original grid into groups of 3×3 sub-grids from left to right, top to bottom.

Getting case candidates

We know that each digit can occur only once for each row, column and sub-grid. That means that each case can be filled with digits that don’t appear in the case’s row, column and sub-grid. We will call that set of options “candidates”.

The following function implements this idea:

def get_candidates(grid):
    # Helper function
    def subgrid_index(i, j):
        return (i//3) * 3 + j // 3
    subgrids = get_subgrids(grid)
    candidates = []
    for i in range(9):
        row_candidates = []
        for j in range(9):
            # Row, column and subgrid digits
            row = set(grid[i])
            col = set(grid[:, j])
            sub = set(subgrids[subgrid_index(i, j)])
            common = row | col | sub
            candidates = set(range(10)) - common
            # If the case is filled take its value as the only candidate
            if not grid[i][j]:
                row_candidates.append(list(candidates))
            else:
                row_candidates.append([grid[i][j]])
        candidates.append(row_candidates)
    return candidates

We have used Python set’s operations to handle the candidates. If you aren’t familiar with them, you can see a worked example here.

The candidates are implemented as nested lists. We made use of the helper function subgrid_index that returns the corresponding sub-grid index for the i and j indices of the grid’s case.

Sudoku subgrids

This function returns the following candidates for our current puzzle:

>>> candidates = get_candidates(grid)
[[[1, 7], [4], [3], [9, 7], [8], [9, 6, 7], [2], [5], [1, 6, 7]],
 [[6], [8, 9, 5, 7], [1, 2, 5, 7, 8, 9], [9, 3, 4, 7], [2, 3, 4, 5, 7], [2, 3, 5, 7, 9], [8, 1, 3], [8, 3], [8, 1, 7]],
 [[2, 5, 7], [8, 5, 7], [8, 2, 5, 7], [3, 7], [2, 3, 5, 6, 7], [1], [8, 3, 6], [9], [4]],
 [[9], [8, 5, 6], [8, 2, 5, 6], [1, 3], [1, 3, 5], [4], [8, 1, 5, 6], [7], [8, 1, 2, 6]],
 [[2, 3, 4, 5, 7], [5, 7], [2, 5, 7], [6], [1, 3, 5, 7], [8], [1, 4, 5, 9], [2, 4], [1, 2, 9]],
 [[4, 5, 7], [1], [8, 5, 6, 7], [2], [5, 7], [9, 5, 7], [4, 5, 6, 8, 9], [8, 4, 6], [3]],
 [[8], [2], [1, 9, 6, 7], [5], [1, 3, 4, 6, 7], [3, 6, 7], [9, 3, 4, 6], [3, 4, 6], [9, 6]],
 [[1, 7], [9, 6, 7], [1, 9, 6, 7], [1, 3, 4, 7, 8], [1, 2, 3, 4, 6, 7], [2, 3, 6, 7], [3, 4, 6, 8, 9], [2, 3, 4, 6, 8], [5]],
 [[5], [3], [4], [8], [9], [2, 6], [7], [1], [8, 2, 6]]]

For instance, the case at the 3th row (i = 2) and the 1st column (j = 0) could be filled with any of the digits candidates[i][j]. That means any of the digits in the list [2, 5, 7].

Filling single candidates

Once we have generated the candidates for each case, we will see that some of them can be filled by only a single candidate. We will start filling the grid with those “single candidates”.

def fill_singles(grid):
    grid = grid.copy()
    candidates = get_candidates(grid)
    any_fill = True
    while any_fill:
        any_fill = False
        for i in range(9):
            for j in range(9):
                if len(candidates[i][j]) == 1 and grid[i][j] == 0:
                    grid[i][j] = candidates[i][j][0]
                    candidates = get_candidates(grid)
                    any_fill = True

    return grid

This function is implemented in a loop. Every time we fill any case, we generate a new set of possible candidates until there aren’t any new filled cases.

When we apply this function to our grid, we get:

>>> fill_singles(grid)
array([[ 0 , 4, 3,  0 , 8, 0, 2, 5, 0],
       [ 6 , 0, 0,  0 , 0, 0, 0, 0, 0],
       [ 0 , 0, 0,  0 , 0, 1, 0, 9, 4],
       [ 9 , 0, 0,  0 , 0, 4, 0, 7, 0],
       [ 0 , 0, 0,  6 , 0, 8, 0, 0, 0],
       [ 0 , 1, 0,  2 , 0, 0, 0, 0, 3],
       [ 8 , 2, 0,  5 , 0, 0, 0, 0, 0],
       [ 0 , 0, 0,  0 , 0, 0, 0, 0, 5],
       [*5*, 3, 4, *8*, 9, 0, 7, 1, 0]])

I have enclosed the new inputs with asterisks to remark them. We have only two new values filled in this case. But the fill_singles function alone will be able to solve some of the easiest Sudoku puzzles!

Once we’re stuck solving Sudoku puzzles, like in this case, we will use a recursive approach.

Recursive Sudoku solver

To implement a Sudoku solver, we will follow four steps:

  1. Fill cases with only one candidate.
  2. If the grid is completely filled, return it.
  3. Check if the current grid is “valid”. If it isn’t erase the last guess and continue with the next guess.
  4. If the current grid is both incomplete and “valid”, fill one case with a guess and go back to 1.

The fill_singles function of the last section takes care of the first step. Let’s see how to implement the other steps.

Verifying a solution

The solver will return a grid when it’s completely filled. A solution verifies that all rows, columns and sub-grids have only one occurrence of the digits 1 to 9:

def is_solution(grid):
    if np.all(np.sum(grid, axis=1) == 45) and \
       np.all(np.sum(grid, axis=0) == 45) and \
       np.all(np.sum(get_subgrids(grid), axis=1) == 45):
        return True
    return False

With this function, we indirectly verify the uniqueness of each digit by taking the sum of the grid values along each row, column and sub-grid. If we sum the digits 1 to 9, we get 45.

Invalid guess

We will know when to backtrack when we reach a Sudoku grid that has a cell that can’t be filled with any value. For example, this could happen if by checking the possible candidates in a cell’s row, we can fill it only with the digit 5 but that digit is already part of its corresponding column or sub-grid. This no-solution situations will arise as empty list candidates. We can easily check for them with:

def is_valid_grid(grid):
    candidates = get_candidates(grid)
    for i in range(9):
        for j in range(9):
            if len(candidates[i][j]) == 0:
                return False
    return True

Making a guess

Whenever we reach a point where we can’t further fill the Sudoku grid by filling single candidates, we will fill a case by guessing which one of its candidates is the correct one. In order to increase the chances of guessing correctly, the guess will be taken from a case that has the least number of possible candidates. Then we will try to find a solution for the grid with the “guessed” value.

def make_guess(grid):
    grid = grid.copy()
    candidates = get_candidates(grid)
    # Getting the shortest number of candidates > 1:
    min_len = sorted(list(set(map(
        len, np.array(candidates).reshape(1,81)[0]))))[1]
    for i in range(9):
        for j in range(9):
            if len(candidates[i][j]) == min_len:
                for guess in candidates[i][j]:
                    grid[i][j] = guess
                    solution = solve(grid)
                    if solution is not None:
                        return solution
                    # Discarding incorrect guess
                    grid[i][j] = 0

The recursive step takes place here, when we call the solve function that restarts the process of attempting a solution on a new grid. The failing condition of the solve function will return a None object, at which point the grid will revert back the changes on the grid and continue with the next possible guesses.

Finally, let’s see how the solve function puts it all together.

Recursive solver

The solver follows the steps described at the beginning of this section:

def solve(grid):
    grid = fill_singles(grid)
    if is_solution(grid):
        return grid
    if not is_valid_grid(grid):
        return None
    return make_guess(grid)

The recursive step and the track back takes place inside the make_guess function. We have seen this function will call the solve function again, but on a new grid and revert the changes on failure.

Applying the solve function on our puzzle, we get:

>>> solve(create_grid(puzzle))
array([[1, 4, 3, 9, 8, 6, 2, 5, 7],
       [6, 7, 9, 4, 2, 5, 3, 8, 1],
       [2, 8, 5, 7, 3, 1, 6, 9, 4],
       [9, 6, 2, 3, 5, 4, 1, 7, 8],
       [3, 5, 7, 6, 1, 8, 9, 4, 2],
       [4, 1, 8, 2, 7, 9, 5, 6, 3],
       [8, 2, 1, 5, 6, 7, 4, 3, 9],
       [7, 9, 6, 1, 4, 3, 8, 2, 5],
       [5, 3, 4, 8, 9, 2, 7, 1, 6]])

Which successfully returns a solution to the Sudoku puzzle!

Final analysis and conclusion

The solver implemented in this post, will perform a depth-first search of the viable options to solve the Sudoku puzzle. In the worst case scenario, it will traverse most possible combinations of candidates, discarding some as it fills the grid. This makes it an exponential algorithm. Due to the exponential increase of complexity, this solver will take too long to solve harder Sudoku puzzles. For those puzzles, the candidate combinations should be filtered more efficiently before attempting the recursive step.

Published inProgramming
Subscribe
Notify of
guest
2 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
sudoku tool
10 months ago

You can use this sudoku solver to help you solve your puzzle in an easy way

Sudoku
5 months ago
Reply to  sudoku tool

They have other social media in here: Sudoku solver