ECX 30 Days of Code and Design

Day 30

Sudoku Solver

Task

Write a function that takes in a 9×9 array of numbers. Let this list represent a partially filled grid of numbers (specifically; integers ranging from 1 to 9, where "0" signifies an empty space in the grid) as parameters, and return a filled 9×9 array, the solution to it. If there are no solutions, return False.

Exceptions:

If an empty list or an invalid list (list with numbers outside the 1-9 range, or empty lists, or a list of the wrong size, etc.) is input, it issues a warning. Hint: Backtracking is one effective method for solving this problem—it is however not the only method.

The problem is further explained below.
Given a partially filled 9×9 list, the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and sub-grid of size 3×3 contains exactly one instance of the digits from 1 to 9.

My Approach

Full Code

This is the full code below. I will explain it in bits throughout this article.

def is_valid_move(grid, row, col, number):
    """Checks if the number inputted is a valid move."""

    # Check the row for repeated number
    for x in range(9):
        if grid[row][x] == number:
            return False

    # Check the columns for repeated number
    for x in range(9):
        if grid[x][col] == number:
            return False

    # Check the 3 by 3 square for repeated number
    corner_row = row - row % 3
    corner_col = col - col % 3

    for x in range(3):
        for y in range(3):
            if grid[corner_row + x][corner_col + y] == number:
                return False

    return True


def solve(grid, row, col):
    """Solves the sudoku"""
    try:  # This handles a wrong type found in the grid

        # If we are at the last column and row, and all digits have been inputted,
        # the board is filled and the game ends
        if col == 9:
            if row == 8:
                return True

            # This takes us to the beginning of a new row when col = 9
            row += 1
            col = 0

        # Recurse the function if the cell is not empty (that it is not empty).
        if grid[row][col] > 0:
            return solve(grid, row, col + 1)

        # Try the numbers 1 - 9 in an empty slot (slot having the number 0).
        for num in range(1, 10):

            # Check if the number is valid and enter the valid number into the cell
            if is_valid_move(grid, row, col, num):

                grid[row][col] = num

                if solve(grid, row, col + 1):
                    return True

            grid[row][col] = 0

        return False

    except TypeError:
        print('Invalid input!')


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


# Function to print board
def print_board():
    """Prints the sudoku board"""
    print(' Sudoku Board '.center(21, '*'))

    for i in range(9):
        for j in range(9):
            print(grids[i][j], end=' ')

            if (j + 1) % 3 == 0 and j != 8:
                print('|', end=' ')

        print()

        if (i + 1) % 3 == 0 and i != 8:
            print('---------------------')

        if i == 8:
            print('\n')


# Function call
print_board()

if solve(grids, 0, 0):
    print(' Solved Board '.center(21, '*'))

    for k in range(9):
        for l in range(9):
            print(grids[k][l], end=' ')

            if (l + 1) % 3 == 0 and l != 8:
                print('|', end=' ')

        print()

        if (k + 1) % 3 == 0 and k != 8:
            print('---------------------')

else:
    print('No Solution For This Sudoku')

Function to Check if an Input Can Be in a Cell

First, we define a function, is_valid_move(), which is used to check if a number is already in a given row, column, or 3 by 3 small square. corner_row = row - row % 3 and corner_col = col - col % 3 is used to define our 3 by 3 square; for example, if we are to input a number in row 7 and column 4, corner_row = row - row % 3 ( 7 – (7%3) = 7 – 1 = 6) and corner_row = row - row % 3 (4 – (4%3) = 4 – 1 = 3) takes us to the beginning of the small square and using two for loops at a range of 3, we check if the number we are inputting is already within the square. If the number is either within the square, the row, or the column, we return False, else, we return True.

def is_valid_move(grid, row, col, number):
    """Checks if the number inputted is a valid move."""

    for x in range(9):
        if grid[row][x] == number:
            return False

    for x in range(9):
        if grid[x][col] == number:
            return False

    corner_row = row - row % 3
    corner_col = col - col % 3

    for x in range(3):
        for y in range(3):
            if grid[corner_row + x][corner_col + y] == number:
                return False

    return True

Function to Solve the Sudoku

Next, we define the function which solves the sudoku board. Using an if statement, we check if the board has already been solved. When col = 9 and row = 8 it means the whole board has been filled. But if row != 8 and col = 9, it means that we have exceeded that row, thus we move to the next row. Using grid[row][col] > 0:, we check if the slot is empty (as 0 indicates an unfilled space); if it is not empty, we move to the next column in that row by recursing solve(grid, row, col + 1), but if it is empty, we would call is_valid_move() function and check from 1 to 9 which of the numbers is a valid move in that space. We would wrap the code in a try except block to handle values other than integers.

def solve(grid, row, col):
    """Solves the sudoku"""
    try: 

        if col == 9:
            if row == 8:
                return True

            row += 1
            col = 0

        if grid[row][col] > 0:
            return solve(grid, row, col + 1)

        for num in range(1, 10):

            if is_valid_move(grid, row, col, num):

                grid[row][col] = num

                if solve(grid, row, col + 1):
                    return True

            grid[row][col] = 0

        return False

    except TypeError:
        print('Invalid input!')

Sudoku Board Input

Next, we store the sudoku board in a variable, grids, using nested lists.

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

Function to Display the Sudoku Board

Next, we define a function, print_board(), which prints the above board in a pretty format. After every 3 numbers, a pipe (|) is printed to demarcate the square. Also, after every 3 columns, dashes (------) are printed.

def print_board():
    """Prints the sudoku board"""
    print(' Sudoku Board '.center(21, '*'))

    for i in range(9):
        for j in range(9):
            print(grids[i][j], end=' ')

            if (j + 1) % 3 == 0 and j != 8:
                print('|', end=' ')

        print()

        if (i + 1) % 3 == 0 and i != 8:
            print('---------------------')

        if i == 8:
            print('\n')


print_board()

Displaying the Solved Sudoku Board

Finally, using an if statement we check if the sudoku grid was solvable, if yes, we print it out in a pretty format; else, we display on the screen that there is no solution for the sudoku.

if solve(grids, 0, 0):
    print(' Solved Board '.center(21, '*'))

    for k in range(9):
        for l in range(9):
            print(grids[k][l], end=' ')

            if (l + 1) % 3 == 0 and l != 8:
                print('|', end=' ')

        print()

        if (k + 1) % 3 == 0 and k != 8:
            print('---------------------')

else:
    print('No Solution For This Sudoku')

There you have it. In case of questions and suggestions, kindly drop a comment. Thank you.

Run the code on Replit.

Creating a Sudoku Solver Using Python

Table of contents