Python：用DFS算法实现数独游戏解谜

下面是用DFS算法实现的数独游戏的Python代码示例： ```python def is_valid(board, row, col, num): # 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 square 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 def solve_sudoku(board): empty_cell = find_empty_cell(board) if not empty_cell: return True row, col = empty_cell for num in range(1, 10): if is_valid(board, row, col, str(num)): board[row][col] = str(num) if solve_sudoku(board): return True board[row][col] = '.' return False def find_empty_cell(board): for i in range(9): for j in range(9): if board[i][j] == '.': return (i, j) return None def print_board(board): for row in board: print(' '.join(row)) board = [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] solve_sudoku(board) print_board(board) ``` 这段代码通过DFS算法来解决数独游戏，首先定义了`is_valid`函数用来检查当前位置插入数字是否合法，然后定义了`solve_sudoku`函数来递归解决数独问题，最后使用`find_empty_cell`函数来找到未填入数字的位置。控制主要逻辑的`solve_sudoku`函数在找到空位置后，尝试填入1-9的数字，如果合法则递归进行下一个位置的尝试，直到填满整个数独板。 ######[AI写代码神器 | 1294点数解答 | 2024-11-03 08:40:39]