之所以突发奇想做一个这个解题器是因为行测小助手里面的数独，后面去搜了一下世界最难数独。
发现完全做不出，后来想着能不能用电脑暴力求解。
后来发现是完全可行的；目前(25年5月28日)实现了数独的自定义求解，可以csv导入数独，使用内置数独题库，以及保存解题步骤和显示求解时间。
以下是求解的python代码。
import tkinter as tk
from tkinter import messagebox, filedialog, simpledialog
import numpy as np
from numba import njit
import threading
import random
import csv
import requests
import time
import imageio
import os
# ---------- Numba 加速数独求解器 ----------
@njit
def is_valid(board, row, col, num):
for i in range(9):
if board[row, i] == num or board[i, col] == num:
return False
sr, sc = row - row % 3, col - col % 3
for i in range(3):
for j in range(3):
if board[sr + i, sc + j] == num:
return False
return True
@njit
def solve_sudoku(board):
for r in range(9):
for c in range(9):
if board[r, c] == 0:
for num in range(1, 10):
if is_valid(board, r, c, num):
board[r, c] = num
if solve_sudoku(board):
return True
board[r, c] = 0
return False
return True
# ---------- 纯 Python 记录步骤求解器 ----------
def solve_with_steps(board, steps):
for r in range(9):
for c in range(9):
if board[r, c] == 0:
for num in range(1, 10):
if py_valid(board, r, c, num):
board[r, c] = num
steps.append(board.copy())
if solve_with_steps(board, steps):
return True
board[r, c] = 0
steps.append(board.copy())
return False
return True
def py_valid(board, row, col, num):
if num in board[row, :] or num in board[:, col]:
return False
sr, sc = row - row % 3, col - col % 3
if num in board[sr:sr+3, sc:sc+3]:
return False
return True
# ---------- 内置题库 ----------
PUZZLES = [
[8,0,0,0,0,0,0,0,0,
0,0,3,6,0,0,0,0,0,
0,7,0,0,9,0,2,0,0,
0,5,0,0,0,7,0,0,0,
0,0,0,0,4,5,7,0,0,
0,0,0,1,0,0,0,3,0,
0,0,1,0,0,0,0,6,8,
0,0,8,5,0,0,0,1,0,
0,9,0,0,0,0,4,0,0]
]
# ---------- GUI 主类 ----------
class SudokuGUI:
def __init__(self, root):
self.root = root
self.root.title("Numba Sudoku Solver v3")
self.entries = [[None]*9 for _ in range(9)]
# 创建 9x9 输入格
for i in range(9):
for j in range(9):
e = tk.Entry(root, width=2, font=('Arial',18), justify='center')
e.grid(row=i, column=j, padx=1, pady=1)
self.entries[i][j] = e
# 按钮区
btn_frame = tk.Frame(root)
btn_frame.grid(row=9, column=0, columnspan=9, pady=5)
tk.Button(btn_frame, text="求解", width=8, command=self._start_solve).pack(side='left', padx=2)
tk.Button(btn_frame, text="清空", width=8, command=self.clear).pack(side='left', padx=2)
tk.Button(btn_frame, text="载入 CSV", width=8, command=self.load_csv).pack(side='left', padx=2)
tk.Button(btn_frame, text="生成新题", width=8, command=self.generate).pack(side='left', padx=2)
tk.Button(btn_frame, text="下载题库", width=8, command=self.download_puzzles).pack(side='left', padx=2)
tk.Button(btn_frame, text="保存步骤GIF", width=10, command=self.save_gif).pack(side='left', padx=2)
def clear(self):
for row in self.entries:
for e in row:
e.delete(0, tk.END)
def load_csv(self):
path = filedialog.askopenfilename(filetypes=[("CSV 文件","*.csv")])
if not path: return
try:
with open(path, newline='') as f:
arr = [list(map(int,row)) for row in csv.reader(f)]
if len(arr)!=9 or any(len(r)!=9 for r in arr): raise ValueError
self.clear()
for i in range(9):
for j in range(9):
if arr[i][j]!=0:
self.entries[i][j].insert(0, str(arr[i][j]))
except:
messagebox.showerror("错误","CSV 格式须为 9×9 数字矩阵，空格请填 0")
def generate(self):
flat = random.choice(PUZZLES)
self.clear()
for idx,val in enumerate(flat):
if val:
i,j = divmod(idx,9)
self.entries[i][j].insert(0,str(val))
def download_puzzles(self):
url = simpledialog.askstring("下载题库","请输入CSV题库URL：")
if not url: return
try:
r = requests.get(url)
r.raise_for_status()
data = r.text.splitlines()
new = [list(map(int,row.split(','))) for row in data]
if len(new)==9 and all(len(r)==9 for r in new):
PUZZLES.append(sum(new,[]))
messagebox.showinfo("成功","题库下载并添加成功！")
else:
raise ValueError
except Exception:
messagebox.showerror("错误","下载或格式解析失败")
def _start_solve(self):
threading.Thread(target=self.solve).start()
def solve(self):
# 禁用按钮
for btn in self.root.winfo_children()[9].winfo_children(): btn.config(state='disabled')
try:
board = np.zeros((9,9),dtype=np.int32)
for i in range(9):
for j in range(9):
s = self.entries[i][j].get().strip()
if s:
n=int(s)
if not 1<=n<=9: raise ValueError
board[i,j]=n
start=time.perf_counter()
solved = solve_sudoku(board)
elapsed = time.perf_counter()-start
if solved:
for i in range(9):
for j in range(9):
self.entries[i][j].delete(0,tk.END)
self.entries[i][j].insert(0,str(board[i,j]))
messagebox.showinfo("成功",f"求解完成！用时 {elapsed:.4f}s")
else:
messagebox.showwarning("失败","该题无解！")
except ValueError:
messagebox.showerror("错误","请输入1~9或留空")
finally:
for btn in self.root.winfo_children()[9].winfo_children(): btn.config(state='normal')
def save_gif(self):
# 记录步骤并生成GIF
board = np.zeros((9,9),dtype=np.int32)
for i in range(9):
for j in range(9):
s=self.entries[i][j].get().strip()
if s: board[i,j]=int(s)
steps=[]
if not solve_with_steps(board.copy(),steps):
messagebox.showwarning("失败","该题无解，无法生成GIF！")
return
temp_dir='sudoku_frames'
os.makedirs(temp_dir,exist_ok=True)
filenames=[]
import matplotlib.pyplot as plt
for idx, b in enumerate(steps):
fig,ax=plt.subplots(figsize=(4,4))
for k in range(10):
lw=2 if k%3==0 else 1
ax.plot([k,k],[0,9],'k-',lw=lw)
ax.plot([0,9],[k,k],'k-',lw=lw)
for r in range(9):
for c in range(9):
num=b[r,c]
if num:
ax.text(c+0.5,8.5-r,str(num),ha='center',va='center')
ax.axis('off')
fname=os.path.join(temp_dir,f"frame_{idx}.png")
fig.savefig(fname)
plt.close(fig)
filenames.append(fname)
gif_path = filedialog.asksaveasfilename(defaultextension='.gif',filetypes=[('GIF文件','*.gif')])
if not gif_path: return
images=[imageio.imread(f) for f in filenames]
imageio.mimsave(gif_path,images,duration=0.2)
messagebox.showinfo("成功",f"步骤GIF已保存至 {gif_path}")
for f in filenames: os.remove(f)
os.rmdir(temp_dir)
# ---------- 启动 ----------
if __name__ == "__main__":
root=tk.Tk()
app=SudokuGUI(root)
root.mainloop()
注：使用Pythoninstaller打包成exe时，需要使用 --collect-submodules=numba ，不然因为numba，会运行出现错误。https://github.com/pyinstaller/pyinstaller/issues/8989
250529 1:30
增加ocr识别
import tkinter as tk
from tkinter import filedialog, messagebox
import numpy as np
import cv2
import pytesseract
import time
from numba import njit
# 设置 tesseract 路径（请根据你的路径设置）
pytesseract.pytesseract.tesseract_cmd = r'C:\Program Files\Tesseract-OCR\tesseract.exe'
@njit
def is_valid(board, row, col, num):
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False
if board[3*(row//3)+i//3][3*(col//3)+i%3] == num:
return False
return True
@njit
def solve_sudoku(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1, 10):
if is_valid(board, i, j, num):
board[i][j] = num
if solve_sudoku(board):
return True
board[i][j] = 0
return False
return True
def extract_sudoku_grid(image_path):
image = cv2.imread(image_path)
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
blur = cv2.GaussianBlur(gray, (7, 7), 0)
thresh = cv2.adaptiveThreshold(blur, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C,
cv2.THRESH_BINARY_INV, 11, 2)
contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
largest = max(contours, key=cv2.contourArea)
peri = cv2.arcLength(largest, True)
approx = cv2.approxPolyDP(largest, 0.02 * peri, True)
if len(approx) != 4:
raise ValueError("无法检测到数独边框。")
pts = approx.reshape(4, 2)
s = pts.sum(axis=1)
diff = np.diff(pts, axis=1)
rect = np.array([
pts[np.argmin(s)],
pts[np.argmin(diff)],
pts[np.argmax(s)],
pts[np.argmax(diff)]
], dtype="float32")
side = max(np.linalg.norm(rect[0] - rect[1]), np.linalg.norm(rect[1] - rect[2]),
np.linalg.norm(rect[2] - rect[3]), np.linalg.norm(rect[3] - rect[0]))
dst = np.array([[0, 0], [side - 1, 0], [side - 1, side - 1], [0, side - 1]], dtype="float32")
M = cv2.getPerspectiveTransform(rect, dst)
warp = cv2.warpPerspective(gray, M, (int(side), int(side)))
return warp
def ocr_cells(warped):
side = warped.shape[0]
cell_side = side // 9
grid = []
config = "--psm 10 -c tessedit_char_whitelist=0123456789"
for y in range(9):
row = []
for x in range(9):
x1, y1 = x * cell_side, y * cell_side
cell = warped[y1:y1 + cell_side, x1:x1 + cell_side]
_, thresh = cv2.threshold(cell, 0, 255, cv2.THRESH_BINARY_INV + cv2.THRESH_OTSU)
resized = cv2.resize(thresh, None, fx=2, fy=2, interpolation=cv2.INTER_CUBIC)
digit_str = pytesseract.image_to_string(resized, config=config).strip()
row.append(int(digit_str) if digit_str.isdigit() else 0)
grid.append(row)
return grid
class SudokuGUI:
def __init__(self, root):
self.root = root
self.root.title("OCR 数独求解器")
self.entries = [[tk.Entry(root, width=2, font=('Arial', 18), justify='center') for _ in range(9)] for _ in range(9)]
for i in range(9):
for j in range(9):
self.entries[i][j].grid(row=i, column=j, padx=1, pady=1)
tk.Button(root, text="求解", command=self.solve).grid(row=9, column=0, columnspan=3)
tk.Button(root, text="清除", command=self.clear).grid(row=9, column=3, columnspan=3)
tk.Button(root, text="从图像识别", command=self.load_image).grid(row=9, column=6, columnspan=3)
self.time_label = tk.Label(root, text="", font=('Arial', 12))
self.time_label.grid(row=10, column=0, columnspan=9)
def read_board(self):
board = []
for row in self.entries:
current_row = []
for cell in row:
val = cell.get()
current_row.append(int(val) if val.isdigit() else 0)
board.append(current_row)
return board
def fill_board(self, board):
for i in range(9):
for j in range(9):
self.entries[i][j].delete(0, tk.END)
if board[i][j] != 0:
self.entries[i][j].insert(0, str(board[i][j]))
def solve(self):
board = self.read_board()
start = time.time()
success = solve_sudoku(np.array(board))
end = time.time()
if success:
self.fill_board(board)
self.time_label.config(text=f"求解耗时: {end - start:.3f} 秒")
else:
messagebox.showerror("错误", "无法求解该数独。")
def clear(self):
for row in self.entries:
for cell in row:
cell.delete(0, tk.END)
self.time_label.config(text="")
def load_image(self):
path = filedialog.askopenfilename(filetypes=[("Image files", "*.png *.jpg *.jpeg *.bmp")])
if not path:
return
try:
warp = extract_sudoku_grid(path)
sudoku = ocr_cells(warp)
self.fill_board(sudoku)
except Exception as e:
messagebox.showerror("错误", str(e))
if __name__ == "__main__":
root = tk.Tk()
gui = SudokuGUI(root)
root.mainloop()
现在可以读取题库。
import tkinter as tk
from tkinter import messagebox, filedialog
import numpy as np
from numba import njit
import threading
import random
import csv
import time
import imageio
import os
import cv2
import pytesseract
import matplotlib.pyplot as plt
# 配置 Tesseract 路径（请根据实际安装路径修改）
pytesseract.pytesseract.tesseract_cmd = r'C:\Program Files\Tesseract-OCR\tesseract.exe'
# Numba 加速数独求解器
@njit
def is_valid(board, row, col, num):
for i in range(9):
if board[row, i] == num or board[i, col] == num:
return False
sr, sc = (row // 3) * 3, (col // 3) * 3
for i in range(3):
for j in range(3):
if board[sr + i, sc + j] == num:
return False
return True
@njit
def solve_sudoku(board):
for r in range(9):
for c in range(9):
if board[r, c] == 0:
for num in range(1, 10):
if is_valid(board, r, c, num):
board[r, c] = num
if solve_sudoku(board):
return True
board[r, c] = 0
return False
return True
# 纯 Python 记录关键步骤（仅记录填充，减少帧数）
def solve_with_steps(board, steps):
for r in range(9):
for c in range(9):
if board[r, c] == 0:
for num in range(1, 10):
if py_valid(board, r, c, num):
board[r, c] = num
steps.append(board.copy())
if solve_with_steps(board, steps):
return True
board[r, c] = 0
return False
return True
def py_valid(board, row, col, num):
if num in board[row, :] or num in board[:, col]:
return False
sr, sc = (row // 3) * 3, (col // 3) * 3
if num in board[sr:sr+3, sc:sc+3]:
return False
return True
# OCR 识别功能
def extract_sudoku_grid(image_path):
image = cv2.imread(image_path)
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
blur = cv2.GaussianBlur(gray, (7, 7), 0)
thresh = cv2.adaptiveThreshold(blur, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C,
cv2.THRESH_BINARY_INV, 11, 2)
contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
largest = max(contours, key=cv2.contourArea)
peri = cv2.arcLength(largest, True)
approx = cv2.approxPolyDP(largest, 0.02 * peri, True)
if len(approx) != 4:
raise ValueError("无法检测到数独边框。")
pts = approx.reshape(4, 2)
rect = np.zeros((4, 2), dtype="float32")
s = pts.sum(axis=1)
rect[0] = pts[np.argmin(s)]
rect[2] = pts[np.argmax(s)]
diff = np.diff(pts, axis=1)
rect[1] = pts[np.argmin(diff)]
rect[3] = pts[np.argmax(diff)]
side = int(max(
np.linalg.norm(rect[0] - rect[1]),
np.linalg.norm(rect[1] - rect[2]),
np.linalg.norm(rect[2] - rect[3]),
np.linalg.norm(rect[3] - rect[0])
))
dst = np.array([[0, 0], [side-1, 0], [side-1, side-1], [0, side-1]], dtype="float32")
M = cv2.getPerspectiveTransform(rect, dst)
warp = cv2.warpPerspective(gray, M, (side, side))
return warp
def ocr_cells(warped):
side = warped.shape[0]
cell = side // 9
grid = []
config = "--psm 10 -c tessedit_char_whitelist=0123456789"
for y in range(9):
row = []
for x in range(9):
img = warped[y*cell:(y+1)*cell, x*cell:(x+1)*cell]
_, thr = cv2.threshold(img, 0, 255, cv2.THRESH_BINARY_INV + cv2.THRESH_OTSU)
sz = cv2.resize(thr, None, fx=2, fy=2, interpolation=cv2.INTER_CUBIC)
txt = pytesseract.image_to_string(sz, config=config).strip()
row.append(int(txt) if txt.isdigit() else 0)
grid.append(row)
return grid
# 题库与解答存储
PUZZLES, SOLUTIONS = [], []
class SudokuGUI:
def __init__(self, root):
self.root = root
root.title("Numba & OCR 数独求解器")
# 创建 9x9 输入框
self.entries = [[tk.Entry(root, width=2, font=('Arial',18), justify='center') for _ in range(9)] for _ in range(9)]
for i in range(9):
for j in range(9):
self.entries[i][j].grid(row=i, column=j, padx=1, pady=1)
# 按钮区
self.btn_frame = tk.Frame(root)
self.btn_frame.grid(row=9, column=0, columnspan=9, pady=5)
buttons = [
("OCR 识别", self.load_image),
("读取题库", self.load_library),
("生成新题", self.generate),
("求解", self._start_solve),
("保存步骤GIF", self.save_gif),
("清空", self.clear)
]
for text, cmd in buttons:
tk.Button(self.btn_frame, text=text, width=10, command=cmd).pack(side='left', padx=2)
self.time_label = tk.Label(root, text='', font=('Arial',12))
self.time_label.grid(row=10, column=0, columnspan=9)
def clear(self):
for row in self.entries:
for cell in row:
cell.delete(0, tk.END)
self.time_label.config(text='')
def load_library(self):
path = filedialog.askopenfilename(filetypes=[("CSV","*.csv")])
if not path:
return
try:
with open(path, newline='') as f:
reader = csv.DictReader(f)
PUZZLES.clear()
SOLUTIONS.clear()
for row in reader:
pu = row['puzzle'].strip()
so = row.get('solution', '').strip()
if len(pu) == 81:
PUZZLES.append([int(c) for c in pu])
SOLUTIONS.append([int(c) for c in so] if len(so) == 81 else None)
messagebox.showinfo("成功", f"加载 {len(PUZZLES)} 道题")
except Exception as e:
messagebox.showerror("错误", f"读取失败：{e}")
def generate(self):
if not PUZZLES:
messagebox.showwarning("提示", "请先读取题库！")
return
flat = random.choice(PUZZLES)
self.clear()
for idx, val in enumerate(flat):
if val:
r, c = divmod(idx, 9)
self.entries[r][c].insert(0, str(val))
def load_image(self):
path = filedialog.askopenfilename(filetypes=[("Image files", "*.png;*.jpg;*.bmp")])
if not path:
return
try:
warped = extract_sudoku_grid(path)
grid = ocr_cells(warped)
self.clear()
for i in range(9):
for j in range(9):
if grid[i][j]:
self.entries[i][j].insert(0, str(grid[i][j]))
except Exception as e:
messagebox.showerror("错误", str(e))
def _start_solve(self):
threading.Thread(target=self.solve).start()
def solve(self):
for btn in self.btn_frame.winfo_children():
btn.config(state='disabled')
try:
board = np.zeros((9,9), int)
for i in range(9):
for j in range(9):
v = self.entries[i][j].get().strip()
board[i,j] = int(v) if v.isdigit() else 0
start = time.time()
success = solve_sudoku(board)
elapsed = time.time() - start
if success:
self.clear()
for i in range(9):
for j in range(9):
self.entries[i][j].insert(0, str(board[i,j]))
self.time_label.config(text=f"求解用时: {elapsed:.3f}s")
else:
messagebox.showwarning("失败", "无解！")
finally:
for btn in self.btn_frame.winfo_children():
btn.config(state='normal')
def save_gif(self):
board = np.zeros((9,9), int)
for i in range(9):
for j in range(9):
v = self.entries[i][j].get().strip()
board[i,j] = int(v) if v.isdigit() else 0
solved = board.copy()
solve_sudoku(solved)
steps = []
solve_with_steps(board.copy(), steps)
if not steps:
steps = [board]
steps.append(solved)
max_frames = 20
if len(steps) > max_frames:
indices = np.linspace(0, len(steps)-1, max_frames, dtype=int)
steps = [steps[i] for i in indices]
tmp = 'frames'
os.makedirs(tmp, exist_ok=True)
files = []
for idx, b in enumerate(steps):
fig, ax = plt.subplots(figsize=(4,4))
ax.axis('off')
for k in range(10):
lw = 2 if k%3==0 else 1
ax.plot([k,k],[0,9],'k-',lw=lw)
ax.plot([0,9],[k,k],'k-',lw=lw)
for r in range(9):
for c in range(9):
if b[r,c]: ax.text(c+0.5, 8.5-r, str(b[r,c]), ha='center', va='center')
path = os.path.join(tmp, f'frame_{idx}.png')
fig.savefig(path)
plt.close(fig)
files.append(path)
out = filedialog.asksaveasfilename(defaultextension='.gif', filetypes=[('GIF','*.gif')])
if out:
imgs = [imageio.imread(f) for f in files]
imageio.mimsave(out, imgs, duration=0.2)
messagebox.showinfo("成功", f"已保存 {out}")
for f in files:
os.remove(f)
os.rmdir(tmp)
if __name__ == '__main__':
root = tk.Tk()
SudokuGUI(root)
root.mainloop()
进一步优化
import tkinter as tk
from tkinter import ttk, messagebox, filedialog
import numpy as np
from numba import njit
import threading, random, csv, time, os
import imageio, cv2, pytesseract, matplotlib.pyplot as plt
# 高 DPI 支持
class HiDPITk(tk.Tk):
def __init__(self):
super().__init__()
try: self.call('tk', 'scaling', 2.0)
except: pass
# 配置 Tesseract
pytesseract.pytesseract.tesseract_cmd = r'C:\Program Files\Tesseract-OCR\tesseract.exe'
# Numba 加速求解
@njit
def is_valid(b, r, c, n):
for i in range(9):
if b[r,i]==n or b[i,c]==n: return False
sr,sc=(r//3)*3,(c//3)*3
for i in range(3):
for j in range(3):
if b[sr+i,sc+j]==n: return False
return True
@njit
def solve_sudoku(b):
for r in range(9):
for c in range(9):
if b[r,c]==0:
for n in range(1,10):
if is_valid(b,r,c,n):
b[r,c]=n
if solve_sudoku(b): return True
b[r,c]=0
return False
return True
# 预编译
_dummy=np.zeros((9,9),np.int32)
solve_sudoku(_dummy.copy())
def solve_with_steps(b,steps):
for r in range(9):
for c in range(9):
if b[r,c]==0:
for n in range(1,10):
if n not in b[r,:] and n not in b[:,c] and n not in b[(r//3)*3:(r//3)*3+3,(c//3)*3:(c//3)*3+3]:
b[r,c]=n
steps.append(b.copy())
if solve_with_steps(b,steps): return True
b[r,c]=0
return False
return True
# 改进OCR提取
def extract_sudoku_grid(path):
img=cv2.imread(path)
gray=cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
# 自适应对比度
clahe=cv2.createCLAHE(clipLimit=2.0, tileGridSize=(8,8))
gray=clahe.apply(gray)
blur=cv2.GaussianBlur(gray,(5,5),0)
_,thresh=cv2.threshold(blur,0,255,cv2.THRESH_BINARY_INV+cv2.THRESH_OTSU)
# 膨胀填充
kernel=cv2.getStructuringElement(cv2.MORPH_RECT,(3,3))
thresh=cv2.morphologyEx(thresh, cv2.MORPH_CLOSE, kernel)
cnts,_=cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
maxc=max(cnts, key=cv2.contourArea)
peri=cv2.arcLength(maxc, True)
approx=cv2.approxPolyDP(maxc, 0.02*peri, True)
if len(approx)!=4: raise ValueError('无法检测到数独边框')
pts=approx.reshape(4,2)
# 排序点
rect=np.zeros((4,2),dtype='float32')
s=pts.sum(axis=1); rect[0]=pts[np.argmin(s)]; rect[2]=pts[np.argmax(s)]
diff=np.diff(pts,axis=1); rect[1]=pts[np.argmin(diff)]; rect[3]=pts[np.argmax(diff)]
side=int(max(np.linalg.norm(rect[0]-rect[1]), np.linalg.norm(rect[1]-rect[2]), np.linalg.norm(rect[2]-rect[3]), np.linalg.norm(rect[3]-rect[0])))
dst=np.array([[0,0],[side-1,0],[side-1,side-1],[0,side-1]],dtype='float32')
M=cv2.getPerspectiveTransform(rect, dst)
warp=cv2.warpPerspective(gray, M, (side, side))
return warp
def ocr_cells(warp):
side=warp.shape[0]; cell=side//9; grid=[]
config='--psm 10 -c tessedit_char_whitelist=123456789'
for y in range(9):
row=[]
for x in range(9):
sub=warp[y*cell:(y+1)*cell, x*cell:(x+1)*cell]
# 去噪点
_,th=cv2.threshold(sub,0,255,cv2.THRESH_BINARY_INV+cv2.THRESH_OTSU)
th=cv2.medianBlur(th,3)
conts,_=cv2.findContours(th,cv2.RETR_CCOMP,cv2.CHAIN_APPROX_SIMPLE)
mask=np.zeros(th.shape, dtype='uint8')
for cnt in conts:
area=cv2.contourArea(cnt)
if area>100: cv2.drawContours(mask,[cnt],-1,255,-1)
digit=cv2.bitwise_and(th,mask)
big=cv2.resize(digit,None,fx=3,fy=3,interpolation=cv2.INTER_CUBIC)
txt=pytesseract.image_to_string(big,config=config).strip()
row.append(int(txt) if txt.isdigit() else 0)
grid.append(row)
return grid
PUZZLES,SOLUTIONS=[],[]
class SudokuGUI(HiDPITk):
def __init__(self):
super().__init__(); self.title('数独求解器'); self.geometry('900x650'); self.resizable(True,True)
self.canvas=tk.Canvas(self,bg='white'); self.canvas.pack(fill='both',expand=True,padx=5,pady=5)
self.canvas.bind('<Configure>',self.draw)
self.entries=[[None]*9 for _ in range(9)]
btnf=ttk.Frame(self); btnf.pack(fill='x',pady=5)
for t,c in [('OCR',self.load_image),('载入题库',self.load_library),('随机新题',self.generate),('解题',self._start),('GIF',self.save_gif),('清空',self.clear)]:
ttk.Button(btnf,text=t,command=c).pack(side='left',padx=3)
self.time_label=ttk.Label(self,text='',font=('Arial',12)); self.time_label.pack(anchor='e',padx=5)
def draw(self,event):
self.canvas.delete('all'); w,h=self.canvas.winfo_width(),self.canvas.winfo_height(); size=min(w,h); cs=size/9
for r in range(9):
for c in range(9):
block=(r//3)*3+(c//3); color='lightblue' if block in (0,2,4,6,8) else 'white'
self.canvas.create_rectangle(c*cs,r*cs,(c+1)*cs,(r+1)*cs,fill=color,outline='')
for i in range(10): lw=3 if i%3==0 else 1; x=i*cs; self.canvas.create_line(x,0,x,9*cs,width=lw)
for i in range(10): lw=3 if i%3==0 else 1; y=i*cs; self.canvas.create_line(0,y,9*cs,y,width=lw)
for r in range(9):
for c in range(9):
if self.entries[r][c] is None:
e=tk.Entry(self.canvas,font=('Arial',28),justify='center',bd=0)
self.entries[r][c]=e
e=self.entries[r][c]
self.canvas.create_window(c*cs+cs/2,r*cs+cs/2,window=e,width=cs*0.9,height=cs*0.9)
def clear(self):
for r in range(9):
for c in range(9): self.entries[r][c].delete(0,'end')
self.time_label.config(text='')
def load_library(self):
p=filedialog.askopenfilename(filetypes=[('CSV','*.csv')]);
if not p: return
try:
with open(p) as f:
rdr=csv.DictReader(f); PUZZLES.clear(); SOLUTIONS.clear()
for row in rdr:
pu=row['puzzle'].strip(); so=row.get('solution','').strip()
if len(pu)==81: PUZZLES.append([int(ch) for ch in pu]); SOLUTIONS.append([int(ch) for ch in so] if len(so)==81 else None)
messagebox.showinfo('成功',f'加载{len(PUZZLES)}道题')
except Exception as e: messagebox.showerror('错误',str(e))
def generate(self):
if not PUZZLES: messagebox.showwarning('提示','请先加载题库'); return
flat=random.choice(PUZZLES); self.clear()
for idx,v in enumerate(flat):
if v: r,c=divmod(idx,9); self.entries[r][c].insert(0,str(v))
def load_image(self):
p=filedialog.askopenfilename(filetypes=[('IMG','*.png;*.jpg;*.bmp')]);
if not p: return
try:
warp=extract_sudoku_grid(p); grid=ocr_cells(warp); self.clear()
for r in range(9):
for c in range(9):
if grid[r][c]: self.entries[r][c].insert(0,str(grid[r][c]))
except Exception as e: messagebox.showerror('错误',str(e))
def _start(self): threading.Thread(target=self.solve,daemon=True).start()
def solve(self):
for b in self.children['!frame'].winfo_children(): b.config(state='disabled')
bd=np.zeros((9,9),int)
for r in range(9):
for c in range(9): v=self.entries[r][c].get().strip(); bd[r,c]=int(v) if v.isdigit() else 0
t0=time.time(); ok=solve_sudoku(bd); dt=time.time()-t0
if ok:
self.clear();
for r in range(9):
for c in range(9): self.entries[r][c].insert(0,str(bd[r,c]))
self.time_label.config(text=f'{dt:.3f}s')
else: messagebox.showwarning('无解','')
for b in self.children['!frame'].winfo_children(): b.config(state='normal')
def save_gif(self):
bd=np.zeros((9,9),int); files=[]; tmp='frames'
for r in range(9):
for c in range(9): v=self.entries[r][c].get().strip(); bd[r,c]=int(v) if v.isdigit() else 0
sol=bd.copy(); solve_sudoku(sol)
steps=[]; solve_with_steps(bd.copy(),steps)
if not steps: steps=[bd]
steps.append(sol)
if len(steps)>20: idxs=np.linspace(0,len(steps)-1,20,dtype=int); steps=[steps[i] for i in idxs]
os.makedirs(tmp,exist_ok=True)
for i,grid in enumerate(steps):
fig,ax=plt.subplots(figsize=(6,6),dpi=150); ax.axis('off')
for k in range(10): lw=3 if k%3==0 else 1; ax.plot([k,k],[0,9],'k-',lw=lw); ax.plot([0,9],[k,k],'k-',lw=lw)
for rr in range(9):
for cc in range(9):
if grid[rr][cc]: ax.text(cc+0.5,8.5-rr,str(grid[rr][cc]),ha='center',va='center',fontsize=24)
p=os.path.join(tmp,f'{i}.png'); fig.savefig(p); plt.close(fig); files.append(p)
out=filedialog.asksaveasfilename(defaultextension='.gif',filetypes=[('GIF','*.gif')])
if out: imageio.mimsave(out,[imageio.imread(f) for f in files],duration=0.2); messagebox.showinfo('成功','保存成功')
for f in files: os.remove(f)
os.rmdir(tmp)
if __name__=='__main__': SudokuGUI().mainloop()250529 3:19
进一步优化界面和解题算法，这个算法超级快。https://leetcode.cn/problems/sudoku-solver/solutions/650909/shi-zi-jiao-cha-shuang-xiang-xun-huan-li-xzyj/
import tkinter as tk
from tkinter import ttk, messagebox, filedialog, font as tkfont # Added tkfont
import numpy as np
import threading, random, csv, time, os
import imageio
import cv2
import pytesseract
import matplotlib.pyplot as plt
from typing import List
# --- HiDPI Support ---
class HiDPITk(tk.Tk):
def __init__(self):
super().__init__()
try:
self.tk.call('tk', 'scaling', 1.5)
except tk.TclError:
pass
# --- Tesseract Configuration ---
try:
pytesseract.pytesseract.tesseract_cmd = r'C:\Program Files\Tesseract-OCR\tesseract.exe'
# print(f"Tesseract version: {pytesseract.get_tesseract_version()}")
except Exception as e:
print(f"Tesseract configuration warning: {e}. OCR functionality might not work if Tesseract is not correctly configured.")
# --- DLX Algorithm (largely unchanged from previous version) ---
class DLX:
def __init__(self, n_sudoku_subgrid_size):
self.n_sq = n_sudoku_subgrid_size ** 2
self.num_columns = self.n_sq * self.n_sq * 4
self.head_node_idx = 0
max_data_nodes = (self.n_sq ** 3) * 4
self.max_nodes = max_data_nodes + self.num_columns + 1
self.u = [0] * self.max_nodes
self.d = [0] * self.max_nodes
self.l = [0] * self.max_nodes
self.r = [0] * self.max_nodes
self.row_header = [0] * self.max_nodes
self.col_header = [0] * self.max_nodes
for i in range(self.num_columns + 1):
self.u[i] = i
self.d[i] = i
self.l[i] = i - 1
self.r[i] = i + 1
self.col_header[i] = i
self.row_header[i] = 0
self.r[self.num_columns] = self.head_node_idx
self.l[self.head_node_idx] = self.num_columns
self.s = [0] * (self.num_columns + 1)
self.next_free_node_idx = self.num_columns + 1
self.solution_rows = [0] * (self.n_sq ** 2 + 10)
self.num_solution_rows = 0
self.dlx_row_to_sudoku_map = []
def _map_sudoku_to_dlx_cols(self, r_1idx, c_1idx, num_1idx):
n_sq = self.n_sq
n = int(np.sqrt(n_sq))
col1 = (r_1idx - 1) * n_sq + (c_1idx - 1) + 1
col2 = n_sq * n_sq + (r_1idx - 1) * n_sq + (num_1idx - 1) + 1
col3 = 2 * n_sq * n_sq + (c_1idx - 1) * n_sq + (num_1idx - 1) + 1
box_idx = ((r_1idx - 1) // n) * n + ((c_1idx - 1) // n)
col4 = 3 * n_sq * n_sq + box_idx * n_sq + (num_1idx - 1) + 1
return [col1, col2, col3, col4]
def add_dlx_row(self, dlx_row_id, column_indices):
first_node_in_row = self.next_free_node_idx
for i, c_idx in enumerate(column_indices):
node = self.next_free_node_idx
if i == 0:
self.l[node] = node
self.r[node] = node
else:
self.l[node] = node - 1
self.r[node - 1] = node
self.r[node] = first_node_in_row
self.l[first_node_in_row] = node
self.d[node] = c_idx
self.u[node] = self.u[c_idx]
self.d[self.u[c_idx]] = node
self.u[c_idx] = node
self.row_header[node] = dlx_row_id
self.col_header[node] = c_idx
self.s[c_idx] += 1
self.next_free_node_idx += 1
def _cover_column(self, c_idx):
self.r[self.l[c_idx]] = self.r[c_idx]
self.l[self.r[c_idx]] = self.l[c_idx]
i_node = self.d[c_idx]
while i_node != c_idx:
j_node = self.r[i_node]
while j_node != i_node:
self.d[self.u[j_node]] = self.d[j_node]
self.u[self.d[j_node]] = self.u[j_node]
self.s[self.col_header[j_node]] -= 1
j_node = self.r[j_node]
i_node = self.d[i_node]
def _uncover_column(self, c_idx):
i_node = self.u[c_idx]
while i_node != c_idx:
j_node = self.l[i_node]
while j_node != i_node:
self.s[self.col_header[j_node]] += 1
self.d[self.u[j_node]] = j_node
self.u[self.d[j_node]] = j_node
j_node = self.l[j_node]
i_node = self.u[i_node]
self.r[self.l[c_idx]] = c_idx
self.l[self.r[c_idx]] = c_idx
def dance(self, k_depth):
if self.r[self.head_node_idx] == self.head_node_idx:
self.num_solution_rows = k_depth
return True
c_chosen = self.r[self.head_node_idx]
if c_chosen == self.head_node_idx :
return False
min_s = self.s[c_chosen]
temp_node = self.r[self.head_node_idx]
while temp_node != self.head_node_idx:
if self.s[temp_node] < min_s:
min_s = self.s[temp_node]
c_chosen = temp_node
temp_node = self.r[temp_node]
self._cover_column(c_chosen)
r_node = self.d[c_chosen]
while r_node != c_chosen:
self.solution_rows[k_depth] = self.row_header[r_node]
j_node = self.r[r_node]
while j_node != r_node:
self._cover_column(self.col_header[j_node])
j_node = self.r[j_node]
if self.dance(k_depth + 1):
return True
j_node = self.l[r_node]
while j_node != r_node:
self._uncover_column(self.col_header[j_node])
j_node = self.l[j_node]
r_node = self.d[r_node]
self._uncover_column(c_chosen)
return False
def run_solver(self, input_sudoku_board_lol_str):
self.dlx_row_to_sudoku_map = []
current_dlx_row_id = 1
for r_0idx in range(self.n_sq):
for c_0idx in range(self.n_sq):
r_1idx, c_1idx = r_0idx + 1, c_0idx + 1
char_val = input_sudoku_board_lol_str[r_0idx][c_0idx]
if char_val != '.':
num_1idx = int(char_val)
self.dlx_row_to_sudoku_map.append({'id': current_dlx_row_id, 'r': r_1idx, 'c': c_1idx, 'num': num_1idx})
cols_for_dlx = self._map_sudoku_to_dlx_cols(r_1idx, c_1idx, num_1idx)
self.add_dlx_row(current_dlx_row_id, cols_for_dlx)
current_dlx_row_id += 1
else:
for num_1idx_try in range(1, self.n_sq + 1):
self.dlx_row_to_sudoku_map.append({'id': current_dlx_row_id, 'r': r_1idx, 'c': c_1idx, 'num': num_1idx_try})
cols_for_dlx = self._map_sudoku_to_dlx_cols(r_1idx, c_1idx, num_1idx_try)
self.add_dlx_row(current_dlx_row_id, cols_for_dlx)
current_dlx_row_id += 1
if self.dance(0):
for i in range(self.num_solution_rows):
dlx_row_id_solved = self.solution_rows[i]
entry = next((item for item in self.dlx_row_to_sudoku_map if item['id'] == dlx_row_id_solved), None)
if entry:
r, c, num = entry['r'], entry['c'], entry['num']
input_sudoku_board_lol_str[r-1][c-1] = str(num)
else:
print(f"Error: Solved DLX row ID {dlx_row_id_solved} not found in map during reconstruction.")
return False
return True
else:
return False
def solve_sudoku_dlx(board_numpy_input):
board_numpy = board_numpy_input.copy()
board_lol_str = [['.' for _ in range(9)] for _ in range(9)]
for r in range(9):
for c in range(9):
if board_numpy[r, c] != 0:
board_lol_str[r][c] = str(board_numpy[r, c])
dlx_solver = DLX(n_sudoku_subgrid_size=3)
success = dlx_solver.run_solver(board_lol_str)
if success:
solved_board_numpy = np.zeros((9, 9), dtype=int)
for r in range(9):
for c in range(9):
if board_lol_str[r][c] != '.' and board_lol_str[r][c].isdigit():
solved_board_numpy[r, c] = int(board_lol_str[r][c])
return True, solved_board_numpy
else:
return False, board_numpy_input
# --- OCR and Image Processing Functions ---
def extract_sudoku_grid(path):
img = cv2.imread(path)
if img is None:
raise ValueError(f"无法从路径读取图片: {path}")
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
clahe = cv2.createCLAHE(clipLimit=2.0, tileGridSize=(8,8))
gray_contrast = clahe.apply(gray)
blur = cv2.GaussianBlur(gray_contrast, (5,5), 0)
_, thresh = cv2.threshold(blur, 0, 255, cv2.THRESH_BINARY_INV + cv2.THRESH_OTSU)
kernel = cv2.getStructuringElement(cv2.MORPH_RECT, (3,3))
thresh_closed = cv2.morphologyEx(thresh, cv2.MORPH_CLOSE, kernel)
contours_tuple = cv2.findContours(thresh_closed, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
cnts = contours_tuple[0] if len(contours_tuple) == 2 else contours_tuple[1]
if not cnts:
raise ValueError('图片中未找到轮廓。')
maxc = max(cnts, key=cv2.contourArea)
peri = cv2.arcLength(maxc, True)
approx = cv2.approxPolyDP(maxc, 0.02 * peri, True)
if len(approx) != 4:
largest_quad = None
max_area_quad = 0
for cnt_fallback in cnts:
peri_fallback = cv2.arcLength(cnt_fallback, True)
approx_fallback = cv2.approxPolyDP(cnt_fallback, 0.02 * peri_fallback, True)
if len(approx_fallback) == 4:
area_fallback = cv2.contourArea(approx_fallback)
if area_fallback > max_area_quad:
if cv2.isContourConvex(approx_fallback):
x_br, y_br, w_br, h_br = cv2.boundingRect(approx_fallback)
aspect_ratio = float(w_br)/h_br
if 0.8 < aspect_ratio < 1.2:
largest_quad = approx_fallback
max_area_quad = area_fallback
if largest_quad is not None:
approx = largest_quad
else:
raise ValueError('无法检测到数独边框。请确保图片清晰且网格突出。')
pts = approx.reshape(4, 2)
rect = np.zeros((4, 2), dtype='float32')
s = pts.sum(axis=1)
rect[0] = pts[np.argmin(s)]
rect[2] = pts[np.argmax(s)]
diff = np.diff(pts, axis=1)
rect[1] = pts[np.argmin(diff)]
rect[3] = pts[np.argmax(diff)]
side_length_warped = 450
dst_pts = np.array([[0,0], [side_length_warped-1,0], [side_length_warped-1,side_length_warped-1], [0,side_length_warped-1]], dtype='float32')
M = cv2.getPerspectiveTransform(rect, dst_pts)
warp = cv2.warpPerspective(gray, M, (side_length_warped, side_length_warped))
return warp
def ocr_cells(warp):
"""Performs OCR on individual cells of the warped Sudoku grid with enhancements."""
side = warp.shape[0]
cell_dim = side // 9
grid_from_ocr = []
config = '--psm 10 -c tessedit_char_whitelist=123456789'
for y_offset in range(9):
row_from_ocr = []
for x_offset in range(9):
pad_ratio = 0.15 # Slightly increased padding ratio
pad = int(cell_dim * pad_ratio)
y_start, y_end = y_offset * cell_dim + pad, (y_offset + 1) * cell_dim - pad
x_start, x_end = x_offset * cell_dim + pad, (x_offset + 1) * cell_dim - pad
y_start, x_start = max(0, y_start), max(0, x_start)
y_end, x_end = min(side, y_end), min(side, x_end)
if y_start >= y_end or x_start >= x_end:
row_from_ocr.append(0)
continue
cell_img_gray = warp[y_start:y_end, x_start:x_end]
# --- OCR Enhancement: Isolate digit using contours ---
# Resize for initial processing
cell_resized = cv2.resize(cell_img_gray, (100, 100), interpolation=cv2.INTER_AREA) # Standard size for contour finding
# Adaptive thresholding might be better for varying lighting within cells
cell_thresh = cv2.adaptiveThreshold(cell_resized, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C,
cv2.THRESH_BINARY_INV, 11, 2) # Inverted for findContours
# Find contours of the digit
contours, _ = cv2.findContours(cell_thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
digit_isolated_img = cell_resized # Fallback to resized cell if no good contour
if contours:
largest_contour = max(contours, key=cv2.contourArea)
area = cv2.contourArea(largest_contour)
x_c, y_c, w_c, h_c = cv2.boundingRect(largest_contour)
# Filter contour: area, aspect ratio, extent (ratio of contour area to bounding box area)
# These thresholds are heuristic and might need tuning
min_area_ratio = 0.1 # Min area relative to cell_resized area
if area > (cell_resized.shape[0] * cell_resized.shape[1] * min_area_ratio) and \
0.2 < (w_c / h_c if h_c > 0 else 0) < 1.5 and \
area / (w_c * h_c if w_c*h_c > 0 else 1) > 0.3 :
mask = np.zeros_like(cell_resized)
cv2.drawContours(mask, [largest_contour], -1, (255), thickness=cv2.FILLED)
# Create a white background image
white_bg = np.ones_like(cell_resized, dtype=np.uint8) * 255
# Use the mask to take the digit from original (or thresholded) and place on white_bg
# To get black digit on white bg for Tesseract:
# Option 1: Use original gray, threshold it, then mask.
# Option 2: Use already thresholded (cell_thresh, which is white digit on black), invert it, then mask.
# Let's use cell_thresh (white digit/black_bg), invert it to black_digit/white_bg, then mask
digit_on_black_bg = cv2.bitwise_and(cell_thresh, cell_thresh, mask=mask)
digit_on_white_bg = cv2.bitwise_not(digit_on_black_bg) # Invert: black digit, white elsewhere
# Crop to bounding box of the digit for tighter fit, then add padding
cropped_digit = digit_on_white_bg[y_c:y_c+h_c, x_c:x_c+w_c]
# Add a white border for Tesseract
border_size = 15 # Pixels
digit_isolated_img = cv2.copyMakeBorder(cropped_digit, border_size, border_size,
border_size, border_size,
cv2.BORDER_CONSTANT, value=[255]) # White border
# else: contour not good, use cell_resized or cell_thresh inverted
# Final prep for Tesseract (resize again if needed, ensure black text on white)
# If digit_isolated_img is from cell_resized (gray), it needs thresholding.
# If from contour processing, it should already be black on white.
if len(digit_isolated_img.shape) == 2 and digit_isolated_img.dtype == np.uint8: # Check if it's a grayscale/binary image
# If it's not already black on white (e.g. if fallback was used with gray cell_resized)
# We need to ensure it is. For simplicity, if fallback, we use the original path.
if digit_isolated_img is cell_resized: # Fallback was used
final_ocr_img = cv2.resize(cell_img_gray, None, fx=3, fy=3, interpolation=cv2.INTER_CUBIC)
_, final_ocr_img = cv2.threshold(final_ocr_img, 0, 255, cv2.THRESH_BINARY + cv2.THRESH_OTSU)
else: # Contour isolation was successful
final_ocr_img = cv2.resize(digit_isolated_img, (150,150), interpolation=cv2.INTER_LANCZOS4) # Resize isolated digit
else: # Should not happen, but as a safeguard
final_ocr_img = cv2.resize(cell_img_gray, None, fx=3, fy=3, interpolation=cv2.INTER_CUBIC)
_, final_ocr_img = cv2.threshold(final_ocr_img, 0, 255, cv2.THRESH_BINARY + cv2.THRESH_OTSU)
txt = pytesseract.image_to_string(final_ocr_img, config=config).strip()
row_from_ocr.append(int(txt) if txt.isdigit() else 0)
grid_from_ocr.append(row_from_ocr)
return grid_from_ocr
# --- Sudoku Step-by-Step Solver (for GIF, uses simple backtracking) ---
def is_valid_for_gif(board, r, c, num):
if num in board[r, :]: return False
if num in board[:, c]: return False
start_row, start_col = 3 * (r // 3), 3 * (c // 3)
if num in board[start_row:start_row + 3, start_col:start_col + 3].flatten(): return False
return True
def solve_with_steps(board_for_gif_steps, steps_list):
for r in range(9):
for c in range(9):
if board_for_gif_steps[r, c] == 0:
for num_try in range(1, 10):
if is_valid_for_gif(board_for_gif_steps, r, c, num_try):
board_for_gif_steps[r, c] = num_try
steps_list.append(board_for_gif_steps.copy())
if solve_with_steps(board_for_gif_steps, steps_list):
return True
board_for_gif_steps[r, c] = 0
return False
return True
# --- Global Variables for Puzzle Library ---
PUZZLES, SOLUTIONS = [], []
# --- Sudoku GUI ---
class SudokuGUI(HiDPITk):
def __init__(self):
super().__init__()
self.title('数独求解器 (DLX OCR增强版)')
self.geometry('750x800') # Increased size slightly
self.resizable(True, True)
self.configure(bg='#F0F0F0') # Light gray background for the window
# --- Define modern fonts ---
try:
self.default_font = tkfont.nametofont("TkDefaultFont")
self.default_font.configure(family="Segoe UI Variable Text", size=10) # More modern font
self.header_font = tkfont.Font(family="Segoe UI Variable Display", size=12, weight="bold")
self.entry_font_spec = ("Segoe UI Variable Text", 22, "bold") # For Sudoku cells
self.button_font_spec = ("Segoe UI Variable Text", 10)
except tk.TclError: # Fallback fonts if Segoe UI is not available
self.default_font = tkfont.nametofont("TkDefaultFont")
self.default_font.configure(family="Arial", size=10)
self.header_font = tkfont.Font(family="Arial", size=12, weight="bold")
self.entry_font_spec = ("Arial", 22, "bold")
self.button_font_spec = ("Arial", 10)
# Apply default font to root window to affect some widgets
self.option_add("*Font", self.default_font)
# --- Canvas for Sudoku Grid ---
self.canvas = tk.Canvas(self, bg='#FFFFFF', highlightthickness=1, highlightbackground='#B0B0B0')
self.canvas.pack(fill='both', expand=True, padx=20, pady=(20,10)) # Increased padding
self.canvas.bind('<Configure>', self.draw_grid_and_entries)
self.entries = [[None for _ in range(9)] for _ in range(9)]
self.initial_puzzle_for_ocr_highlight = None
# --- Control Buttons Frame ---
self.button_frame = ttk.Frame(self, style='Modern.TFrame', padding=(10,5))
self.button_frame.pack(fill='x', padx=15, pady=(0,10))
# Style for frame and buttons
s = ttk.Style()
s.configure('Modern.TFrame', background='#F0F0F0')
s.configure('Modern.TButton', font=self.button_font_spec, padding=(10, 5), relief='flat', borderwidth=1)
s.map('Modern.TButton',
background=[('active', '#D0D0D0'), ('!disabled', '#E0E0E0')],
relief=[('pressed', 'sunken'), ('!pressed', 'raised')])
buttons_config = [
('OCR 读取', self.load_image_and_populate_grid),
('加载题库', self.load_puzzle_library),
('新题目', self.generate_puzzle_from_library),
('求解 (DLX)', self.start_solve_thread),
('保存 GIF', self.save_solution_gif),
('清空面板', self.clear_board_and_time)
]
for i, (text, command) in enumerate(buttons_config):
btn = ttk.Button(self.button_frame, text=text, command=command, style='Modern.TButton', width=12)
btn.grid(row=0, column=i, padx=5, pady=5, sticky='ew')
self.button_frame.grid_columnconfigure(i, weight=1)
# --- Time Label ---
self.time_label = ttk.Label(self, text='用时: N/A', font=self.default_font, background='#F0F0F0')
self.time_label.pack(anchor='e', padx=20, pady=(0,10))
self.draw_grid_and_entries()
def draw_grid_and_entries(self, event=None):
self.canvas.delete('all')
width = self.canvas.winfo_width()
height = self.canvas.winfo_height()
if width < 50 or height < 50: return
grid_size = min(width, height) * 0.95 # Slightly less padding inside canvas
cell_size = grid_size / 9
offset_x = (width - grid_size) / 2
offset_y = (height - grid_size) / 2
# Softer grid colors
color_light_cell = '#F8F8F8'
color_dark_cell = '#E8E8E8'
grid_line_color = '#C0C0C0'
thick_grid_line_color = '#808080'
for r in range(9):
for c in range(9):
x0, y0 = offset_x + c * cell_size, offset_y + r * cell_size
x1, y1 = x0 + cell_size, y0 + cell_size
block_r, block_c = r // 3, c // 3
fill_color = color_light_cell if (block_r + block_c) % 2 == 0 else color_dark_cell
self.canvas.create_rectangle(x0, y0, x1, y1, fill=fill_color, outline=grid_line_color, width=0.5) # Thinner outlines for cells
for i in range(10):
line_width = 2.0 if i % 3 == 0 else 0.8 # Adjusted line widths
current_line_color = thick_grid_line_color if i % 3 == 0 else grid_line_color
x_line = offset_x + i * cell_size
self.canvas.create_line(x_line, offset_y, x_line, offset_y + grid_size, width=line_width, fill=current_line_color)
y_line = offset_y + i * cell_size
self.canvas.create_line(offset_x, y_line, offset_x + grid_size, y_line, width=line_width, fill=current_line_color)
# Dynamic font size for entries based on cell_size
entry_font_size = max(12, int(cell_size / 2.2))
current_entry_font = (self.entry_font_spec[0], entry_font_size, self.entry_font_spec[2])
for r_idx in range(9):
for c_idx in range(9):
entry_bg_color = color_light_cell if ((r_idx//3) + (c_idx//3)) % 2 == 0 else color_dark_cell
if self.entries[r_idx][c_idx] is None:
entry = tk.Entry(self.canvas, font=current_entry_font, justify='center', bd=0,
relief='flat',
# disabledbackground is tricky with ttk themes, set bg directly
bg=entry_bg_color
)
vcmd = (self.register(self.validate_entry), '%P')
entry.config(validate='key', validatecommand=vcmd)
self.entries[r_idx][c_idx] = entry
entry_widget = self.entries[r_idx][c_idx]
is_initial_number = False
current_value_in_widget = ""
if self.initial_puzzle_for_ocr_highlight is not None and \
self.initial_puzzle_for_ocr_highlight[r_idx, c_idx] != 0:
is_initial_number = True
current_value_in_widget = str(self.initial_puzzle_for_ocr_highlight[r_idx, c_idx])
entry_widget.config(state='normal', bg=entry_bg_color)
entry_widget.delete(0, 'end')
if current_value_in_widget:
entry_widget.insert(0, current_value_in_widget)
text_color_initial = '#003399' # Darker blue for initial
text_color_solved = '#CC0000' # Darker red for solved
text_color_normal = '#333333' # Dark gray for normal input
if is_initial_number:
entry_widget.config(fg=text_color_initial, state='disabled', disabledforeground=text_color_initial, readonlybackground=entry_bg_color)
else:
current_text_in_entry = entry_widget.get()
if current_text_in_entry:
entry_widget.config(fg=text_color_solved)
else:
entry_widget.config(fg=text_color_normal)
entry_widget.config(state='normal')
entry_x = offset_x + c_idx * cell_size + cell_size / 2
entry_y = offset_y + r_idx * cell_size + cell_size / 2
self.canvas.create_window(entry_x, entry_y, window=entry_widget,
width=cell_size * 0.8, height=cell_size * 0.8) # Slightly smaller entry box
def validate_entry(self, P):
if P == "" or (P.isdigit() and len(P) == 1 and P != '0'):
return True
return False
def clear_board_and_time(self):
self.initial_puzzle_for_ocr_highlight = None
for r in range(9):
for c in range(9):
if self.entries[r][c]:
self.entries[r][c].config(state='normal')
self.entries[r][c].delete(0, 'end')
# Reset color in draw_grid_and_entries
self.time_label.config(text='用时: N/A')
self.draw_grid_and_entries()
def load_puzzle_library(self):
filepath = filedialog.askopenfilename(
title="加载数独题库",
filetypes=[('CSV 文件', '*.csv'), ('文本文件', '*.txt')]
)
if not filepath: return
global PUZZLES, SOLUTIONS
PUZZLES.clear(); SOLUTIONS.clear()
loaded_count = 0
try:
with open(filepath, 'r', encoding='utf-8') as f:
if filepath.endswith('.csv'):
reader = csv.DictReader(f)
if 'puzzle' not in reader.fieldnames:
messagebox.showerror('格式错误', "CSV文件必须包含 'puzzle' 列标题。")
return
for row_num, row_data in enumerate(reader):
puzzle_str = row_data.get('puzzle', '').strip()
solution_str = row_data.get('solution', '').strip()
if len(puzzle_str) == 81 and all(c.isdigit() or c == '.' or c == '0' for c in puzzle_str):
PUZZLES.append([int(ch) if ch.isdigit() and ch != '0' else 0 for ch in puzzle_str.replace('.', '0')])
if solution_str and len(solution_str) == 81 and all(c.isdigit() and c != '0' for c in solution_str):
SOLUTIONS.append([int(ch) for ch in solution_str])
else:
SOLUTIONS.append(None)
loaded_count +=1
else:
print(f"跳过CSV文件无效的题目字符串，行 {row_num+1}: {puzzle_str}")
else:
for line_num, line in enumerate(f):
puzzle_str = line.strip()
if len(puzzle_str) == 81 and all(c.isdigit() or c == '.' or c == '0' for c in puzzle_str):
PUZZLES.append([int(ch) if ch.isdigit() and ch != '0' else 0 for ch in puzzle_str.replace('.', '0')])
SOLUTIONS.append(None)
loaded_count += 1
else:
print(f"跳过TXT文件无效的题目字符串，行 {line_num+1}: {puzzle_str}")
if loaded_count > 0:
messagebox.showinfo('题库已加载', f'成功加载 {loaded_count} 个题目。')
self.generate_puzzle_from_library()
else:
messagebox.showwarning('题库为空', '选择的文件中未找到有效的题目。')
except Exception as e:
messagebox.showerror('加载题库错误', str(e))
def generate_puzzle_from_library(self):
if not PUZZLES:
messagebox.showwarning('无题目', '请先加载题库。')
return
self.clear_board_and_time()
puzzle_flat_list = random.choice(PUZZLES)
self.initial_puzzle_for_ocr_highlight = np.array(puzzle_flat_list).reshape(9,9)
self.draw_grid_and_entries()
def load_image_and_populate_grid(self):
filepath = filedialog.askopenfilename(
title="加载数独图片",
filetypes=[('图片文件', '*.png;*.jpg;*.jpeg;*.bmp;*.tiff')]
)
if not filepath: return
self.clear_board_and_time()
try:
warped_grid_img = extract_sudoku_grid(filepath)
ocr_result_grid_list_of_lists = ocr_cells(warped_grid_img)
self.initial_puzzle_for_ocr_highlight = np.array(ocr_result_grid_list_of_lists)
self.draw_grid_and_entries()
messagebox.showinfo("OCR 完成", "已从图片中提取数字。请检查并点击 '求解'。")
except ValueError as ve:
messagebox.showerror('图片处理错误', str(ve))
except pytesseract.TesseractNotFoundError:
messagebox.showerror('Tesseract 错误', "未安装Tesseract或未在系统路径中找到。请安装Tesseract OCR并确保其配置正确。")
except Exception as e:
messagebox.showerror('加载图片错误', f'发生意外错误: {str(e)}')
def start_solve_thread(self):
for child_widget in self.button_frame.winfo_children():
if isinstance(child_widget, ttk.Button):
child_widget.config(state='disabled')
self.time_label.config(text="求解中...")
solve_thread = threading.Thread(target=self.solve_puzzle_with_dlx, daemon=True)
solve_thread.start()
def solve_puzzle_with_dlx(self):
current_board_numpy = np.zeros((9, 9), dtype=int)
has_input = False
for r in range(9):
for c in range(9):
val_str = self.entries[r][c].get().strip()
if val_str.isdigit():
current_board_numpy[r, c] = int(val_str)
if current_board_numpy[r,c] != 0: has_input = True
else:
current_board_numpy[r, c] = 0
if not has_input:
messagebox.showwarning("面板为空", "面板为空。请加载题目或输入数字。")
self.time_label.config(text='用时: N/A')
for child_widget in self.button_frame.winfo_children():
if isinstance(child_widget, ttk.Button):
child_widget.config(state='normal')
return
start_time = time.time()
success, solved_board = solve_sudoku_dlx(current_board_numpy.copy())
elapsed_time = time.time() - start_time
# After solving, update self.initial_puzzle_for_ocr_highlight
# to include the solved numbers, so draw_grid_and_entries colors them correctly
# Or, more directly, update entry colors here.
if success:
for r_idx in range(9):
for c_idx in range(9):
entry_widget = self.entries[r_idx][c_idx]
is_initial = self.initial_puzzle_for_ocr_highlight is not None and \
self.initial_puzzle_for_ocr_highlight[r_idx, c_idx] != 0
entry_widget.config(state='normal')
entry_widget.delete(0, 'end')
if solved_board[r_idx, c_idx] != 0:
entry_widget.insert(0, str(solved_board[r_idx, c_idx]))
text_color_initial = '#003399'
text_color_solved = '#CC0000'
if is_initial:
entry_widget.config(fg=text_color_initial, state='disabled', disabledforeground=text_color_initial)
elif solved_board[r_idx, c_idx] != 0 :
entry_widget.config(fg=text_color_solved, state='normal')
else:
entry_widget.config(fg='#333333', state='normal')
self.time_label.config(text=f'用时: {elapsed_time:.4f}s (DLX)')
else:
messagebox.showwarning('无解', 'DLX算法未能找到此题的解。')
self.time_label.config(text='用时: 无解')
for child_widget in self.button_frame.winfo_children():
if isinstance(child_widget, ttk.Button):
child_widget.config(state='normal')
# self.draw_grid_and_entries() # Call to ensure styles are consistently applied after solve
def save_solution_gif(self):
initial_board_numpy = np.zeros((9, 9), dtype=int)
has_input = False
for r in range(9):
for c in range(9):
val_str = self.entries[r][c].get().strip()
if val_str.isdigit():
initial_board_numpy[r, c] = int(val_str)
if initial_board_numpy[r,c] != 0: has_input = True
if not has_input:
messagebox.showwarning("面板为空", "无法从空面板生成GIF。")
return
dlx_success, final_solved_board_dlx = solve_sudoku_dlx(initial_board_numpy.copy())
if not dlx_success:
messagebox.showerror("求解器错误", "DLX无法解开此题目，无法生成GIF。")
return
gif_steps = []
board_for_gif_generation = initial_board_numpy.copy()
gif_steps.append(initial_board_numpy.copy())
solve_with_steps(board_for_gif_generation, gif_steps)
if not gif_steps or not np.array_equal(gif_steps[-1], final_solved_board_dlx):
if gif_steps and not np.array_equal(gif_steps[-1], final_solved_board_dlx):
pass
if not gif_steps or not np.array_equal(gif_steps[-1], final_solved_board_dlx):
gif_steps.append(final_solved_board_dlx.copy())
max_gif_frames = 30
if len(gif_steps) > max_gif_frames:
indices = np.linspace(0, len(gif_steps) - 1, max_gif_frames, dtype=int)
unique_indices = sorted(list(set(indices)))
gif_steps = [gif_steps[i] for i in unique_indices]
temp_frame_dir = 'sudoku_gif_frames'
os.makedirs(temp_frame_dir, exist_ok=True)
frame_files = []
try:
for i, board_state_numpy in enumerate(gif_steps):
fig, ax = plt.subplots(figsize=(5,5), dpi=120)
ax.set_aspect('equal')
ax.axis('off')
for k_line in range(10):
line_w = 2 if k_line % 3 == 0 else 0.5
ax.axvline(k_line, color='black', lw=line_w, ymin=0.05, ymax=0.95)
ax.axhline(k_line, color='black', lw=line_w, xmin=0.05, xmax=0.95)
ax.set_xlim(0, 9)
ax.set_ylim(0, 9)
for r_plot in range(9):
for c_plot in range(9):
if board_state_numpy[r_plot, c_plot] != 0:
num_val = board_state_numpy[r_plot, c_plot]
is_original_num = initial_board_numpy[r_plot, c_plot] == num_val and \
initial_board_numpy[r_plot,c_plot] !=0
text_color = '#003399' if is_original_num else '#CC0000' # Blue for original, Red for solved
if not is_original_num and i > 0 and gif_steps[i-1][r_plot, c_plot] == 0 and board_state_numpy[r_plot, c_plot] != 0:
text_color = '#009933' # Green for newly placed in this step
ax.text(c_plot + 0.5, 8.5 - r_plot, str(num_val),
ha='center', va='center', fontsize=18,
color=text_color, weight='bold')
frame_path = os.path.join(temp_frame_dir, f'frame_{i:03d}.png')
fig.savefig(frame_path, bbox_inches='tight', pad_inches=0.1)
plt.close(fig)
frame_files.append(frame_path)
gif_output_path = filedialog.asksaveasfilename(
defaultextension='.gif',
filetypes=[('GIF 动画', '*.gif')]
)
if gif_output_path:
try:
with imageio.get_writer(gif_output_path, mode='I', duration=200, loop=0) as writer:
for frame_f in frame_files:
image = imageio.v3.imread(frame_f)
writer.append_data(image)
except AttributeError:
images_for_mimsave = [imageio.imread(f) for f in frame_files]
imageio.mimsave(gif_output_path, images_for_mimsave, duration=0.2, loop=0)
messagebox.showinfo('GIF 已保存', f'解题动画已保存至 {gif_output_path}')
except Exception as e:
messagebox.showerror('GIF 生成错误', f'无法保存GIF: {str(e)}')
finally:
for f_path in frame_files:
try: os.remove(f_path)
except OSError: pass
try:
if os.path.exists(temp_frame_dir) and not os.listdir(temp_frame_dir):
os.rmdir(temp_frame_dir)
except OSError: pass
if __name__ == '__main__':
app = SudokuGUI()
app.mainloop()
暂时的最终版
import tkinter as tk
from tkinter import ttk, messagebox, filedialog, font as tkfont
import numpy as np
import threading, random, csv, time, os
import imageio
import cv2
import pytesseract
import matplotlib.pyplot as plt
from typing import List, Set, Tuple
# --- HiDPI 高分辨率支持 ---
class HiDPITk(tk.Tk):
def __init__(self):
super().__init__()
try:
# 尝试调整系统缩放比例以支持高分辨率显示器
self.tk.call('tk', 'scaling', 1.5)
except tk.TclError:
pass # 如果失败则忽略
# --- Tesseract OCR 配置 ---
try:
# 设置Tesseract OCR引擎的路径
pytesseract.pytesseract.tesseract_cmd = r'C:\Program Files\Tesseract-OCR\tesseract.exe'
except Exception as e:
print(f"Tesseract配置警告: {e}. 如果Tesseract未正确配置，OCR功能可能无法工作。")
# --- DLX 算法（精确覆盖问题算法）---
class DLX:
def __init__(self, n_sudoku_subgrid_size):
# 初始化DLX数据结构
self.n_sq = n_sudoku_subgrid_size ** 2 # 数独网格大小（9x9）
self.num_columns = self.n_sq * self.n_sq * 4 # 列数（324列）
self.head_node_idx = 0 # 头节点索引
max_data_nodes = (self.n_sq ** 3) * 4 # 最大节点数
self.max_nodes = max_data_nodes + self.num_columns + 1 # 总节点数
# 初始化节点数组（上下左右指针）
self.u = [0] * self.max_nodes # 上指针
self.d = [0] * self.max_nodes # 下指针
self.l = [0] * self.max_nodes # 左指针
self.r = [0] * self.max_nodes # 右指针
self.row_header = [0] * self.max_nodes # 行头
self.col_header = [0] * self.max_nodes # 列头
# 初始化列头节点
for i in range(self.num_columns + 1):
self.u[i] = i
self.d[i] = i
self.l[i] = i - 1
self.r[i] = i + 1
self.col_header[i] = i
self.row_header[i] = 0
# 将头节点连接成循环链表
self.r[self.num_columns] = self.head_node_idx
self.l[self.head_node_idx] = self.num_columns
# 初始化列大小计数器
self.s = [0] * (self.num_columns + 1)
self.next_free_node_idx = self.num_columns + 1 # 下一个空闲节点索引
self.solution_rows = [0] * (self.n_sq ** 2 + 10) # 存储解的行ID
self.num_solution_rows = 0 # 解的行数
self.dlx_row_to_sudoku_map = [] # DLX行到数独位置的映射
def _map_sudoku_to_dlx_cols(self, r_1idx, c_1idx, num_1idx):
# 将数独位置映射到DLX的列索引
n_sq = self.n_sq
n = int(np.sqrt(n_sq))
# 四种约束：行约束、列约束、数字约束、宫约束
col1 = (r_1idx - 1) * n_sq + (c_1idx - 1) + 1
col2 = n_sq * n_sq + (r_1idx - 1) * n_sq + (num_1idx - 1) + 1
col3 = 2 * n_sq * n_sq + (c_1idx - 1) * n_sq + (num_1idx - 1) + 1
box_idx = ((r_1idx - 1) // n) * n + ((c_1idx - 1) // n)
col4 = 3 * n_sq * n_sq + box_idx * n_sq + (num_1idx - 1) + 1
return [col1, col2, col3, col4]
def add_dlx_row(self, dlx_row_id, column_indices):
# 添加一行到DLX矩阵
first_node_in_row = self.next_free_node_idx
for i, c_idx in enumerate(column_indices):
node = self.next_free_node_idx
# 设置节点间的左右连接
if i == 0:
self.l[node] = node
self.r[node] = node
else:
self.l[node] = node - 1
self.r[node - 1] = node
self.r[node] = first_node_in_row
self.l[first_node_in_row] = node
# 设置节点间的上下连接
self.d[node] = c_idx
self.u[node] = self.u[c_idx]
self.d[self.u[c_idx]] = node
self.u[c_idx] = node
# 设置行头和列头
self.row_header[node] = dlx_row_id
self.col_header[node] = c_idx
self.s[c_idx] += 1 # 增加列计数
self.next_free_node_idx += 1 # 移动到下一个空闲节点
def _cover_column(self, c_idx):
# 覆盖一列（算法核心操作）
self.r[self.l[c_idx]] = self.r[c_idx]
self.l[self.r[c_idx]] = self.l[c_idx]
i_node = self.d[c_idx]
while i_node != c_idx:
j_node = self.r[i_node]
while j_node != i_node:
self.d[self.u[j_node]] = self.d[j_node]
self.u[self.d[j_node]] = self.u[j_node]
self.s[self.col_header[j_node]] -= 1
j_node = self.r[j_node]
i_node = self.d[i_node]
def _uncover_column(self, c_idx):
# 取消覆盖一列（回溯操作）
i_node = self.u[c_idx]
while i_node != c_idx:
j_node = self.l[i_node]
while j_node != i_node:
self.s[self.col_header[j_node]] += 1
self.d[self.u[j_node]] = j_node
self.u[self.d[j_node]] = j_node
j_node = self.l[j_node]
i_node = self.u[i_node]
self.r[self.l[c_idx]] = c_idx
self.l[self.r[c_idx]] = c_idx
def dance(self, k_depth):
# 递归求解精确覆盖问题（算法核心）
if self.r[self.head_node_idx] == self.head_node_idx:
self.num_solution_rows = k_depth
return True # 找到解
# 选择列（最小剩余值启发式）
c_chosen = self.r[self.head_node_idx]
if c_chosen == self.head_node_idx:
return False # 无解
min_s = self.s[c_chosen]
temp_node = self.r[self.head_node_idx]
while temp_node != self.head_node_idx:
if self.s[temp_node] < min_s:
min_s = self.s[temp_node]
c_chosen = temp_node
temp_node = self.r[temp_node]
# 覆盖选择的列
self._cover_column(c_chosen)
r_node = self.d[c_chosen]
while r_node != c_chosen:
# 尝试选择当前行
self.solution_rows[k_depth] = self.row_header[r_node]
# 覆盖与当前行冲突的列
j_node = self.r[r_node]
while j_node != r_node:
self._cover_column(self.col_header[j_node])
j_node = self.r[j_node]
# 递归搜索
if self.dance(k_depth + 1):
return True
# 回溯：取消覆盖
j_node = self.l[r_node]
while j_node != r_node:
self._uncover_column(self.col_header[j_node])
j_node = self.l[j_node]
r_node = self.d[r_node]
# 取消覆盖选择的列
self._uncover_column(c_chosen)
return False
def run_solver(self, input_sudoku_board_lol_str):
# 运行DLX求解器
self.dlx_row_to_sudoku_map = []
current_dlx_row_id = 1
# 构建DLX矩阵
for r_0idx in range(self.n_sq):
for c_0idx in range(self.n_sq):
r_1idx, c_1idx = r_0idx + 1, c_0idx + 1
char_val = input_sudoku_board_lol_str[r_0idx][c_0idx]
if char_val != '.':
# 已知数字
num_1idx = int(char_val)
self.dlx_row_to_sudoku_map.append({'id': current_dlx_row_id, 'r': r_1idx, 'c': c_1idx, 'num': num_1idx})
cols_for_dlx = self._map_sudoku_to_dlx_cols(r_1idx, c_1idx, num_1idx)
self.add_dlx_row(current_dlx_row_id, cols_for_dlx)
current_dlx_row_id += 1
else:
# 未知数字（尝试所有可能）
for num_1idx_try in range(1, self.n_sq + 1):
self.dlx_row_to_sudoku_map.append({'id': current_dlx_row_id, 'r': r_1idx, 'c': c_1idx, 'num': num_1idx_try})
cols_for_dlx = self._map_sudoku_to_dlx_cols(r_1idx, c_1idx, num_1idx_try)
self.add_dlx_row(current_dlx_row_id, cols_for_dlx)
current_dlx_row_id += 1
# 调用dancing links算法求解
if self.dance(0):
# 将解填充回数独板
for i in range(self.num_solution_rows):
dlx_row_id_solved = self.solution_rows[i]
entry = next((item for item in self.dlx_row_to_sudoku_map if item['id'] == dlx_row_id_solved), None)
if entry:
r, c, num = entry['r'], entry['c'], entry['num']
input_sudoku_board_lol_str[r-1][c-1] = str(num)
else:
print(f"错误: 解的行ID {dlx_row_id_solved} 在映射中未找到")
return False
return True
else:
return False
def solve_sudoku_dlx(board_numpy_input):
# 使用DLX求解数独的包装函数
board_numpy = board_numpy_input.copy()
board_lol_str = [['.' for _ in range(9)] for _ in range(9)]
# 将NumPy数组转换为字符串列表
for r in range(9):
for c in range(9):
if board_numpy[r, c] != 0:
board_lol_str[r][c] = str(board_numpy[r, c])
# 创建DLX求解器实例
dlx_solver = DLX(n_sudoku_subgrid_size=3)
success = dlx_solver.run_solver(board_lol_str)
if success:
# 将解转换回NumPy数组
solved_board_numpy = np.zeros((9, 9), dtype=int)
for r in range(9):
for c in range(9):
if board_lol_str[r][c] != '.' and board_lol_str[r][c].isdigit():
solved_board_numpy[r, c] = int(board_lol_str[r][c])
return True, solved_board_numpy
else:
return False, board_numpy_input
# --- OCR 和图像处理函数 ---
def extract_sudoku_grid(path):
# 从图像中提取数独网格
img = cv2.imread(path)
if img is None:
raise ValueError(f"无法从路径读取图片: {path}")
# 图像预处理
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
clahe = cv2.createCLAHE(clipLimit=2.0, tileGridSize=(8,8)) # 对比度受限自适应直方图均衡化
gray_contrast = clahe.apply(gray)
blur = cv2.GaussianBlur(gray_contrast, (5,5), 0) # 高斯模糊
_, thresh = cv2.threshold(blur, 0, 255, cv2.THRESH_BINARY_INV + cv2.THRESH_OTSU) # 二值化
kernel = cv2.getStructuringElement(cv2.MORPH_RECT, (3,3))
thresh_closed = cv2.morphologyEx(thresh, cv2.MORPH_CLOSE, kernel) # 形态学闭操作
# 查找轮廓
contours_tuple = cv2.findContours(thresh_closed, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
cnts = contours_tuple[0] if len(contours_tuple) == 2 else contours_tuple[1]
if not cnts:
raise ValueError('图片中未找到轮廓。')
# 找到最大轮廓（数独网格）
maxc = max(cnts, key=cv2.contourArea)
peri = cv2.arcLength(maxc, True)
approx = cv2.approxPolyDP(maxc, 0.02 * peri, True) # 多边形近似
# 处理非四边形情况
if len(approx) != 4:
largest_quad = None
max_area_quad = 0
for cnt_fallback in cnts:
peri_fallback = cv2.arcLength(cnt_fallback, True)
approx_fallback = cv2.approxPolyDP(cnt_fallback, 0.02 * peri_fallback, True)
if len(approx_fallback) == 4:
area_fallback = cv2.contourArea(approx_fallback)
if area_fallback > max_area_quad:
if cv2.isContourConvex(approx_fallback):
x_br, y_br, w_br, h_br = cv2.boundingRect(approx_fallback)
aspect_ratio = float(w_br)/h_br if h_br > 0 else 0
if 0.8 < aspect_ratio < 1.2: # 宽高比检查
largest_quad = approx_fallback
max_area_quad = area_fallback
if largest_quad is not None:
approx = largest_quad
else:
raise ValueError('无法检测到数独边框。请确保图片清晰且网格突出。')
# 透视变换准备
pts = approx.reshape(4, 2)
rect = np.zeros((4, 2), dtype='float32')
s = pts.sum(axis=1)
rect[0] = pts[np.argmin(s)] # 左上
rect[2] = pts[np.argmax(s)] # 右下
diff = np.diff(pts, axis=1)
rect[1] = pts[np.argmin(diff)] # 右上
rect[3] = pts[np.argmax(diff)] # 左下
# 执行透视变换
side_length_warped = 450
dst_pts = np.array([[0,0], [side_length_warped-1,0], [side_length_warped-1,side_length_warped-1], [0,side_length_warped-1]], dtype='float32')
M = cv2.getPerspectiveTransform(rect, dst_pts)
warp = cv2.warpPerspective(gray, M, (side_length_warped, side_length_warped))
return warp
def ocr_cells(warp):
# 对每个单元格进行OCR识别
side = warp.shape[0]
cell_dim = side // 9
grid_from_ocr = []
config = '--psm 10 -c tessedit_char_whitelist=123456789' # Tesseract配置
for y_offset in range(9):
row_from_ocr = []
for x_offset in range(9):
pad_ratio = 0.15
pad = int(cell_dim * pad_ratio)
# 计算单元格坐标（带内边距）
y_start, y_end = y_offset * cell_dim + pad, (y_offset + 1) * cell_dim - pad
x_start, x_end = x_offset * cell_dim + pad, (x_offset + 1) * cell_dim - pad
y_start, x_start = max(0, y_start), max(0, x_start)
y_end, x_end = min(side, y_end), min(side, x_end)
if y_start >= y_end or x_start >= x_end:
row_from_ocr.append(0)
continue
# 提取单元格图像
cell_img_gray = warp[y_start:y_end, x_start:x_end]
# 图像预处理
cell_resized = cv2.resize(cell_img_gray, (100, 100), interpolation=cv2.INTER_LANCZOS4)
cell_thresh = cv2.adaptiveThreshold(cell_resized, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C,
cv2.THRESH_BINARY_INV, 11, 2)
# 基于轮廓的数字提取
final_ocr_img = None
contours, _ = cv2.findContours(cell_thresh.copy(), cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
if contours:
largest_contour = max(contours, key=cv2.contourArea)
area = cv2.contourArea(largest_contour)
x_c, y_c, w_c, h_c = cv2.boundingRect(largest_contour)
# 数字轮廓启发式规则
min_area_ratio = 0.08
aspect_ratio_min, aspect_ratio_max = 0.15, 1.2
solidity_min = 0.25
if area > (cell_resized.shape[0] * cell_resized.shape[1] * min_area_ratio) and \
(h_c > 0 and aspect_ratio_min < (w_c / h_c) < aspect_ratio_max) and \
(w_c*h_c > 0 and area / (w_c * h_c) > solidity_min):
# 创建数字掩码
mask = np.zeros_like(cell_resized)
cv2.drawContours(mask, [largest_contour], -1, (255), thickness=cv2.FILLED)
# 提取数字
digit_on_black_bg = cv2.bitwise_and(cell_thresh, cell_thresh, mask=mask)
digit_on_white_bg = cv2.bitwise_not(digit_on_black_bg)
# 裁剪数字区域
cropped_digit = digit_on_white_bg[y_c:y_c+h_c, x_c:x_c+w_c]
if cropped_digit.size > 0:
# 添加白色边框
border_size = 20
digit_isolated_img_bordered = cv2.copyMakeBorder(cropped_digit, border_size, border_size,
border_size, border_size,
cv2.BORDER_CONSTANT, value=[255])
final_ocr_img = cv2.resize(digit_isolated_img_bordered, (150,150), interpolation=cv2.INTER_LANCZOS4)
# 回退策略：直接使用阈值图像
if final_ocr_img is None:
final_ocr_img = cv2.bitwise_not(cell_thresh)
border_size = 5
final_ocr_img = cv2.copyMakeBorder(final_ocr_img, border_size, border_size, border_size, border_size, cv2.BORDER_CONSTANT, value=[255])
# 执行OCR
txt = pytesseract.image_to_string(final_ocr_img, config=config).strip()
row_from_ocr.append(int(txt) if txt.isdigit() else 0)
grid_from_ocr.append(row_from_ocr)
return grid_from_ocr
# --- 数独逐步求解器（用于生成GIF）---
def is_valid_for_gif(board, r, c, num):
# 检查数字在行、列和宫中的有效性
if num in board[r, :]: return False
if num in board[:, c]: return False
start_row, start_col = 3 * (r // 3), 3 * (c // 3)
if num in board[start_row:start_row + 3, start_col:start_col + 3].flatten(): return False
return True
def solve_with_steps(board_for_gif_steps, steps_list):
# 回溯法求解数独（记录步骤）
for r in range(9):
for c in range(9):
if board_for_gif_steps[r, c] == 0:
for num_try in range(1, 10):
if is_valid_for_gif(board_for_gif_steps, r, c, num_try):
board_for_gif_steps[r, c] = num_try
steps_list.append(board_for_gif_steps.copy()) # 记录步骤
if solve_with_steps(board_for_gif_steps, steps_list):
return True
board_for_gif_steps[r, c] = 0 # 回溯
return False # 无解
return True # 已解决
# --- 全局变量（数独题库）---
PUZZLES, SOLUTIONS = [], [] # 存储数独题目和解
# --- 数独GUI主界面 ---
class SudokuGUI(HiDPITk):
def __init__(self):
super().__init__()
self.title('数独求解器')
self.geometry('850x800')
self.resizable(True, True)
self.configure(bg='#F0F0F0') # 背景色
# 字体配置
try:
self.default_font = tkfont.nametofont("TkDefaultFont")
self.default_font.configure(family="Segoe UI Variable Text", size=10)
self.header_font = tkfont.Font(family="Segoe UI Variable Display", size=12, weight="bold")
self.entry_font_spec = ("Segoe UI Variable Text", 22, "bold") # 单元格字体
self.button_font_spec = ("Segoe UI Variable Text", 10) # 按钮字体
except tk.TclError:
# 回退字体
self.default_font = tkfont.nametofont("TkDefaultFont")
self.default_font.configure(family="Arial", size=10)
self.header_font = tkfont.Font(family="Arial", size=12, weight="bold")
self.entry_font_spec = ("Arial", 22, "bold")
self.button_font_spec = ("Arial", 10)
self.option_add("*Font", self.default_font)
# 主画布（数独网格）
self.canvas = tk.Canvas(self, bg='#FFFFFF', highlightthickness=1, highlightbackground='#B0B0B0')
self.canvas.pack(fill='both', expand=True, padx=20, pady=(20,10))
self.canvas.bind('<Configure>', self.draw_grid_and_entries) # 窗口大小变化时重绘
# 输入框网格
self.entries = [[None for _ in range(9)] for _ in range(9)]
# 状态变量
self.active_problem_board: np.ndarray | None = None # 当前题目
self.active_solution_board: np.ndarray | None = None # 当前解
self.incorrect_cells_highlight_set: Set[Tuple[int, int]] = set() # 错误单元格
self.duplicate_cells_highlight_set: Set[Tuple[int, int]] = set() # 重复单元格
# 解题状态
self.solving_started = False # 用户是否开始解题
self.user_solve_start_time = None # 开始时间
self.timer_id = None # 计时器ID
self.timer_active = False # 计时器是否运行
# 按钮面板
self.button_frame = ttk.Frame(self, style='Modern.TFrame', padding=(10,5))
self.button_frame.pack(fill='x', padx=15, pady=(0,10))
# 按钮样式
s = ttk.Style()
s.configure('Modern.TFrame', background='#F0F0F0')
s.configure('Modern.TButton', font=self.button_font_spec, padding=(10, 5), relief='flat', borderwidth=1)
s.map('Modern.TButton',
background=[('active', '#D0D0D0'), ('!disabled', '#E0E0E0')],
relief=[('pressed', 'sunken'), ('!pressed', 'raised')])
# 按钮引用
self.start_solving_button = None
self.solve_dlx_button = None
self.check_answer_button = None
self.save_gif_button = None
# 按钮配置
buttons_config = [
('OCR 读取', self.load_image_and_populate_grid),
('加载题库', self.load_puzzle_library),
('新题目', self.generate_puzzle_from_library),
('开始做题', self.start_user_session),
('求解', self.start_solve_thread),
('对答案', self.check_answer),
('保存 GIF', self.save_solution_gif),
('清空面板', self.clear_board_and_time)
]
# 创建按钮
for i, (text, command) in enumerate(buttons_config):
btn = ttk.Button(self.button_frame, text=text, command=command, style='Modern.TButton', width=10)
btn.grid(row=0, column=i, padx=3, pady=5, sticky='ew')
self.button_frame.grid_columnconfigure(i, weight=1)
# 保存特殊按钮引用
if text == '开始做题': self.start_solving_button = btn
elif text == '求解': self.solve_dlx_button = btn
elif text == '对答案': self.check_answer_button = btn
elif text == '保存 GIF': self.save_gif_button = btn
# 计时标签
self.time_label = ttk.Label(self, text='用时: N/A', font=self.default_font, background='#F0F0F0')
self.time_label.pack(anchor='e', padx=20, pady=(0,10))
self._update_button_states() # 初始按钮状态
self.draw_grid_and_entries() # 初始绘制
def _reset_user_timer_and_session_state(self):
# 重置计时器和会话状态
self.solving_started = False
self.timer_active = False
if self.timer_id:
self.after_cancel(self.timer_id)
self.timer_id = None
self.user_solve_start_time = None
self.time_label.config(text='用时: N/A')
def _update_button_states(self):
# 根据状态更新按钮可用性
is_puzzle_loaded = self.active_problem_board is not None and np.any(self.active_problem_board != 0)
# 开始做题按钮
if self.start_solving_button:
self.start_solving_button.config(state='normal' if is_puzzle_loaded and not self.solving_started else 'disabled')
# 其他功能按钮
can_operate_on_board = is_puzzle_loaded or self.solving_started or np.any(self.get_current_gui_board() != 0)
if self.solve_dlx_button:
self.solve_dlx_button.config(state='normal' if can_operate_on_board else 'disabled')
if self.check_answer_button:
self.check_answer_button.config(state='normal' if can_operate_on_board else 'disabled')
if self.save_gif_button:
self.save_gif_button.config(state='normal' if can_operate_on_board else 'disabled')
def find_duplicate_entries(self, board: np.ndarray) -> Set[Tuple[int, int]]:
# 查找重复数字的单元格
duplicates = set()
n = 9
# 检查行
for r in range(n):
counts = {}
for c in range(n):
num = board[r, c]
if num != 0:
if num not in counts: counts[num] = []
counts[num].append(c)
for num_val, indices in counts.items():
if len(indices) > 1:
for c_idx in indices: duplicates.add((r, c_idx))
# 检查列
for c in range(n):
counts = {}
for r_idx_loop in range(n):
num = board[r_idx_loop, c]
if num != 0:
if num not in counts: counts[num] = []
counts[num].append(r_idx_loop)
for num_val, indices in counts.items():
if len(indices) > 1:
for r_idx_val in indices: duplicates.add((r_idx_val, c))
# 检查宫
for box_r_start in range(0, n, 3):
for box_c_start in range(0, n, 3):
counts = {}
for r_offset in range(3):
for c_offset in range(3):
r_cell, c_cell = box_r_start + r_offset, box_c_start + c_offset
num = board[r_cell, c_cell]
if num != 0:
if num not in counts: counts[num] = []
counts[num].append((r_cell,c_cell))
for num_val, cells_with_num in counts.items():
if len(cells_with_num) > 1:
for cell_r, cell_c in cells_with_num: duplicates.add((cell_r, cell_c))
return duplicates
def draw_grid_and_entries(self, event=None):
# 绘制数独网格和输入框
self.canvas.delete('all')
width = self.canvas.winfo_width()
height = self.canvas.winfo_height()
if width < 50 or height < 50: return
# 计算网格尺寸
grid_size = min(width, height) * 0.95
cell_size = grid_size / 9
offset_x = (width - grid_size) / 2
offset_y = (height - grid_size) / 2
# 颜色定义
color_light_cell = '#F8F8F8'
color_dark_cell = '#E8E8E8'
grid_line_color = '#C0C0C0'
thick_grid_line_color = '#808080'
color_error_bg = '#FFCCCC'
color_duplicate_bg = '#FFEB99'
text_color_initial = '#003399'
text_color_solved = '#CC0000'
text_color_normal = '#333333'
# 绘制单元格背景
for r in range(9):
for c in range(9):
x0, y0 = offset_x + c * cell_size, offset_y + r * cell_size
x1, y1 = x0 + cell_size, y0 + cell_size
# 判断是否为题目初始单元格
is_locked_problem_cell = (self.solving_started and \
self.active_problem_board is not None and \
self.active_problem_board[r, c] != 0)
# 设置单元格背景色
current_bg_color = color_light_cell if ((r//3) + (c//3)) % 2 == 0 else color_dark_cell
if (r, c) in self.duplicate_cells_highlight_set:
current_bg_color = color_duplicate_bg
elif (r, c) in self.incorrect_cells_highlight_set and not is_locked_problem_cell:
current_bg_color = color_error_bg
self.canvas.create_rectangle(x0, y0, x1, y1, fill=current_bg_color, outline=grid_line_color, width=0.5)
# 绘制网格线
for i in range(10):
line_width = 2.0 if i % 3 == 0 else 0.8
curr_line_color = thick_grid_line_color if i % 3 == 0 else grid_line_color
self.canvas.create_line(offset_x + i * cell_size, offset_y, offset_x + i * cell_size, offset_y + grid_size,
width=line_width, fill=curr_line_color)
self.canvas.create_line(offset_x, offset_y + i * cell_size, offset_x + grid_size, offset_y + i * cell_size,
width=line_width, fill=curr_line_color)
# 创建/更新输入框
entry_font_size = max(12, int(cell_size / 2.2))
current_entry_font = (self.entry_font_spec[0], entry_font_size, self.entry_font_spec[2])
for r_idx in range(9):
for c_idx in range(9):
entry_widget = self.entries[r_idx][c_idx]
if entry_widget is None:
# 创建新输入框
entry_widget = tk.Entry(self.canvas, font=current_entry_font, justify='center', bd=0, relief='flat')
vcmd = (self.register(self.validate_entry), '%P')
entry_widget.config(validate='key', validatecommand=vcmd)
self.entries[r_idx][c_idx] = entry_widget
entry_widget.config(state='normal')
# 判断是否为题目初始单元格
is_locked_problem_cell = (self.solving_started and \
self.active_problem_board is not None and \
self.active_problem_board[r_idx, c_idx] != 0)
# 设置输入框背景色
current_entry_bg = color_light_cell if ((r_idx//3) + (c_idx//3)) % 2 == 0 else color_dark_cell
if (r_idx, c_idx) in self.duplicate_cells_highlight_set:
current_entry_bg = color_duplicate_bg
elif (r_idx, c_idx) in self.incorrect_cells_highlight_set and not is_locked_problem_cell:
current_entry_bg = color_error_bg
entry_widget.config(bg=current_entry_bg)
# 设置输入框值
val_to_show_str = ""
if self.active_problem_board is not None and self.active_problem_board[r_idx, c_idx] != 0:
val_to_show_str = str(self.active_problem_board[r_idx, c_idx])
current_gui_val = entry_widget.get()
# 处理题目初始单元格
if is_locked_problem_cell:
if current_gui_val != val_to_show_str:
entry_widget.delete(0, 'end')
entry_widget.insert(0, val_to_show_str)
entry_widget.config(fg=text_color_initial, state='disabled',
disabledforeground=text_color_initial,
readonlybackground=current_entry_bg)
else:
# 处理用户输入单元格
fg_color = text_color_normal
# 填充初始值（未开始做题时）
if not current_gui_val and val_to_show_str and not self.solving_started:
entry_widget.insert(0, val_to_show_str)
current_gui_val = val_to_show_str
# 设置文本颜色
if current_gui_val:
if self.active_solution_board is not None and \
current_gui_val.isdigit() and \
self.active_problem_board is not None and \
self.active_problem_board[r_idx,c_idx] == 0 and \
int(current_gui_val) == self.active_solution_board[r_idx, c_idx]:
fg_color = text_color_solved # 用户填写的正确数字
elif self.active_problem_board is not None and \
self.active_problem_board[r_idx, c_idx] != 0 and \
not self.solving_started:
fg_color = text_color_initial # 初始数字
entry_widget.config(fg=fg_color, state='normal')
# 确保高亮单元格文本可见
if (r_idx,c_idx) in self.duplicate_cells_highlight_set or \
(r_idx,c_idx) in self.incorrect_cells_highlight_set:
entry_widget.config(fg='black')
# 放置输入框
entry_x = offset_x + c_idx * cell_size + cell_size / 2
entry_y = offset_y + r_idx * cell_size + cell_size / 2
self.canvas.create_window(entry_x, entry_y, window=entry_widget,
width=cell_size * 0.8, height=cell_size * 0.8)
self._update_button_states()
def validate_entry(self, P):
# 验证输入（只允许1-9数字或空）
if P == "" or (P.isdigit() and len(P) == 1 and P != '0'):
return True
return False
def format_time(self, seconds: float) -> str:
# 格式化时间显示
secs = int(seconds)
mins = secs // 60
secs %= 60
hours = mins // 60
mins %= 60
if hours > 0:
return f"{hours:02d}:{mins:02d}:{secs:02d}"
else:
return f"{mins:02d}:{secs:02d}"
def update_timer_display(self):
# 更新计时器显示
if self.timer_active and self.user_solve_start_time is not None:
elapsed_seconds = time.time() - self.user_solve_start_time
self.time_label.config(text=f'计时: {self.format_time(elapsed_seconds)}')
self.timer_id = self.after(1000, self.update_timer_display)
def start_user_session(self):
# 开始用户解题会话
current_board = self.get_current_gui_board()
if np.all(current_board == 0):
messagebox.showwarning("面板为空", "面板为空，无法开始。请先加载或输入题目。")
return
# 设置状态
self.active_problem_board = current_board.copy()
self.active_solution_board = None
self.solving_started = True
self.timer_active = True
self.user_solve_start_time = time.time()
# 启动计时器
self.update_timer_display()
# 重绘界面（锁定初始单元格）
self.draw_grid_and_entries()
messagebox.showinfo("开始计时", "题目已锁定，计时开始！")
def clear_board_and_time(self):
# 清空面板和计时器
self._reset_user_timer_and_session_state()
self.active_problem_board = None
self.active_solution_board = None
self.incorrect_cells_highlight_set.clear()
self.duplicate_cells_highlight_set.clear()
# 清空所有输入框
for r in range(9):
for c in range(9):
if self.entries[r][c]:
self.entries[r][c].config(state='normal')
self.entries[r][c].delete(0, 'end')
self.draw_grid_and_entries()
def load_puzzle_library(self):
# 加载数独题库
filepath = filedialog.askopenfilename(
title="加载数独题库", filetypes=[('CSV 文件', '*.csv'), ('文本文件', '*.txt')]
)
if not filepath: return
# 重置状态
self._reset_user_timer_and_session_state()
self.active_problem_board = None
self.active_solution_board = None
self.incorrect_cells_highlight_set.clear()
self.duplicate_cells_highlight_set.clear()
# 清空输入框
for r_idx in range(9):
for c_idx in range(9):
if self.entries[r_idx][c_idx]:
self.entries[r_idx][c_idx].config(state='normal')
self.entries[r_idx][c_idx].delete(0, 'end')
global PUZZLES, SOLUTIONS
PUZZLES.clear()
SOLUTIONS.clear()
loaded_count = 0
try:
with open(filepath, 'r', encoding='utf-8') as f:
if filepath.endswith('.csv'):
# 处理CSV格式题库
reader = csv.DictReader(f)
if 'puzzle' not in reader.fieldnames:
messagebox.showerror('格式错误', "CSV文件必须包含 'puzzle' 列标题。")
self.draw_grid_and_entries()
return
for row_num, row_data in enumerate(reader):
puzzle_str = row_data.get('puzzle', '').strip()
solution_str = row_data.get('solution', '').strip()
# 验证题目格式
if len(puzzle_str) == 81 and all(c.isdigit() or c == '.' or c == '0' for c in puzzle_str):
# 转换题目格式
PUZZLES.append([int(ch) if ch.isdigit() and ch != '0' else 0 for ch in puzzle_str.replace('.', '0')])
# 处理解
if solution_str and len(solution_str) == 81 and all(c.isdigit() and c != '0' for c in solution_str):
SOLUTIONS.append([int(ch) for ch in solution_str])
else:
SOLUTIONS.append(None)
loaded_count +=1
else:
print(f"跳过CSV文件无效的题目字符串，行 {row_num+1}: {puzzle_str}")
else:
# 处理TXT格式题库
for line_num, line in enumerate(f):
puzzle_str = line.strip()
if len(puzzle_str) == 81 and all(c.isdigit() or c == '.' or c == '0' for c in puzzle_str):
PUZZLES.append([int(ch) if ch.isdigit() and ch != '0' else 0 for ch in puzzle_str.replace('.', '0')])
SOLUTIONS.append(None)
loaded_count += 1
else:
print(f"跳过TXT文件无效的题目字符串，行 {line_num+1}: {puzzle_str}")
# 结果反馈
if loaded_count > 0:
messagebox.showinfo('题库已加载', f'成功加载 {loaded_count} 个题目。将显示第一个题目。')
self.generate_puzzle_from_library(pick_first=True)
else:
messagebox.showwarning('题库为空', '选择的文件中未找到有效的题目。')
except Exception as e:
messagebox.showerror('加载题库错误', str(e))
self.draw_grid_and_entries()
def generate_puzzle_from_library(self, pick_first=False):
# 从题库中随机选择题目
if not PUZZLES:
messagebox.showwarning('无题目', '请先加载题库。')
return
# 重置状态
self._reset_user_timer_and_session_state()
self.active_solution_board = None
self.incorrect_cells_highlight_set.clear()
self.duplicate_cells_highlight_set.clear()
# 清空输入框
for r_idx in range(9):
for c_idx in range(9):
if self.entries[r_idx][c_idx]:
self.entries[r_idx][c_idx].config(state='normal')
self.entries[r_idx][c_idx].delete(0, 'end')
# 选择题目
chosen_index = 0 if pick_first else random.randrange(len(PUZZLES))
puzzle_flat_list = PUZZLES[chosen_index]
self.active_problem_board = np.array(puzzle_flat_list).reshape(9,9)
# 设置解（如果有）
if SOLUTIONS[chosen_index] is not None:
self.active_solution_board = np.array(SOLUTIONS[chosen_index]).reshape(9,9)
else:
self.active_solution_board = None
# 更新界面
self.draw_grid_and_entries()
def load_image_and_populate_grid(self):
# 通过OCR加载数独图片
filepath = filedialog.askopenfilename(
title="加载数独图片",
filetypes=[('图片文件', '*.png;*.jpg;*.jpeg;*.bmp;*.tiff')]
)
if not filepath: return
# 重置状态
self._reset_user_timer_and_session_state()
self.active_problem_board = None
self.active_solution_board = None
self.incorrect_cells_highlight_set.clear()
self.duplicate_cells_highlight_set.clear()
# 清空输入框
for r_idx in range(9):
for c_idx in range(9):
if self.entries[r_idx][c_idx]:
self.entries[r_idx][c_idx].config(state='normal')
self.entries[r_idx][c_idx].delete(0, 'end')
try:
# 处理图像并OCR识别
warped_grid_img = extract_sudoku_grid(filepath)
ocr_result_grid_list_of_lists = ocr_cells(warped_grid_img)
self.active_problem_board = np.array(ocr_result_grid_list_of_lists)
messagebox.showinfo("OCR 完成", "已从图片中提取数字。请检查并点击 '开始做题' 或 '求解'。")
except ValueError as ve:
messagebox.showerror('图片处理错误', str(ve))
except pytesseract.TesseractNotFoundError:
messagebox.showerror('Tesseract 错误', "未安装Tesseract或未在系统路径中找到。请安装Tesseract OCR并确保其配置正确。")
except Exception as e:
messagebox.showerror('加载图片错误', f'发生意外错误: {str(e)}')
self.draw_grid_and_entries()
def get_current_gui_board(self) -> np.ndarray:
# 获取当前GUI面板状态
board = np.zeros((9,9), dtype=int)
for r in range(9):
for c in range(9):
if self.entries[r][c]:
val_str = self.entries[r][c].get().strip()
if val_str.isdigit():
board[r,c] = int(val_str)
return board
def check_answer(self):
# 检查答案
self.incorrect_cells_highlight_set.clear()
self.duplicate_cells_highlight_set.clear()
current_gui_board = self.get_current_gui_board()
problem_board_for_check = None
true_solution_board = None
# 确定当前题目和解
if self.solving_started:
# 在解题会话中
if self.active_problem_board is None:
messagebox.showerror("错误", "解答会话已开始，但无题目定义。")
self.draw_grid_and_entries()
return
problem_board_for_check = self.active_problem_board
# 确保有解
if self.active_solution_board is None:
success_solve, solved_s = solve_sudoku_dlx(problem_board_for_check.copy())
if success_solve:
self.active_solution_board = solved_s
else:
messagebox.showerror("错误", "无法求解当前题目以进行核对。")
self.draw_grid_and_entries()
return
true_solution_board = self.active_solution_board
else:
# 不在正式解题会话中
if np.all(current_gui_board == 0):
messagebox.showinfo("面板为空", "请输入或加载一个题目以核对答案。")
self.draw_grid_and_entries()
return
problem_board_for_check = current_gui_board.copy()
# 求解当前面板
success_solve, solved_s = solve_sudoku_dlx(problem_board_for_check.copy())
if success_solve:
true_solution_board = solved_s
self.active_problem_board = problem_board_for_check.copy()
self.active_solution_board = true_solution_board.copy()
else:
messagebox.showerror("无法检查", "无法求得当前面板的解，无法进行核对。可能题目本身无解或有误。")
self.draw_grid_and_entries()
return
# 阶段1：检查规则冲突（重复数字）
self.duplicate_cells_highlight_set = self.find_duplicate_entries(current_gui_board)
if self.duplicate_cells_highlight_set:
self.draw_grid_and_entries()
messagebox.showwarning("规则错误", "存在违反数独规则的重复数字 (已用黄色背景标出)。请先修正这些错误。")
return
# 阶段2：检查答案正确性
is_fully_solved_and_correct = True
all_user_inputs_correct_so_far = True
user_made_at_least_one_entry_in_empty_cell = False
for r in range(9):
for c in range(9):
gui_val = current_gui_board[r,c]
true_val = true_solution_board[r,c]
problem_val = problem_board_for_check[r,c]
if problem_val == 0: # 用户应填写的单元格
if gui_val != 0: # 用户已填写
user_made_at_least_one_entry_in_empty_cell = True
if gui_val != true_val: # 答案错误
self.incorrect_cells_highlight_set.add((r,c))
all_user_inputs_correct_so_far = False
is_fully_solved_and_correct = False
else: # 用户未填写
is_fully_solved_and_correct = False
self.draw_grid_and_entries()
# 结果反馈
if not all_user_inputs_correct_so_far:
messagebox.showwarning("检查结果", "部分数字填写错误 (已用红色背景标出)。")
elif is_fully_solved_and_correct:
if self.timer_active:
self.timer_active = False
final_user_time = time.time() - self.user_solve_start_time
self.time_label.config(text=f'完成! 用时: {self.format_time(final_user_time)}')
messagebox.showinfo("恭喜!", "太棒了! 数独已正确完成！")
elif user_made_at_least_one_entry_in_empty_cell:
messagebox.showinfo("检查结果", "目前为止所有填写均正确，请继续！")
else:
messagebox.showinfo("提示", "请填写数字后进行核对，或使用 '求解' 功能。")
def start_solve_thread(self):
# 在后台线程中启动求解器
self.incorrect_cells_highlight_set.clear()
self.duplicate_cells_highlight_set.clear()
# 禁用按钮
for child_widget in self.button_frame.winfo_children():
if isinstance(child_widget, ttk.Button):
child_widget.config(state='disabled')
self.time_label.config(text="求解中...")
# 启动求解线程
solve_thread = threading.Thread(target=self.solve_puzzle_with_dlx, daemon=True)
solve_thread.start()
def solve_puzzle_with_dlx(self):
# 使用DLX求解数独
board_to_solve = None
problem_definition_source = ""
# 确定要解的题目
if self.solving_started and self.active_problem_board is not None:
board_to_solve = self.active_problem_board.copy()
problem_definition_source = "当前计时题目"
if self.timer_active:
self.timer_active = False # 暂停用户计时器
else:
current_gui_board = self.get_current_gui_board()
if np.all(current_gui_board == 0):
messagebox.showwarning("面板为空", "面板为空。请加载题目或输入数字。")
self.time_label.config(text='用时: N/A')
self._enable_buttons_after_threaded_task()
self.draw_grid_and_entries()
return
board_to_solve = current_gui_board.copy()
problem_definition_source = "当前面板内容"
self.active_problem_board = board_to_solve.copy()
# 求解
start_time_dlx = time.time()
success, solved_board = solve_sudoku_dlx(board_to_solve)
elapsed_time_dlx = time.time() - start_time_dlx
if success:
self.active_solution_board = solved_board
# 更新界面
for r_idx in range(9):
for c_idx in range(9):
entry_widget = self.entries[r_idx][c_idx]
if entry_widget:
entry_widget.config(state='normal')
entry_widget.delete(0, 'end')
if solved_board[r_idx,c_idx] != 0:
entry_widget.insert(0, str(solved_board[r_idx,c_idx]))
# 更新计时显示
time_msg = f'DLX求解 ({problem_definition_source}) 用时: {elapsed_time_dlx:.4f}s'
if self.user_solve_start_time is not None and not self.timer_active and self.solving_started:
user_final_elapsed = (start_time_dlx - self.user_solve_start_time)
time_msg += f" (您的计时已暂停于: {self.format_time(user_final_elapsed)})"
self.time_label.config(text=time_msg)
else:
messagebox.showwarning('无解', f'DLX算法未能找到 ({problem_definition_source}) 的解。')
if self.timer_active:
self.time_label.config(text=f'计时: {self.format_time(time.time() - self.user_solve_start_time)} (DLX无解)')
else:
self.time_label.config(text='用时: 无解 (DLX算法)')
# 重新启用按钮
self._enable_buttons_after_threaded_task()
self.draw_grid_and_entries()
def _enable_buttons_after_threaded_task(self):
# 线程任务完成后启用按钮
for child_widget in self.button_frame.winfo_children():
if isinstance(child_widget, ttk.Button):
child_widget.config(state='normal')
self._update_button_states()
def save_solution_gif(self):
# 保存解题动画GIF
initial_board_numpy_for_gif = None
# 确定题目
if self.solving_started and self.active_problem_board is not None:
initial_board_numpy_for_gif = self.active_problem_board.copy()
else:
current_gui_board_for_gif = self.get_current_gui_board()
if np.all(current_gui_board_for_gif == 0):
messagebox.showwarning("面板为空", "无法从空面板生成GIF。请先加载或输入题目。")
return
initial_board_numpy_for_gif = current_gui_board_for_gif.copy()
# 求解题目（用于最终验证）
dlx_success, final_solved_board_for_gif = solve_sudoku_dlx(initial_board_numpy_for_gif.copy())
if not dlx_success:
messagebox.showerror("求解器错误", "DLX算法无法解开GIF起始题目，无法生成GIF。")
return
# 生成解题步骤
gif_steps = []
board_for_gif_steps_generation = initial_board_numpy_for_gif.copy()
gif_steps.append(initial_board_numpy_for_gif.copy()) # 初始状态
solve_with_steps(board_for_gif_steps_generation, gif_steps) # 生成步骤
# 确保最终状态正确
if not gif_steps or not np.array_equal(gif_steps[-1], final_solved_board_for_gif):
gif_steps.append(final_solved_board_for_gif.copy())
# 限制帧数
max_gif_frames = 45
if len(gif_steps) > max_gif_frames:
indices = np.linspace(0, len(gif_steps) - 1, max_gif_frames, dtype=int)
unique_indices = sorted(list(set(indices)))
gif_steps = [gif_steps[i] for i in unique_indices]
elif not gif_steps and np.any(initial_board_numpy_for_gif !=0 ):
gif_steps.append(initial_board_numpy_for_gif.copy())
if not np.array_equal(initial_board_numpy_for_gif, final_solved_board_for_gif):
gif_steps.append(final_solved_board_for_gif.copy())
if not gif_steps:
messagebox.showwarning("GIF 生成", "未能生成解题步骤。")
return
# 创建临时目录
temp_frame_dir = 'sudoku_gif_frames'
os.makedirs(temp_frame_dir, exist_ok=True)
frame_files = []
try:
# 生成每一帧图像
for i, board_state_numpy in enumerate(gif_steps):
fig, ax = plt.subplots(figsize=(5,5), dpi=120)
ax.set_aspect('equal')
ax.axis('off')
# 绘制网格线
for k_line_minor in range(10):
ax.axvline(k_line_minor, color='grey', lw=0.5, ymin=0, ymax=1)
ax.axhline(k_line_minor, color='grey', lw=0.5, xmin=0, xmax=1)
for k_line_major in range(0, 10, 3):
ax.axvline(k_line_major, color='black', lw=1.5, ymin=0, ymax=1)
ax.axhline(k_line_major, color='black', lw=1.5, xmin=0, xmax=1)
ax.set_xlim(0, 9)
ax.set_ylim(0, 9)
# 绘制数字
for r_plot in range(9):
for c_plot in range(9):
if board_state_numpy[r_plot, c_plot] != 0:
num_val = board_state_numpy[r_plot, c_plot]
# 确定数字类型
is_original_problem_num = (initial_board_numpy_for_gif[r_plot, c_plot] != 0 and \
initial_board_numpy_for_gif[r_plot, c_plot] == num_val)
# 设置颜色
text_color = '#003399' if is_original_problem_num else '#CC0000'
if not is_original_problem_num and i > 0 and \
(len(gif_steps) > i-1 and gif_steps[i-1][r_plot, c_plot] == 0) and \
board_state_numpy[r_plot, c_plot] != 0:
text_color = '#009933' # 新填入的数字
# 添加文本
ax.text(c_plot + 0.5, 8.5 - r_plot, str(num_val),
ha='center', va='center', fontsize=16,
color=text_color, weight='bold',
fontfamily='Arial')
# 保存帧
frame_path = os.path.join(temp_frame_dir, f'frame_{i:03d}.png')
fig.savefig(frame_path, bbox_inches='tight', pad_inches=0.05)
plt.close(fig)
frame_files.append(frame_path)
if not frame_files:
messagebox.showwarning("GIF 生成", "没有帧可以生成GIF。")
return
# 保存GIF
gif_output_path = filedialog.asksaveasfilename(
defaultextension='.gif',
filetypes=[('GIF 动画', '*.gif')]
)
if gif_output_path:
duration_ms = 300 # 每帧持续时间（毫秒）
try:
# 使用imageio创建GIF
with imageio.get_writer(gif_output_path, mode='I', duration=duration_ms, loop=0) as writer:
for frame_f in frame_files:
image = imageio.v3.imread(frame_f)
writer.append_data(image)
except AttributeError:
# 回退方法
images_for_mimsave = [imageio.imread(f) for f in frame_files]
imageio.mimsave(gif_output_path, images_for_mimsave, duration=duration_ms/1000.0, loop=0)
messagebox.showinfo('GIF 已保存', f'解题动画已保存至 {gif_output_path}')
except Exception as e:
messagebox.showerror('GIF 生成错误', f'无法保存GIF: {str(e)}')
finally:
# 清理临时文件
for f_path in frame_files:
try: os.remove(f_path)
except OSError: pass
try:
if os.path.exists(temp_frame_dir) and not os.listdir(temp_frame_dir):
os.rmdir(temp_frame_dir)
except OSError: pass
if __name__ == '__main__':
app = SudokuGUI()
app.mainloop()6.1日，发现在重复造轮子
https://github.com/tropicalwzc/ice_sudoku.github.io?tab=readme-ov-file