数独 | 云雾海的博客

数独问题数独是在一个9*9宫格中，保证每行每列以及九个九宫格中填入的1-9的数字不出现重复。通过穷举法实现求解。程序 import tkinter as tk from tkinter import ttk, messagebox import time import threading class SudokuSolver: def __init__(self, root): self.root = root self.root.title("数独求解器 - 穷举法") self.root.geometry("600x700") # 初始化数独网格 self.board = [[0 for _ in range(9)] for _ in range(9)] self.initial_board = [[0 for _ in range(9)] for _ in range(9)] # 存储初始题目 self.cells = [[None for _ in range(9)] for _ in range(9)] self.selected_cell = None self.solving = False self.speed = 100 # 默认速度（毫秒） self.algorithm_time = 0 # 纯算法时间 self.step_count = 0 # 步骤计数器 # 初始化组件变量 self.speed_label = None self.speed_scale = None self.status_label = None self.stats_label = None self.create_widgets() def create_widgets(self): # 主框架 main_frame = ttk.Frame(self.root, padding="10") main_frame.pack(fill=tk.BOTH, expand=True) # 标题 title_label = ttk.Label(main_frame, text="数独求解器 - 穷举回溯法", font=("Arial", 16, "bold")) title_label.pack(pady=10) # 数独网格框架 grid_frame = ttk.Frame(main_frame) grid_frame.pack(pady=20) # 创建9x9网格 self.create_grid(grid_frame) # 控制面板 control_frame = ttk.Frame(main_frame) control_frame.pack(pady=20) # 速度控制 speed_frame = ttk.Frame(control_frame) speed_frame.pack(pady=10) ttk.Label(speed_frame, text="演示速度:").pack(side=tk.LEFT) self.speed_scale = ttk.Scale(speed_frame, from_=10, to=1000, orient=tk.HORIZONTAL, length=200, command=self.update_speed) self.speed_scale.set(100) self.speed_scale.pack(side=tk.LEFT, padx=10) self.speed_label = ttk.Label(speed_frame, text="100 ms") self.speed_label.pack(side=tk.LEFT) # 按钮 button_frame = ttk.Frame(control_frame) button_frame.pack(pady=10) ttk.Button(button_frame, text="开始求解", command=self.start_solving).pack(side=tk.LEFT, padx=5) ttk.Button(button_frame, text="直接作答", command=self.direct_solve).pack(side=tk.LEFT, padx=5) ttk.Button(button_frame, text="重置", command=self.reset_board).pack(side=tk.LEFT, padx=5) ttk.Button(button_frame, text="清空", command=self.clear_board).pack(side=tk.LEFT, padx=5) ttk.Button(button_frame, text="示例", command=self.load_example).pack(side=tk.LEFT, padx=5) # 状态显示 self.status_label = ttk.Label(main_frame, text="请点击格子并输入数字1-9", font=("Arial", 10)) self.status_label.pack(pady=10) # 统计信息 self.stats_label = ttk.Label(main_frame, text="步骤: 0 | 算法时间: 0.00s", font=("Arial", 10)) self.stats_label.pack(pady=5) # 操作说明 instruction_text = """操作说明： 1. 点击格子，然后按数字键1-9填入数字 2. 按0或Delete键清空格子 3. 调整速度滑块控制演示速度 4. 点击"开始求解"观看穷举求解过程 5. 点击"直接作答"直接获得答案 6. 紫色格子表示初始题目，绿色表示尝试的数字，红色表示回溯""" instruction_label = ttk.Label(main_frame, text=instruction_text, justify=tk.LEFT, font=("Arial", 9)) instruction_label.pack(pady=10) def create_grid(self, parent): # 创建9x9网格，每个3x3区域有更粗的边框 for i in range(9): for j in range(9): # 确定边框宽度 - 为3x3区域边界设置更粗的边框 border_width = 1 if i % 3 == 0 and i != 0: border_width = 3 if j % 3 == 0 and j != 0: border_width = 3 # 为外边框设置更粗的边框 if i == 0 or i == 8: border_width = 3 if j == 0 or j == 8: border_width = 3 cell = tk.Entry(parent, width=3, font=("Arial", 16), justify=tk.CENTER, relief="solid", borderwidth=border_width) cell.grid(row=i, column=j, padx=(1, 1), pady=(1, 1), ipady=5) # 绑定事件 cell.bind("<Button-1>", lambda e, row=i, col=j: self.select_cell(row, col)) cell.bind("<Key>", lambda e, row=i, col=j: self.on_key_press(e, row, col)) cell.bind("<FocusIn>", lambda e, row=i, col=j: self.select_cell(row, col)) self.cells[i][j] = cell def select_cell(self, row, col): # 取消之前选中格子的高亮 if self.selected_cell: old_row, old_col = self.selected_cell self.cells[old_row][old_col].config(bg=self.get_cell_color(old_row, old_col)) # 高亮当前选中的格子 self.selected_cell = (row, col) self.cells[row][col].config(bg="#e0e0ff") self.cells[row][col].focus_set() self.status_label.config(text=f"选中格子: ({row+1}, {col+1})") def get_cell_color(self, row, col): """根据格子内容返回对应的背景颜色""" if self.initial_board[row][col] != 0: return "#e0c0ff" # 初始题目 - 紫色 else: return "white" # 空白格子 - 白色 def on_key_press(self, event, row, col): if event.char in '123456789': self.set_cell_value(row, col, int(event.char)) elif event.keysym in ['Delete', 'BackSpace'] or event.char == '0': self.set_cell_value(row, col, 0) # 阻止默认行为 return "break" def set_cell_value(self, row, col, value): self.board[row][col] = value if value == 0: self.cells[row][col].delete(0, tk.END) else: self.cells[row][col].delete(0, tk.END) self.cells[row][col].insert(0, str(value)) # 更新格子颜色 self.cells[row][col].config(bg=self.get_cell_color(row, col)) def update_speed(self, value): self.speed = int(float(value)) # 确保 speed_label 已创建 if hasattr(self, 'speed_label') and self.speed_label is not None: self.speed_label.config(text=f"{self.speed} ms") def reset_board(self): for i in range(9): for j in range(9): self.set_cell_value(i, j, self.board[i][j]) self.status_label.config(text="棋盘已重置") def clear_board(self): for i in range(9): for j in range(9): self.set_cell_value(i, j, 0) self.initial_board[i][j] = 0 # 同时清空初始题目 self.status_label.config(text="棋盘已清空") self.step_count = 0 self.algorithm_time = 0 self.update_stats() def load_example(self): # 加载一个示例数独 example = [ [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] ] for i in range(9): for j in range(9): self.set_cell_value(i, j, example[i][j]) self.initial_board[i][j] = example[i][j] # 保存初始题目 self.status_label.config(text="已加载示例数独") def start_solving(self): if self.solving: return # 保存当前棋盘状态作为初始题目 for i in range(9): for j in range(9): if self.board[i][j] != 0: self.initial_board[i][j] = self.board[i][j] # 更新格子颜色为初始题目颜色 self.cells[i][j].config(bg=self.get_cell_color(i, j)) # 在新线程中运行求解过程，避免阻塞UI thread = threading.Thread(target=self.solve_thread) thread.daemon = True thread.start() def direct_solve(self): """直接求解，不演示中间过程""" if self.solving: return # 保存当前棋盘状态作为初始题目 for i in range(9): for j in range(9): if self.board[i][j] != 0: self.initial_board[i][j] = self.board[i][j] # 在新线程中运行直接求解过程 thread = threading.Thread(target=self.direct_solve_thread) thread.daemon = True thread.start() def solve_thread(self): """演示求解线程""" self.solving = True self.status_label.config(text="开始求解...") self.step_count = 0 self.algorithm_time = 0 # 禁用控制按钮 self.toggle_buttons(False) # 开始求解 start_time = time.time() solved = self.solve_sudoku() end_time = time.time() self.solving = False # 启用控制按钮 self.toggle_buttons(True) total_time = end_time - start_time if solved: self.status_label.config(text=f"求解完成! 总用时: {total_time:.2f}秒") else: self.status_label.config(text="无解!") def direct_solve_thread(self): """直接求解线程""" self.solving = True self.status_label.config(text="直接求解中...") # 禁用控制按钮 self.toggle_buttons(False) # 开始直接求解 start_time = time.time() solved = self.solve_sudoku_direct() end_time = time.time() self.solving = False # 启用控制按钮 self.toggle_buttons(True) total_time = end_time - start_time if solved: # 更新UI显示最终结果 self.update_final_board() self.status_label.config(text=f"直接求解完成! 用时: {total_time:.2f}秒") else: self.status_label.config(text="无解!") def solve_sudoku_direct(self): """直接求解数独，不更新UI，不延迟""" # 创建棋盘副本 board_copy = [row[:] for row in self.board] # 直接求解 solved = self.solve_direct(board_copy) # 如果求解成功，更新棋盘 if solved: self.board = board_copy return solved def solve_direct(self, board): """直接求解数独的递归函数""" empty_cell = self.find_empty_cell_direct(board) if not empty_cell: return True # 没有空格子，求解完成 row, col = empty_cell for num in range(1, 10): if self.is_valid_direct(board, row, col, num): # 尝试填入数字 board[row][col] = num # 递归求解 if self.solve_direct(board): return True # 回溯 board[row][col] = 0 return False def find_empty_cell_direct(self, board): """在直接求解模式下查找空格子""" for i in range(9): for j in range(9): if board[i][j] == 0: return (i, j) return None def is_valid_direct(self, board, row, col, num): """在直接求解模式下检查数字是否有效""" # 检查行 for i in range(9): if board[row][i] == num: return False # 检查列 for i in range(9): if board[i][col] == num: return False # 检查3x3宫格 start_row, start_col = 3 * (row // 3), 3 * (col // 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 update_final_board(self): """更新UI显示最终结果""" for i in range(9): for j in range(9): value = self.board[i][j] if value != 0: self.cells[i][j].delete(0, tk.END) self.cells[i][j].insert(0, str(value)) # 如果是算法填入的数字，显示为浅蓝色 if self.initial_board[i][j] == 0: self.cells[i][j].config(bg="#c0e0ff") def toggle_buttons(self, state): state_str = "normal" if state else "disabled" for widget in self.root.winfo_children(): for child in widget.winfo_children(): if isinstance(child, ttk.Frame): for button in child.winfo_children(): if isinstance(button, ttk.Button): button.config(state=state_str) def is_valid(self, board, row, col, num): # 检查行 for i in range(9): if board[row][i] == num: return False # 检查列 for i in range(9): if board[i][col] == num: return False # 检查3x3宫格 start_row, start_col = 3 * (row // 3), 3 * (col // 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(self): # 使用回溯法求解数独 empty_cell = self.find_empty_cell() if not empty_cell: return True # 没有空格子，求解完成 row, col = empty_cell for num in range(1, 10): # 记录算法开始时间 algo_start = time.time() if self.is_valid(self.board, row, col, num): # 尝试填入数字 self.board[row][col] = num self.step_count += 1 # 更新UI - 确保格子显示为绿色 self.root.after(0, lambda r=row, c=col, v=num: self.update_cell_ui(r, c, v, "try")) # 记录算法结束时间 algo_end = time.time() self.algorithm_time += (algo_end - algo_start) self.update_stats() # 延迟用于演示 time.sleep(self.speed / 1000.0) # 递归求解 if self.solve_sudoku(): return True # 回溯 algo_start = time.time() self.board[row][col] = 0 self.step_count += 1 # 更新UI self.root.after(0, lambda r=row, c=col, v=0: self.update_cell_ui(r, c, v, "backtrack")) # 记录算法结束时间 algo_end = time.time() self.algorithm_time += (algo_end - algo_start) self.update_stats() # 延迟用于演示 time.sleep(self.speed / 1000.0) else: # 即使数字无效，也记录算法时间 algo_end = time.time() self.algorithm_time += (algo_end - algo_start) self.update_stats() return False def find_empty_cell(self): for i in range(9): for j in range(9): if self.board[i][j] == 0: return (i, j) return None def update_cell_ui(self, row, col, value, action_type): # 如果是初始题目格子，保持紫色，不改变 if self.initial_board[row][col] != 0: return if value == 0: self.cells[row][col].delete(0, tk.END) if action_type == "backtrack": self.cells[row][col].config(bg="#ffcccc") # 回溯时显示红色 # 立即更新UI self.root.update_idletasks() self.root.update() else: self.cells[row][col].delete(0, tk.END) self.cells[row][col].insert(0, str(value)) if action_type == "try": self.cells[row][col].config(bg="#ccffcc") # 尝试时显示绿色 # 立即更新UI self.root.update_idletasks() self.root.update() def update_stats(self): if hasattr(self, 'stats_label') and self.stats_label is not None: self.root.after(0, lambda: self.stats_label.config( text=f"步骤: {self.step_count} | 算法时间: {self.algorithm_time:.3f}s")) def main(): root = tk.Tk() app = SudokuSolver(root) root.mainloop() if __name__ == "__main__": main() 执行结果 ...