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()