Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· OpenAIHugging Face Arena Human Preference 55K

Python Sudoku solver recursive backtracking

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Mistralmistral-medium’s answer.
  1. User

    Python Sudoku solver recursive backtracking

  2. Assistant

    Sure! Here's an example of a Python Sudoku solver using recursive backtracking:

    def solve_sudoku(board):
        # Find the next empty cell on the board
        row, col = find_empty_cell(board)
        
        # If there are no more empty cells, the board is solved
        if row == -1 and col == -1:
            return True
        
        # Try placing numbers 1-9 in the empty cell
        for num in range(1, 10):
            if is_valid(board, row, col, num):
                # Place the number in the empty cell
                board[row][col] = num
                
                # Recursively solve the board
                if solve_sudoku(board):
                    return True
                
                # If the board cannot be solved, backtrack and try a different number
                board[row][col] = 0
        
        # If no number works in the current cell, the board cannot be solved
        return False
    
    def find_empty_cell(board):
        # Find the next empty cell on the board
        for row in range(9):
            for col in range(9):
                if board[row][col] == 0:
                    return row, col
        return -1, -1
    
    def is_valid(board, row, col, num):
        # Check if placing a number in a cell is valid
        # Check row
        for i in range(9):
            if board[row][i] == num:
                return False
        
        # Check column
        for i in range(9):
            if board[i][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[start_row + i][start_col + j] == num:
                    return False
        
        return True
    
    # Test the solver
    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("Sudoku solved:")
        for row in board:
            print(row)
    else:
        print("No solution exists for the given Sudoku board.")
    

    This implementation uses a recursive function solve_sudoku to solve the Sudoku board. It finds the next empty cell on the board using the find_empty_cell function, and then tries placing numbers 1-9 in that cell. It checks if the placement is valid using the is_valid function, which checks the row, column, and 3x3 box constraints. If a number placement is valid, it recursively calls solve_sudoku to solve the rest of the board. If the board cannot be solved, it backtracks and tries a different number. The function returns True if the board is solved, and False if no solution exists. Finally, a test case is provided to demonstrate the usage of the solver.

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