题目

数独 问题 数独是在一个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() 执行结果 ...

井字棋 问题 井字棋是在一个九宫格中依次填入O或X，当横、竖、斜出现三个相同棋子时即获胜。以O先下为例，统计各自胜场和平局数。 完全穷举 讨论所有情况的胜率。 程序 class TicTacToeCompleteExhaustive: def __init__(self): self.total_states = 0 self.o_wins = 0 self.x_wins = 0 self.draws = 0 self.unfinished = 0 self.total_moves = 0 # 胜利条件 self.win_conditions = [ [0, 1, 2], [3, 4, 5], [6, 7, 8], # 横线 [0, 3, 6], [1, 4, 7], [2, 5, 8], # 竖线 [0, 4, 8], [2, 4, 6] # 对角线 ] def is_win(self, state, player): """判断某玩家是否获胜""" for condition in self.win_conditions: if all(state[i] == player for i in condition): return True return False def is_draw(self, state): """判断是否平局""" return 0 not in state and not self.is_win(state, 1) and not self.is_win(state, 2) def is_unfinished(self, state): """判断是否未结束""" return 0 in state and not self.is_win(state, 1) and not self.is_win(state, 2) def analyze_state(self, state): """分析一个状态并更新统计""" self.total_states += 1 # 计算当前状态的步数（已下的棋子数） moves_in_state = state.count(1) + state.count(2) self.total_moves += moves_in_state if self.is_win(state, 1): # O赢 self.o_wins += 1 elif self.is_win(state, 2): # X赢 self.x_wins += 1 elif self.is_draw(state): # 平局 self.draws += 1 elif self.is_unfinished(state): # 未结束 self.unfinished += 1 def dfs(self, state, is_o_turn): """深度优先搜索所有可能的局面（完全穷举）""" # 分析当前状态 self.analyze_state(state) # 如果游戏结束，不再继续搜索 if self.is_win(state, 1) or self.is_win(state, 2) or self.is_draw(state): return # 继续搜索下一步 for i in range(9): if state[i] == 0: state[i] = 1 if is_o_turn else 2 self.dfs(state, not is_o_turn) state[i] = 0 def analyze_all_states(self): """分析所有可能的游戏局面（完全穷举）""" print("开始分析井字棋所有可能局面（完全穷举）...") initial_state = [0] * 9 # 0表示空，1表示O，2表示X self.dfs(initial_state, True) # O先手 # 输出结果 print("\n=== 井字棋穷举分析结果（完全穷举）===") print(f"总局面数: {self.total_states:,}") print(f"O 获胜局面数: {self.o_wins:,}") print(f"X 获胜局面数: {self.x_wins:,}") print(f"平局局面数: {self.draws:,}") print(f"未结束局面数: {self.unfinished:,}") # 验证总数 total_calculated = self.o_wins + self.x_wins + self.draws + self.unfinished print(f"验证: {self.o_wins:,} + {self.x_wins:,} + {self.draws:,} + {self.unfinished:,} = {total_calculated:,}") print(f"与实际总数对比: {total_calculated} = {self.total_states}") print("\n=== 比例分析 ===") print(f"O 胜率: {self.o_wins/self.total_states*100:.4f}%") print(f"X 胜率: {self.x_wins/self.total_states*100:.4f}%") print(f"平局率: {self.draws/self.total_states*100:.4f}%") print(f"未结束率: {self.unfinished/self.total_states*100:.4f}%") # 计算平均深度 if self.total_states > 0: avg_moves = self.total_moves / self.total_states print(f"\n平均步数: {avg_moves:.2f}") return self.total_states # 运行分析 if __name__ == "__main__": analyzer = TicTacToeCompleteExhaustive() total = analyzer.analyze_all_states() 执行结果 ...

密码破解 问题 使用暴力破解包含大小写字母和数字的四位密码。 程序 import itertools import time import hashlib def generate_hashes(passwords): """生成密码的MD5哈希值""" hashes = {} for pwd in passwords: hashes[pwd] = hashlib.md5(pwd.encode()).hexdigest() return hashes def crack_by_hash(target_hashes): """通过哈希值破解密码""" characters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789' print("开始破解密码...") start_time = time.time() attempts = 0 found_passwords = {} # 记录每个密码的破解信息 crack_info = {} # 生成所有1-3位字符组合 for length in range(1, 5): for candidate in itertools.product(characters, repeat=length): password_attempt = ''.join(candidate) attempts += 1 # 计算当前尝试密码的MD5哈希值 hash_attempt = hashlib.md5(password_attempt.encode()).hexdigest() # 检查哈希值是否匹配任何目标 for original_pwd, target_hash in target_hashes.items(): if hash_attempt == target_hash and original_pwd not in found_passwords: found_passwords[original_pwd] = password_attempt crack_time = time.time() - start_time crack_info[original_pwd] = { 'attempts': attempts, 'time': crack_time, 'found_password': password_attempt } print(f"✅ 破解成功: '{original_pwd}' -> '{password_attempt}'") print(f" 尝试次数: {attempts}, 耗时: {crack_time:.4f}秒") # 如果所有密码都已找到，提前结束 if len(found_passwords) == len(target_hashes): total_time = time.time() - start_time print(f"\n所有密码破解完成!") print(f"总尝试次数: {attempts}, 总耗时: {total_time:.4f}秒") return crack_info total_time = time.time() - start_time print(f"\n破解结束，找到 {len(found_passwords)}/{len(target_hashes)} 个密码") print(f"总尝试次数: {attempts}, 总耗时: {total_time:.4f}秒") return crack_info def main(): # 预存密码 - 代表最快和最后被遍历出来的密码 passwords = ['a', '9', 'aa', '99', 'aaa', '999', 'aaaa', '9999'] print("=" * 60) print(" 密码哈希破解演示 (使用MD5)") print("=" * 60) # 生成并显示预存密码的哈希值 print("\n预存密码及其MD5哈希值:") print("-" * 80) hashes = generate_hashes(passwords) for pwd, h in hashes.items(): print(f"密码: '{pwd}' -> 哈希: {h}") print("-" * 80) # 显示字符集信息 characters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789' print(f"\n字符集: {characters}") print(f"字符集大小: {len(characters)}") print(f"1位密码组合数: {len(characters)}") print(f"2位密码组合数: {len(characters)**2}") print(f"3位密码组合数: {len(characters)**3}") print(f"4位密码组合数: {len(characters)**4}") print(f"总组合数: {len(characters) + len(characters)**2 + len(characters)**3 + len(characters)**4}") # 开始破解 input("\n按回车键开始破解...") # 破解密码（只通过哈希值比较） results = crack_by_hash(hashes) # 显示破解结果总结 print("\n" + "=" * 60) print("破解结果总结:") print("-" * 60) # 按破解顺序显示 for pwd in passwords: if pwd in results: info = results[pwd] print(f"密码 '{pwd}': {info['attempts']:6d} 次尝试, {info['time']:.4f} 秒") else: print(f"密码 '{pwd}': 未找到") print("=" * 60) if __name__ == "__main__": main() 执行效果 ============================================================ 密码哈希破解演示 (使用MD5) ============================================================ 预存密码及其MD5哈希值: -------------------------------------------------------------------------------- 密码: 'a' -> 哈希: 0cc175b9c0f1b6a831c399e269772661 密码: '9' -> 哈希: 45c48cce2e2d7fbdea1afc51c7c6ad26 密码: 'aa' -> 哈希: 4124bc0a9335c27f086f24ba207a4912 密码: '99' -> 哈希: ac627ab1ccbdb62ec96e702f07f6425b 密码: 'aaa' -> 哈希: 47bce5c74f589f4867dbd57e9ca9f808 密码: '999' -> 哈希: b706835de79a2b4e80506f582af3676a 密码: 'aaaa' -> 哈希: 74b87337454200d4d33f80c4663dc5e5 密码: '9999' -> 哈希: fa246d0262c3925617b0c72bb20eeb1d -------------------------------------------------------------------------------- 字符集: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 字符集大小: 62 1位密码组合数: 62 2位密码组合数: 3844 3位密码组合数: 238328 4位密码组合数: 14776336 总组合数: 15018570 按回车键开始破解... 开始破解密码... ✅ 破解成功: 'a' -> 'a' 尝试次数: 1, 耗时: 0.0000秒 ✅ 破解成功: '9' -> '9' 尝试次数: 62, 耗时: 0.0006秒 ✅ 破解成功: 'aa' -> 'aa' 尝试次数: 63, 耗时: 0.0010秒 ✅ 破解成功: '99' -> '99' 尝试次数: 3906, 耗时: 0.0053秒 ✅ 破解成功: 'aaa' -> 'aaa' 尝试次数: 3907, 耗时: 0.0055秒 ✅ 破解成功: '999' -> '999' 尝试次数: 242234, 耗时: 0.2391秒 ✅ 破解成功: 'aaaa' -> 'aaaa' 尝试次数: 242235, 耗时: 0.2394秒 ✅ 破解成功: '9999' -> '9999' 尝试次数: 15018570, 耗时: 14.6867秒 所有密码破解完成! 总尝试次数: 15018570, 总耗时: 14.6869秒 ============================================================ 破解结果总结: ------------------------------------------------------------ 密码 'a': 1 次尝试, 0.0000 秒 密码 '9': 62 次尝试, 0.0006 秒 密码 'aa': 63 次尝试, 0.0010 秒 密码 '99': 3906 次尝试, 0.0053 秒 密码 'aaa': 3907 次尝试, 0.0055 秒 密码 '999': 242234 次尝试, 0.2391 秒 密码 'aaaa': 242235 次尝试, 0.2394 秒 密码 '9999': 15018570 次尝试, 14.6867 秒 ============================================================

水仙花数 问题 三位数的水仙花数是指一个三位数的每个数字的立方和等于该数本身。求所有三位水仙花数。 程序 for num in range(100, 1000): a = num // 100 # 百位 b = (num // 10) % 10 # 十位 c = num % 10 # 个位 if a**3 + b**3 + c**3 == num: print(num) 思想 穷举所有可能并打印合适的数。 执行效果

百钱买百鸡 问题 鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，则翁、母、雏各几何？ 程序 # 公鸡5文钱一只，母鸡3文钱一只，小鸡1文钱三只。用100文钱买100只鸡，问公鸡、母鸡、小鸡各多少只？ # 穷举法：遍历所有可能的公鸡、母鸡、小鸡数量，判断是否满足条件 for cock in range(0, 21): # 公鸡从0到20只 for hen in range(0, 34): # 母鸡从0到33只 chick = 100 - cock - hen # 小鸡数量 if chick % 3 == 0 and cock * 5 + hen * 3 + chick // 3 == 100: print(f"公鸡：{cock}只，母鸡：{hen}只，小鸡：{chick}只") 思想 穷举所有可能，记录所有可能的情况。 执行效果