How to Create Sudoku Solver Python

1. Use Backtracking Algorithm in Python to Solve Sudoku
2. Conclusion

Sudoku is a logic-based number-placement puzzle game that is most popular among persons who are in love with logic and reasoning. Solving sudoku puzzles helps the brain improve concentration and logical thinking.

This article describes how we can solve sudoku using Python.

Use Backtracking Algorithm in Python to Solve Sudoku

When finding solutions for computational problems, the backtracking algorithm is the technique we are frequently using. While solving sudoku, it checks whether the filled boxes’ digits are valid or not.

If it is not valid, it checks other numbers from 1 to 9. If it finds no valid digit, it backtracks to the previous option.

When we reach a dead end and return to the previous choice, we have made and will change our choice, resulting in a different possible solution.

Let’s take the approach of implementing the sudoku solver along with the backtracking algorithm.

First, we have to set up the board by forming the puzzle.

def setBoardFunc(puz):
    global grid
    print("\n---------------Sudoku Solver---------------\n")
    print("Here is the Sudoku Problem :")
    for i in range(0, len(puz), 9):
        row = puz[i : i + 9]
        temp = []
        for block in row:
            temp.append(int(block))
        grid.append(temp)
    printGridFunc()

Here, I have defined a function named setBoardFunc() to form the puzzle. While looping, it sets a 9x9 puzzle and initializes the empty cells with 0.

After completing the functions’ operations, it prints out the input given in the puz. Then we have to print the grid; this step prints out the 9x9 grid with the given inputs.

def printGridFunc():
    global grid
    for row in grid:
        print(row)

Next, we will check whether the current value can place within the current box.

def checkValidFunc(row, column, num):
    global grid
    for i in range(0, 9):
        if grid[row][i] == num:
            return False
    for i in range(0, 9):
        if grid[i][column] == num:
            return False
    square_row = (row // 3) * 3
    square_col = (column // 3) * 3
    for i in range(0, 3):
        for j in range(0, 3):
            if grid[square_row + i][square_col + j] == num:
                return False
    return True

This step checks whether the given number is valid for the particular box. The number should be none of the boxes of the same row, column, or block boxes to place in the current place.

If the number satisfies that requirement and returns true, we can move to the next value; if not, the number gets rejected. Then we have to traverse all blocks adapting to the backtracking algorithm.

def solveFunc():
    global grid
    for row in range(9):
        for column in range(9):
            if grid[row][column] == 0:
                for num in range(1, 10):
                    if checkValidFunc(row, column, num):
                        grid[row][column] = num
                        solveFunc()
                        grid[row][column] = 0
                return
    print("\nSolution for the Sudoku Problem: ")
    printGridFunc()

The latter part of this code chunk checks whether the number is valid or not. Here, it has introduced the function backtracking algorithm.

At first, it searches for an empty cell; if found, the solved sudoku is there, and it prints out the solution of the given sudoku. If it found any empty box, it would guess a number from 1 to 9 through iterating.

If a valid number exists, it calls the solveFunc() and moves to the next empty cell, but if none of the guesses are valid, the previous call of the function will reset the value of the cell to 0 and continue iterating to find the following valid number.

When the algorithm fills up the empty boxes with valid numbers till the dead end, it backtracks the process and re-iterates the whole process. At last, let’s pass the grid and call the function to solve the given sudoku.

puz = (
    "004300209005009001070060043006002087190007400050083000600000105003508690042910300"
)
grid = []
setBoardFunc(puz)
solveFunc()

Complete Source Code:

def setBoardFunc(puz):
    global grid
    print("\n---------------Sudoku Solver---------------\n")
    print("Here is the Sudoku Problem :")
    for i in range(0, len(puz), 9):
        row = puz[i : i + 9]
        temp = []
        for block in row:
            temp.append(int(block))
        grid.append(temp)
    printGridFunc()


def printGridFunc():
    global grid
    for row in grid:
        print(row)


def checkValidFunc(row, column, num):
    global grid
    for i in range(0, 9):
        if grid[row][i] == num:
            return False
    for i in range(0, 9):
        if grid[i][column] == num:
            return False
    square_row = (row // 3) * 3
    square_col = (column // 3) * 3
    for i in range(0, 3):
        for j in range(0, 3):
            if grid[square_row + i][square_col + j] == num:
                return False
    return True


def solveFunc():
    global grid
    for row in range(9):
        for column in range(9):
            if grid[row][column] == 0:
                for num in range(1, 10):
                    if checkValidFunc(row, column, num):
                        grid[row][column] = num
                        solveFunc()
                        grid[row][column] = 0
                return
    print("\nSolution for the Sudoku Problem: ")
    printGridFunc()


puz = (
    "004300209005009001070060043006002087190007400050083000600000105003508690042910300"
)
grid = []
setBoardFunc(puz)
solveFunc()

Output:

Conclusion

Even though there are more ways to solve, using the backtracking algorithm makes the final output of the sudoku more accurate, but it takes more time as it consists of many iterations. However, solving sudoku puzzles improves a person’s logical thinking and is an exciting way to spend leisure time.