八皇后问题
八皇后问题 问题 八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵列、正斜线或反斜线。使用穷举法列举所有可能。 程序 import tkinter as tk from tkinter import messagebox import time import threading class EightQueensGUI: def __init__(self, root): self.root = root self.root.title("八皇后问题演示") self.root.geometry("650x750") self.board_size = 8 self.cell_size = 50 self.delay = 100 self.setup_ui() self.solutions = [] self.current_solution = 0 self.solving = False self.solve_thread = None def setup_ui(self): # 创建主框架 main_frame = tk.Frame(self.root) main_frame.pack(fill=tk.BOTH, expand=True, padx=10, pady=10) # 创建画布 self.canvas = tk.Canvas(main_frame, width=500, height=500, bg='white') self.canvas.pack(pady=10) # 创建控制按钮框架 control_frame = tk.Frame(main_frame) control_frame.pack(pady=10, fill=tk.X) # 第一行按钮 btn_frame1 = tk.Frame(control_frame) btn_frame1.pack(pady=5) self.solve_btn = tk.Button(btn_frame1, text="开始求解", command=self.solve, width=10) self.solve_btn.pack(side=tk.LEFT, padx=5) self.next_btn = tk.Button(btn_frame1, text="下一个解", command=self.next_solution, width=10) self.next_btn.pack(side=tk.LEFT, padx=5) self.prev_btn = tk.Button(btn_frame1, text="上一个解", command=self.prev_solution, width=10) self.prev_btn.pack(side=tk.LEFT, padx=5) self.stop_btn = tk.Button(btn_frame1, text="停止求解", command=self.stop_solving, width=10) self.stop_btn.pack(side=tk.LEFT, padx=5) # 第二行控件 btn_frame2 = tk.Frame(control_frame) btn_frame2.pack(pady=5, fill=tk.X) # 速度控制 speed_frame = tk.Frame(btn_frame2) speed_frame.pack(side=tk.LEFT, padx=10) tk.Label(speed_frame, text="速度:").pack(side=tk.LEFT) self.speed_scale = tk.Scale(speed_frame, from_=10, to=500, orient=tk.HORIZONTAL, length=200, showvalue=True, command=self.update_delay) self.speed_scale.set(self.delay) self.speed_scale.pack(side=tk.LEFT, padx=5) # 解决方案选择 sol_frame = tk.Frame(btn_frame2) sol_frame.pack(side=tk.RIGHT, padx=10) tk.Label(sol_frame, text="直接查看解:").pack(side=tk.LEFT) self.solution_var = tk.StringVar(value="1") self.solution_spinbox = tk.Spinbox(sol_frame, from_=1, to=92, width=5, textvariable=self.solution_var, command=self.jump_to_solution) self.solution_spinbox.pack(side=tk.LEFT, padx=5) # 信息标签 self.info_label = tk.Label(main_frame, text="点击'开始求解'来演示八皇后问题的解法", font=("Arial", 12), wraplength=600) self.info_label.pack(pady=5) # 状态标签 self.status_label = tk.Label(main_frame, text="", font=("Arial", 10), fg="blue") self.status_label.pack(pady=5) # 绘制初始棋盘 self.draw_board() def draw_board(self): self.canvas.delete("all") # 绘制棋盘 for row in range(self.board_size): for col in range(self.board_size): x1 = col * self.cell_size + 50 y1 = row * self.cell_size + 50 x2 = x1 + self.cell_size y2 = y1 + self.cell_size color = "#DEB887" if (row + col) % 2 == 0 else "#8B4513" self.canvas.create_rectangle(x1, y1, x2, y2, fill=color, outline="black") # 绘制行列标记 for i in range(self.board_size): # 行标记 (A-H) self.canvas.create_text(25, i * self.cell_size + 50 + self.cell_size // 2, text=chr(65 + i), font=("Arial", 12, "bold")) # 列标记 (1-8) self.canvas.create_text(i * self.cell_size + 50 + self.cell_size // 2, 25, text=str(i + 1), font=("Arial", 12, "bold")) def draw_queens(self, board): self.draw_board() for row in range(self.board_size): for col in range(self.board_size): if board[row][col] == 1: self.draw_queen(row, col) self.root.update() def draw_queen(self, row, col): x = col * self.cell_size + 50 + self.cell_size // 2 y = row * self.cell_size + 50 + self.cell_size // 2 radius = self.cell_size // 3 # 绘制皇后 self.canvas.create_oval(x - radius, y - radius, x + radius, y + radius, fill="red", outline="darkred", width=2) # 绘制皇冠 crown_points = [ x - radius//2, y - radius, x - radius//3, y - radius//2, x, y - radius, x + radius//3, y - radius//2, x + radius//2, y - radius ] self.canvas.create_polygon(crown_points, fill="gold", outline="darkgoldenrod", width=2) def is_safe(self, board, row, col): # 检查同一列 for i in range(row): if board[i][col] == 1: return False # 检查左上对角线 for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)): if board[i][j] == 1: return False # 检查右上对角线 for i, j in zip(range(row-1, -1, -1), range(col+1, self.board_size)): if board[i][j] == 1: return False return True def solve_n_queens(self, board, row=0): if not self.solving: return False if row >= self.board_size: # 找到解，复制当前棋盘状态 solution = [row[:] for row in board] self.solutions.append(solution) self.update_status(f"找到第 {len(self.solutions)} 个解") # 更新显示 self.draw_queens(board) time.sleep(self.delay / 1000) # 继续寻找更多解 return False for col in range(self.board_size): if not self.solving: return False if self.is_safe(board, row, col): board[row][col] = 1 # 更新显示 self.draw_queens(board) self.update_info(f"尝试在位置 ({chr(65+row)}{col+1}) 放置皇后") time.sleep(self.delay / 1000) # 递归调用 self.solve_n_queens(board, row + 1) # 回溯 board[row][col] = 0 # 更新显示 self.draw_queens(board) self.update_info(f"回溯: 移除位置 ({chr(65+row)}{col+1}) 的皇后") time.sleep(self.delay / 1000) return False def solve(self): self.solve_btn.config(state=tk.DISABLED) self.stop_btn.config(state=tk.NORMAL) self.solutions = [] self.solving = True board = [[0 for _ in range(self.board_size)] for _ in range(self.board_size)] # 在新线程中运行求解过程 self.solve_thread = threading.Thread(target=self.solve_thread_func, args=(board,)) self.solve_thread.daemon = True self.solve_thread.start() def solve_thread_func(self, board): # 使用改进的算法找到所有解 self.find_all_solutions(board) if self.solving: if self.solutions: self.current_solution = 0 self.show_solution_info() self.update_status(f"求解完成! 共找到 {len(self.solutions)} 个解") self.solution_spinbox.config(to=len(self.solutions)) self.solution_var.set("1") else: self.update_status("未找到解!") self.solve_btn.config(state=tk.NORMAL) self.stop_btn.config(state=tk.DISABLED) self.solving = False def find_all_solutions(self, board, row=0): """找到所有解的递归函数""" if not self.solving: return if row >= self.board_size: # 找到一个解 solution = [row[:] for row in board] self.solutions.append(solution) self.update_status(f"找到第 {len(self.solutions)} 个解") # 显示当前解 self.draw_queens(board) time.sleep(self.delay / 1000) return for col in range(self.board_size): if not self.solving: return if self.is_safe(board, row, col): board[row][col] = 1 # 更新显示 self.draw_queens(board) self.update_info(f"尝试在位置 ({chr(65+row)}{col+1}) 放置皇后") time.sleep(self.delay / 1000) # 递归调用 self.find_all_solutions(board, row + 1) # 回溯 board[row][col] = 0 # 更新显示 self.draw_queens(board) self.update_info(f"回溯: 移除位置 ({chr(65+row)}{col+1}) 的皇后") time.sleep(self.delay / 1000) def stop_solving(self): self.solving = False self.update_status("求解已停止") def show_solution_info(self): if self.solutions and 0 <= self.current_solution < len(self.solutions): solution = self.solutions[self.current_solution] self.draw_queens(solution) self.update_info(f"解 {self.current_solution + 1}/{len(self.solutions)}") def next_solution(self): if self.solutions: self.current_solution = (self.current_solution + 1) % len(self.solutions) self.solution_var.set(str(self.current_solution + 1)) self.show_solution_info() def prev_solution(self): if self.solutions: self.current_solution = (self.current_solution - 1) % len(self.solutions) self.solution_var.set(str(self.current_solution + 1)) self.show_solution_info() def jump_to_solution(self): if self.solutions: try: sol_num = int(self.solution_var.get()) - 1 if 0 <= sol_num < len(self.solutions): self.current_solution = sol_num self.show_solution_info() except ValueError: pass def update_delay(self, value): self.delay = int(value) def update_info(self, text): self.info_label.config(text=text) self.root.update_idletasks() def update_status(self, text): self.status_label.config(text=text) self.root.update_idletasks() def main(): root = tk.Tk() app = EightQueensGUI(root) root.mainloop() if __name__ == "__main__": main() 思想 该程序使用穷举法，并通过UI展示了完整的穷举过程，可以访问穷举结果。穷举中如果出现错误的情况就回溯。 ...