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