Skip to content
TheChatArchiveThe Chat Archive
Grok 4.1 Fast· xaiHugging Face Frontier Reasoning Traces

Generate Python code to solve a Sudoku puzzle using a backtracking algorithm.

  1. User

    Generate Python code to solve a Sudoku puzzle using a backtracking algorithm.

  2. Assistant
    def print_board(board):
        """Print the Sudoku board in a nicely formatted way."""
        for i in range(9):
            if i % 3 == 0 and i != 0:
                print("-" * 21)
            for j in range(9):
                if j % 3 == 0 and j != 0:
                    print(" | ", end="")
                print(board[i][j], end=" ")
            print()
    
    def is_valid(board, row, col, num):
        """Check if placing num at board[row][col] is valid."""
        # Check row
        for x in range(9):
            if board[row][x] == num:
                return False
        # Check column
        for x in range(9):
            if board[x][col] == num:
                return False
        # Check 3x3 box
        start_row = row // 3 * 3
        start_col = col // 3 * 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):
        """Solve the Sudoku puzzle using backtracking."""
        # Find an empty cell
        row, col = find_empty(board)
        if row == -1:  # No empty cells, puzzle solved
            return True
        
        # Try numbers 1-9
        for num in range(1, 10):
            if is_valid(board, row, col, num):
                board[row][col] = num  # Place number
                if solve_sudoku(board):  # Recurse
                    return True
                board[row][col] = 0  # Backtrack
        
        return False  # No solution found
    
    def find_empty(board):
        """Find the next empty cell (0). Return (row, col) or (-1, -1) if none."""
        for i in range(9):
            for j in range(9):
                if board[i][j] == 0:
                    return i, j
        return -1, -1
    
    # Example Sudoku puzzle (0 represents empty cells)
    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("Original puzzle:")
    print_board(puzzle)
    
    if solve_sudoku(puzzle):
        print("\nSolved puzzle:")
        print_board(puzzle)
    else:
        print("No solution exists.")
    

    How it works:

    • print_board: Displays the 9x9 grid with lines for readability.
    • is_valid: Checks if a number can be placed without violating Sudoku rules (row, column, 3x3 subgrid).
    • find_empty: Locates the next empty cell (0).
    • solve_sudoku: Core backtracking function. Tries numbers 1-9 in empty cells recursively. Backtracks on failure.
    • The puzzle is solved in-place (modifies the original list).

    Run this code to see the unsolved and solved boards. You can replace puzzle with any valid Sudoku grid!

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.