Python Sudoku solver recursive backtracking
- User
Python Sudoku solver recursive backtracking
- 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_sudokuto solve the Sudoku board. It finds the next empty cell on the board using thefind_empty_cellfunction, and then tries placing numbers 1-9 in that cell. It checks if the placement is valid using theis_validfunction, which checks the row, column, and 3x3 box constraints. If a number placement is valid, it recursively callssolve_sudokuto solve the rest of the board. If the board cannot be solved, it backtracks and tries a different number. The function returnsTrueif the board is solved, andFalseif no solution exists. Finally, a test case is provided to demonstrate the usage of the solver.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.