Introduction

Sudoku is a logic-based number placement puzzle. The objective is to fill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 subgrids ("boxes") that compose the grid contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.

This document explains how to solve Sudoku puzzles using a backtracking algorithm, a classic and efficient approach for this type of problem.

Backtracking Explained

Backtracking is a general algorithmic technique for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly lead to a valid solution.

In the context of Sudoku, backtracking involves the following steps:

1. Find an Empty Cell: Locate an unassigned cell (a cell with the value 0 or any other representation of an empty cell).
2. Try Possible Values: For each number from 1 to 9, attempt to place the number in the empty cell.
3. Constraint Checking: Before placing the number, check if it violates any of the Sudoku rules (row, column, or 3x3 box).
4. Recursive Call: If the number is valid, place it and recursively call the solver function to continue filling the grid.
5. Backtrack: If the recursive call doesn't lead to a solution, or if no number from 1 to 9 is valid, reset the cell to empty and backtrack to the previous state to try a different number.
6. Base Case: If there are no more empty cells, it means the Sudoku grid is solved successfully.

Applying Backtracking to Sudoku

Algorithm

1. `solveSudoku(grid)`: This is the main function that takes the Sudoku grid as input.
2. `findEmptyCell(grid)`: Searches the grid for an empty cell (represented typically as 0). Returns the row and column indices as a tuple if found, otherwise returns `None`.
3. `isValid(grid, num, pos)`: Checks if placing the number `num` at position `pos` (row, col) in the `grid` is valid according to Sudoku rules.
   • Row Check: Iterates through the row to check if `num` already exists.
   • Column Check: Iterates through the column to check if `num` already exists.
   • 3x3 Box Check: Calculates the top-left corner of the 3x3 box containing `pos` and checks if `num` exists within that box.
4. Backtracking Steps:
   • Call `findEmptyCell(grid)`. If it returns `None`, the puzzle is solved (base case). Return `True`.
   • If an empty cell is found (row, col):
     • Iterate through numbers 1 to 9.
     • For each number, call `isValid(grid, number, (row, col))`.
     • If `isValid` returns `True`:
       • Place the number in `grid[row][col]`.
       • Recursively call `solveSudoku(grid)`.
         • If the recursive call returns `True`, the puzzle is solved. Return `True`.
         • If the recursive call returns `False`, it means the current assignment didn't lead to a solution. Backtrack: set `grid[row][col] = 0`.
   • If no number from 1 to 9 leads to a solution for this cell, return `False` (backtracking).

Constraint Checking

The core of the backtracking algorithm relies on efficiently checking constraints:

• Row Constraint: Ensures that the same number doesn't appear more than once in a row.
• Column Constraint: Ensures that the same number doesn't appear more than once in a column.
• 3x3 Box Constraint: Ensures that the same number doesn't appear more than once in a 3x3 subgrid.

The isValid function embodies these constraints. It is critical for quickly determining if a potential value violates any of the Sudoku rules, allowing the algorithm to backtrack promptly.

Backtracking Strategies

While the basic backtracking algorithm works, there are strategies to improve its performance:

• Most Constrained Variable (MRV): Instead of picking the first empty cell, choose the cell with the fewest possible values. This reduces the branching factor in the search tree, leading to faster solutions. This requires pre-calculating for each empty cell how many valid choices are available.
• Least Constraining Value (LCV): When choosing which number to try in an empty cell, select the number that eliminates the fewest possible values in the neighboring cells (row, column, box). This helps maintain flexibility for future assignments. This is more complex to implement.
• Forward Checking: After assigning a value to a cell, eliminate that value as a possibility from the domains of its unassigned neighbors (row, column, box). This allows you to detect conflicts earlier and avoid deeper exploration of fruitless branches.

These advanced techniques, particularly MRV and forward checking, can significantly improve the efficiency of the Sudoku solver.

Example (Python)

 def find_empty(board):
    """Finds an empty cell (represented by 0) in the board."""
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] == 0:
                return (i, j)  # row, col
    return None


def is_valid(board, num, pos):
    """Checks if placing num at pos in board is a valid move."""

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

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

    # Check 3x3 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 board[i][j] == num and (i,j) != pos:
                return False

    return True


def solve(board):
    """Solves the Sudoku board using backtracking."""

    find = find_empty(board)
    if not find:
        return True
    else:
        row, col = find

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

            if solve(board):
                return True

            board[row][col] = 0 # Backtrack

    return False


# 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(board):
    for i in range(len(board)):
        print(board[i])
else:
    print("No solution exists")