Sudoku Solver with Step Explanation

 import copy

# ---------------------------------

# Helper Functions

# ---------------------------------

def print_board(board):

    for i in range(9):

        row = ""

        for j in range(9):

            row += str(board[i][j]) + " "

            if j % 3 == 2 and j != 8:

                row += "| "

        print(row)

        if i % 3 == 2 and i != 8:

            print("-" * 21)

    print()

def find_empty(board):

    for r in range(9):

        for c in range(9):

            if board[r][c] == 0:

                return r, c

    return None

def is_valid(board, num, row, col):

    # Row

    if num in board[row]:

        return False

    # Column

    for r in range(9):

        if board[r][col] == num:

            return False

    # 3x3 box

    box_row = (row // 3) * 3

    box_col = (col // 3) * 3

    for r in range(box_row, box_row + 3):

        for c in range(box_col, box_col + 3):

            if board[r][c] == num:

                return False

    return True

# ---------------------------------

# Constraint Propagation

# ---------------------------------

def get_candidates(board, row, col):

    return [num for num in range(1, 10) if is_valid(board, num, row, col)]

def apply_constraint_propagation(board, steps):

    changed = True

    while changed:

        changed = False

        for r in range(9):

            for c in range(9):

                if board[r][c] == 0:

                    candidates = get_candidates(board, r, c)

                    if len(candidates) == 1:

                        board[r][c] = candidates[0]

                        steps.append(

                            f"Naked Single: Placed {candidates[0]} at ({r+1},{c+1})"

                        )

                        changed = True

    return board

# ---------------------------------

# Backtracking with Explanation

# ---------------------------------

def solve(board, steps):

    board = apply_constraint_propagation(board, steps)

    empty = find_empty(board)

    if not empty:

        return True

    row, col = empty

    candidates = get_candidates(board, row, col)

    for num in candidates:

        steps.append(f"Trying {num} at ({row+1},{col+1})")

        board[row][col] = num

        if solve(board, steps):

            return True

        steps.append(f"Backtracking from ({row+1},{col+1})")

        board[row][col] = 0

    return False

# ---------------------------------

# Example Puzzle

# ---------------------------------

if __name__ == "__main__":

    puzzle = [

        [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],

    ]

    print("Initial Puzzle:\n")

    print_board(puzzle)

    steps = []

    board_copy = copy.deepcopy(puzzle)

    if solve(board_copy, steps):

        print("Solved Puzzle:\n")

        print_board(board_copy)

        print("Step-by-Step Explanation:\n")

        for step in steps:

            print(step)

    else:

        print("No solution found.")