Tag: backtracking algorithm

When learning a new programming language, it is always beneficial to tackle a problem that keeps your interest. I always found writing a game usually does it for me. Writing computer games typically involves lots of programming aspects such as user interfaces, data structures, and algorithms.

I really enjoy sudoku puzzles. So while I was learning Python I decided to create a sudoku puzzle solver. There is a lot of Internet literature written on sudoku puzzle solving using the backtracking algorithm.

Sudoku Puzzle

Sudoku is a number placement puzzle that has become popular in the last 10 years. In a “classic” sudoku puzzle there is a 9×9 grid with 9, 3×3 sub-grids. The object is to place a number 1 through 9 in each square. Each number in a row and column in the 9×9 grid must be unique. Also each number in a 3×3 sub-grid must also be unique.

To begin, a partially solved puzzle is provided. Typically the fewer already placed numbers, the harder the puzzle. Each sudoku puzzle is designed to have only a single solution.

Backtracking Algorithm

The backtracking algorithm is a method for solving problems recursively by testing incremental solutions. If the solutions fails, then you “backtrack” the previous solution and attempt another solution.

The backtracking algorithm has been used to solve many problems including the Knight’s Tour Problem, Rat in a Maze, N Queen Problem, Subset Sum, Hamiltonian Cycle, and many others. A cool website, GeeksforGeeks, discusses the backtracking algorithm and application.

To solve a sudoku puzzle using the backtracking algorithm you place a value in the first empty square and test if that solution is valid. If the value is not valid, then the next value is tried. If the test solution is valid, then the next empty square is filled in with a value and then tested until a valid solution is found. This continues until all empty squares have a value.

Python BAcktracking Algorithm

The interface uses Tkinter buttons and creates a 9×9 grid. Code is dedicated for puzzle setup by clicking on a button to enter a known value. Some support functions were also created to check if the placed value is valid for row, column, and sub-grid (square).

The sudoku puzzle is represented as a 2-D array of integer values with 0 being empty. My Python backtracking works a row at a time. A number (1-9) is place in an empty cell and is tested for a valid entry. If the entry is not valid, then the next number is tested. When a number can be placed, the foreground color is changed to blue and the number added as text to the button (cell).

def solvePuzzle(sudoku):
    emptyFound = False
    for row in range(0,9):
        for column in range(0,9):
            if(sudoku[row][column] == 0):
                emptyFound = True
                for num in range(1,10):
                    sudoku[row][column] = num
                    if okRow(sudoku, row):
                        if okColumn(sudoku, column):
                            if okSquare(sudoku, row, column):
                                buttons[(row * 9) + column].configure(fg = 'blue')
                                buttons[(row * 9) + column].configure(text = num)
                                root.update()
                                if solvePuzzle(sudoku):
                                    return True
                                else:
                                    sudoku[row][column] = 0
                            else:
                                sudoku[row][column] = 0
                        else:
                            sudoku[row][column] = 0
                    else:
                        sudoku[row][column] = 0

                # no solution, tried all numbers but failed
                return False
                
    if not emptyFound:
        return True

The code segment below shows testing a row for valid entries. A simple array is used to accumulate the number of times a number is entered in the row. If any entry is greater than 1, then that number was duplicated and the row is not valid.

# check if row is good, number already in row
def okRow(sudoku, row):
    # check for duplicate 1-9 in this row
    check = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]  # count number is row
    for i in range(0, 9):
        check[sudoku[row][i]] += 1
    
    for i in range(1, 10):
        if(check[i] > 1):   # multiples of the same numbers have sum > 1
            return False
    return True

For me, most medium difficult sudoku puzzles are solved in about 10 minutes. Many of the puzzles I have solved using Python take less than 1 second using the backtracking algorithm. The longest solution for an extremely hard puzzle was about 5 minutes.