Backtracking And Branch And Bound Algorithm Sudoku Solver Complete Guide

Last Update:2025-06-22T00:00:00 .NET School AI Teacher - SELECT ANY TEXT TO EXPLANATION. 8 mins read Difficulty-Level: beginner

Understanding the Core Concepts of Backtracking and Branch and Bound Algorithm Sudoku Solver

Backtracking and Branch and Bound Algorithm Sudoku Solver

Backtracking Algorithm

Explanation:

Backtracking is a depth-first search algorithm used to solve Sudoku. It systematically explores all possible configurations of a puzzle, starting from an initial configuration and expanding it incrementally until a solution is found or it determines that no solution exists. If a configuration doesn't lead to a solution, backtracking removes the last choice and tries a different possibility. This process continues until the solution is found or exhaustively all possibilities are explored.

Key Steps in Backtracking:

Identify an Empty Spot: Traverse the grid to find an empty cell (represented by 0).
Attempt to Fill the Spot: Try placing digits 1 through 9 in the empty spot.
Check Validity: Ensure that the digit placement does not violate Sudoku rules (i.e., no repeated digits in the same row, column, or 3x3 subgrid).
Recursive Call: If the digit is valid, make a recursive call to attempt solving the rest of the grid.
Unmake Choices: If placing a digit does not lead to a solution, backtrack by undoing the choice and trying the next digit.

Example Code Snippet (Python):

def is_safe(board, row, col, num):
    # Check if the number is not repeated in the current row, column, and sub-grid
    for i in range(9):
        if board[row][i] == num or board[i][col] == num or board[row - row % 3 + i // 3][col - col % 3 + i % 3] == num:
            return False
    return True

def solve_sudoku(board):
    empty = find_empty_location(board)
    if not empty:
        return True
    row, col = empty

    for num in range(1, 10):
        if is_safe(board, row, col, num):
            board[row][col] = num

            if solve_sudoku(board):
                return True

            board[row][col] = 0  # Backtrack

    return False

def find_empty_location(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return (i, j)
    return None

Branch and Bound Algorithm

Explanation:

Branch and Bound (B&B) is an optimization algorithm that incrementally builds candidates for the solution and abandons a candidate as soon as it determines that the candidate cannot possibly lead to a better solution than the best one found so far. In the context of Sudoku, B&B can be seen as an enhancement over Backtracking, employing bounding (pruning) techniques to reduce the search space.

Key Steps in Branch and Bound:

Identify a Candidate: Select a cell from the grid to fill.
Generate Candidates: Generate all possible valid numbers that can be placed in the selected cell.
Bounding: Evaluate the current state and apply pruning rules to eliminate unlikely candidates. B&B uses heuristics such as the Minimum Remaining Values (MRV) heuristic to focus on cells that offer the most constraints.
Recursive Exploration: Recursively apply the algorithm to the subproblems resulting from candidate placements.
Optimal Solution: Continue exploring until an optimal solution is found or all possibilities are exhausted.

Example Code Snippet (Python):

Implementing Branch and Bound for Sudoku is more complex and typically involves a more sophisticated data structure to manage the bounding process. Here's a simplified version demonstrating the concept:

Online Code run

🔔 Note: Select your programming language to check or run code at

💻 Run Code Compiler

Step-by-Step Guide: How to Implement Backtracking and Branch and Bound Algorithm Sudoku Solver

Backtracking Algorithm for Sudoku Solver

Backtracking is a systematic way of using a brute force approach to try all possible combinations and backtrack when a solution is no longer feasible.

Step-by-Step Example:

Start with an Initial Grid: Consider a partially filled Sudoku grid:

5 3 _ _ 7 _ _ _ _
6 _ _ 1 9 5 _ _ _
_ 9 8 _ _ _ _ 6 _
8 _ _ _ 6 _ _ _ 3
4 _ _ 8 _ 3 _ _ 1
7 _ _ _ 2 _ _ _ 6
_ 6 _ _ _ _ 2 8 _
_ _ _ 4 1 9 _ _ 5
_ _ _ _ 8 _ _ 7 9

Locate an Empty Cell: Find the first empty cell (represented by _), starting from the top-left corner.
Try Possible Numbers: Attempt to place numbers 1 through 9 in the empty cell, checking if it is safe to place the number (no conflicts with the same row, column, or 3x3 box).
Backtrack if Conflict: If placing a number causes a conflict, remove the number and try the next possibility. If all numbers 1 through 9 cause a conflict, backtrack to the previous cell and try a different number there.
Repeat Until the Grid is Filled: Continue this process until the entire grid is filled without any conflicts.

Complete Code Example in Python:

def is_safe(board, row, col, num):
    # Check if the number is not repeated in the current row
    for x in range(9):
        if board[row][x] == num:
            return False

    # Check if the number is not repeated in the current column
    for x in range(9):
        if board[x][col] == num:
            return False

    # Check if the number is not repeated in the current 3x3 box
    start_row = row - row % 3
    start_col = col - col % 3
    for i in range(3):
        for j in range(3):
            if board[i + start_row][j + start_col] == num:
                return False

    return True

def solve_sudoku(board):
    empty = find_empty_location(board)
    if not empty:
        return True  # Puzzle solved

    row, col = empty

    for num in range(1, 10):
        if is_safe(board, row, col, num):
            board[row][col] = num

            if solve_sudoku(board):
                return True

            board[row][col] = 0  # Backtrack

    return False

def find_empty_location(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return (i, j)
    return None

def print_board(board):
    for row in board:
        print(" ".join(str(num) for num in row))

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

if solve_sudoku(board):
    print_board(board)
else:
    print("No solution exists")

Branch and Bound Algorithm for Sudoku Solver

Branch and Bound is an optimization method that seeks a solution within a defined branch of possible solutions and discards branches that are not feasible.

Step-by-Step Example:

Start with an Initial Grid: Use the same partially filled Sudoku grid.
Calculate Lower Bound: For each empty cell, calculate a lower bound by finding the smallest number of candidate values that can be placed in the cell while maintaining the Sudoku rules.
Choose the Best Candidate: Use a priority queue to select the empty cell with the lowest number of candidate values.
Explore Branches: Attempt to place each candidate value in the selected cell and recursively attempt to solve the resulting subproblem.
Bound: If a candidate value leads to a conflict or a subproblem that cannot be solved, discard the branch and backtrack to the previous state.
Repeat Until the Grid is Filled: Continue this process until the entire grid is filled without any conflicts.

Complete Code Example in Python:

Top 10 Interview Questions & Answers on Backtracking and Branch and Bound Algorithm Sudoku Solver

Backtracking And Branch And Bound Algorithm Sudoku Solver Complete Guide