Solving Expert-Level Sudoku Puzzles Quickly Using Python's Backtracking Algorithm

I often play Sudoku in my leisure time as a form of relaxation. My usual method involves eliminating duplicates and filling in unique numbers first, then proceeding step by step. However, it’s inevitable to guess numbers and adjust based on feedback. So, is there a better algorithm to solve Sudoku puzzles? Here, I will use the backtracking method in Python to solve 9x9 expert-level Sudoku puzzles. The backtracking method employs a trial-and-error approach, attempting to solve a problem step by step. If, during the process, it discovers that the current partial solution won’t lead to a valid answer, it undoes the last step, or even several previous steps, and tries other possible partial solutions to find the answer. Backtracking is typically implemented using simple recursion. Our steps to solve Sudoku with Python are as follows:

Steps:

Represent the Sudoku board as an array.
Find the empty cells to fill.
Print the current Sudoku board.
Determine possible valid numbers for the current cell.
Validate the current number based on the Sudoku rules.
If valid, move to the next empty cell; if not, backtrack to the previous cell. If all cells are filled, a solution has been found.

Representing the Sudoku Board as an Array

A Sudoku board is a grid, so it can be represented as a two-dimensional array. For convenience, here’s an example:

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

A 0 indicates an empty cell that needs to be filled, while other numbers represent existing values.

Finding Empty Cells to Fill

The first step is to manually input the Sudoku puzzle. To find empty cells, we simply look for 0s in the array. We’ll fill them one by one, from left to right, top to bottom. Each time, we find a single empty cell. Here’s the code:

def find_empty(bo):
    for i in range(len(bo)):
        for j in range(len(bo[0])):
            if bo[i][j] == 0:
                return (i, j)  # row, col

    return None

Printing the Current Sudoku Board

We use | and - characters to visually separate the 3x3 blocks. These are inserted when the row or column index is a multiple of 3.

def print_board(bo):
    for i in range(len(bo)):
        if i % 3 == 0 and i != 0:
            print("- - - - - - - - - - - - - ")

        for j in range(len(bo[0])):
            if j % 3 == 0 and j != 0:
                print(" | ", end="")

            if j == 8:
                print(bo[i][j])
            else:
                print(str(bo[i][j]) + " ", end="")

Determining Possible Valid Numbers

All possible numbers are from 1 to 9. If a number already exists in the current cell’s row, column, or 3x3 block, it’s removed from the list of available numbers, leaving only the valid candidates.

def find_possible_valid(bo,pos):

    num_list = list(range(1,10))
    for i in range(9):
        if bo[pos[0]][i]!=0 and bo[pos[0]][i] in num_list:   # row
            num_list.remove(bo[pos[0]][i])
        if bo[i][pos[1]]!=0 and bo[i][pos[1]] in num_list:    # column
            num_list.remove(bo[i][pos[1]])
    x,y = pos[0]//3,pos[1]//3
    for i in range(3*x,3*x+3):        # 3x3 box
        for j in range(3*y,3*y+3):
            if bo[i][j]!=0 and bo[i][j] in num_list:
                num_list.remove(bo[i][j])

    return num_list

Validating Numbers 1-9 Against the Current Sudoku Board

Sudoku rules dictate that no duplicate numbers are allowed in any row or column. If a duplicate is found, False is returned, indicating the current number is invalid.

def valid(bo, num, pos):
    # Check row
    for i in range(len(bo[0])):
        if bo[pos[0]][i] == num and pos[1] != i:
            return False

    # Check column
    for i in range(len(bo)):
        if bo[i][pos[1]] == num and pos[0] != i:
            return False

    # Check box
    x = pos[1] // 3
    y = pos[0] // 3

    for i in range(y*3, y*3 + 3):
        for j in range(x * 3, x*3 + 3):
            if bo[i][j] == num and (i,j) != pos:
                return False

    return True

Moving to the Next Empty Cell or Backtracking

This is the main loop. For each empty cell found, it iterates through the possible candidate numbers. If a number is valid, it attempts to fill the next empty cell recursively. If the recursive call returns True (meaning a solution was found), then the current number is correct, and True is propagated back up. If a number leads to a dead end (the recursive call returns False), the current cell is reset to 0, and the loop continues with the next candidate number for the current cell. This process continues until all empty cells are filled, indicating a solution has been found.

def solve_suduko(bo):
    find = find_empty(bo)
    if not find:
        return True
    else:
        row, col = find

    for i in find_possible_valid(bo,[row,col]):
        if valid(bo, i, (row, col)):
            bo[row][col] = i

            if solve_suduko(bo):
                return True

            bo[row][col] = 0

    return False

Putting all the code together, we get the complete Sudoku solver.

import time
def print_board(bo):
    for i in range(len(bo)):
        if i % 3 == 0 and i != 0:
            print("- - - - - - - - - - - - - ")

        for j in range(len(bo[0])):
            if j % 3 == 0 and j != 0:
                print(" | ", end="")

            if j == 8:
                print(bo[i][j])
            else:
                print(str(bo[i][j]) + " ", end="")

def find_possible_valid(bo,pos):

    num_list = list(range(1,10))
    for i in range(9):
        if bo[pos[0]][i]!=0 and bo[pos[0]][i] in num_list:
            num_list.remove(bo[pos[0]][i])
        if bo[i][pos[1]]!=0 and bo[i][pos[1]] in num_list:
            num_list.remove(bo[i][pos[1]])
    x,y = pos[0]//3,pos[1]//3
    for i in range(3*x,3*x+3):
        for j in range(3*y,3*y+3):
            if bo[i][j]!=0 and bo[i][j] in num_list:
                num_list.remove(bo[i][j])

    return num_list



def find_empty(bo):
    for i in range(len(bo)):
        for j in range(len(bo[0])):
            if bo[i][j] == 0:
                return (i, j)  # row, col

    return None

def solve_suduko(bo):
    find = find_empty(bo)
    if not find:
        return True
    else:
        row, col = find

    for i in find_possible_valid(bo,[row,col]):
        if valid(bo, i, (row, col)):
            bo[row][col] = i

            if solve_suduko(bo):
                return True

            bo[row][col] = 0

    return False


def valid(bo, num, pos):
    # Check row
    for i in range(len(bo[0])):
        if bo[pos[0]][i] == num and pos[1] != i:
            return False

    # Check column
    for i in range(len(bo)):
        if bo[i][pos[1]] == num and pos[0] != i:
            return False

    # Check box
    box_x = pos[1] // 3
    box_y = pos[0] // 3

    for i in range(box_y*3, box_y*3 + 3):
        for j in range(box_x * 3, box_x*3 + 3):
            if bo[i][j] == num and (i,j) != pos:
                return False

    return True
if __name__ == "__main__":
    board = [
    [0,0,1,0,0,3,0,0,0],
    [0,0,0,8,5,0,0,0,0],
    [0,4,0,0,2,6,8,0,0],
    [0,7,9,0,0,5,0,0,2],
    [0,0,2,0,0,0,0,0,0],
    [5,0,0,0,0,0,0,0,4],
    [0,0,0,0,0,0,0,2,7],
    [6,0,0,0,4,0,0,0,0],
    [0,0,0,1,9,0,6,8,0]
]

    print_board(board)
    start_time = time.time()
    solve_suduko(board)
    end_time = time.time()
    print("_____________________________n")
    print_board(board)
    print("time used:{}s".format(end_time-start_time))

Running the code solves an expert-level Sudoku puzzle in less than a second. suduko

Summary:

This article demonstrates how to solve an expert-level Sudoku puzzle in under a second using Python’s backtracking algorithm. By finding possible candidate numbers, we significantly reduce the search space and execution time. While the current implementation requires manually inputting the Sudoku board as an array, a future enhancement could involve using image recognition to automatically capture the board, making it even more convenient to get instant solutions. Remember, the primary goal of Sudoku is to exercise your brain, not to simply find quick answers!