Sudoku Solver + Image Recognition

数独求解与图像识别系统，支持通过 API 上传数独图片自动识别并求解。

功能

• Web GUI：浏览器访问即可使用，上传图片 → 编辑识别结果 → 一键求解
• 图像识别：上传数独图片，自动提取网格并识别数字（基于 PyTorch CNN）
• 数独求解：高性能 C++ 求解器（位运算回溯 / DLX / SIMD 加速）
• REST API：基于 FastAPI 提供 HTTP 接口

详细文档

每个子模块有独立的 README 深入介绍：

目录结构

sudoku-py/
├── main.py              # FastAPI 入口
├── CMakeLists.txt       # C++ 构建系统
├── build_pgo.sh         # PGO 一键构建脚本
├── pyproject.toml       # Python 项目配置与依赖（PEP 621）
├── Dockerfile           # 容器化部署
├── sudoku/              # Python 图像识别模块
│   ├── README.md        #   详细文档：识别流水线说明
│   ├── pipeline.py      #   图像识别主流程
│   ├── classifier.py    #   CNN 模型定义
│   ├── correction.py    #   透视变换校正
│   ├── extraction.py         #   数字提取（连通域分析）
│   ├── binary_classifier.py  #   二分类 CNN（空格/数字判别）
│   └── __init__.py
├── training/            # CNN 模型训练
│   ├── README.md        #   详细文档：训练流程说明
│   ├── train.py         #   训练脚本
│   ├── samples.npy      #   自定义训练数据
│   └── label.npy        #   训练标签
├── models/              # 训练好的模型权重
│   ├── sudoku_cnn.pth
│   └── cell_binary.pth
├── src/                 # C++ 求解器源码
│   ├── README.md                 #   详细文档：求解器算法与编译
│   ├── solver_bitmask.hpp        #   位运算回溯求解器头文件
│   ├── solver_bitmask.cpp        #   位运算回溯求解器实现（主力）
│   ├── solver_dpll_triad_simd.cc #   Tdoku SIMD 求解器
│   ├── solver_dpll_triad_scc.cc  #   Tdoku SCC 求解器
│   ├── solver_basic.cc           #   Tdoku 基础求解器
│   ├── solver_backtrack.cpp      #   实验性回溯求解器
│   ├── solver_dlx.cpp            #   实验性 Dancing Links 求解器
│   ├── solver_dfs.cpp            #   实验性 DFS 求解器
│   ├── tables.hpp                #   位掩码查找表
│   └── ...                       #   其他辅助文件
├── lib/                 # 编译产物（.so）
├── tests/               # 测试与基准
│   ├── README.md                 #   详细文档：测试体系说明
│   ├── test_solver.py            #   统一求解器性能测试（bitmask + tdoku）
│   ├── test_solver_tdoku.py      #   Tdoku 兼容入口
│   ├── verify.cpp                #   求解精度验证
│   ├── bench_single.cpp          #   纯 C 性能基准
│   ├── bench_multi.cpp           #   多轮基准（perf 采样）
│   ├── test_e2e.py               #   curl 端到端测试（功能+压测）
│   ├── tools/                    #   PGO 训练程序
│   ├── images/                   #   测试用数独图片
│   ├── ir_bench/                 #   图像识别基准测试（对比/诊断/参数扫描）
│   └── ground_truth/             #   用户标注的基准真相（启用反馈模式后生成，不纳入版本控制）
├── data/                # 测试题库（9 个数据集, 3.8M+ 谜题）+ MNIST（自动下载）
├── templates/            # Web GUI 页面模板
│   └── index.html
├── static/               # 前端静态资源
│   ├── style.css
│   └── app.js

运行时性能

Web 服务层面的优化：

• ORJSON：使用 orjson 替代 stdlib json，序列化快 2-5x
• LRU 缓存：最近 128 次求解结果自动缓存，重复提交零开销
• uvloop + httptools：高性能事件循环和 HTTP 解析器
• 输入校验：Pydantic v2 校验 81 元素长度和 0-9 值域，非法输入在到达 C++ 求解器前被拦截
• 日志：结构化 logging 替代 print，记录每次请求耗时

图像识别流水线优化：

• 圆形遮罩预计算为模块级常量，消除 81×1600 次 Python 循环
• NumPy 高级索引替代显式 for 循环
• torch.inference_mode() 替代 torch.no_grad()

C++ 求解器：

• 统一 C ABI 接口：SudokuBitmaskSolver(const char *puzzle, size_t limit, uint32_t flags, char *solution, size_t *num_guesses) — 81 字符输入（1-9/.），返回找到的解的数量，Web 服务默认使用此接口
• 切换求解器：在 main.py 中修改两行即可切换：将 lib/solver_bitmask.so 改为 lib/solver_tdoku.so，SudokuBitmaskSolver 改为 TdokuSolverDpllTriadSimd（Tdoku 需 AVX512 指令集）
• 循环展开 (-funroll-loops) 提升紧凑循环性能
• 深度溢出不再调用 exit(0)，改为返回错误码

环境要求

Linux

sudo apt-get install -y build-essential cmake

# RHEL 7 / CentOS 7
sudo yum install -y gcc-c++ make cmake

# RHEL 8+ / Fedora
sudo dnf install -y gcc-c++ make cmake

# CPU 版 torch（避免拉下数 GB 的 NVIDIA 包）
pip install torch torchvision --index-url https://download.pytorch.org/whl/cpu
# Python 依赖
pip install -e .
# 解压谜题数据集
unzip data.zip
# PGO 编译 C++ 求解器（推荐，性能提升约 17%）
bash build_pgo.sh

macOS

# 系统依赖（Xcode CLI 自带 g++，cmake 通过 Homebrew 安装）
brew install cmake
# CPU 版 torch
pip install torch torchvision --index-url https://download.pytorch.org/whl/cpu
# Python 依赖
pip install -e .
# 解压谜题数据集
unzip data.zip
# PGO 编译 C++ 求解器（推荐，性能提升约 17%）
bash build_pgo.sh

Windows

# 系统依赖：安装 Visual Studio Build Tools（含 C++ 工具链）和 CMake
# CPU 版 torch
pip install torch torchvision --index-url https://download.pytorch.org/whl/cpu
# Python 依赖
pip install -e .
# 解压谜题数据集
unzip data.zip
# 常规编译（PGO 需 g++，Windows 不适用）
mkdir build && cd build && cmake .. && cmake --build .

Windows 注意：uvloop 仅支持 Linux/macOS。启动前需将 main.py 中的 loop="uvloop" 改为 loop="asyncio"，或安装时跳过高性能组件：pip install uvicorn（不带 [standard] extra），需手动补装 httptools（Windows 兼容的 C 扩展）。

安装

# 1. 先装 CPU 版 torch（避免 PyPI 拉下数 GB 的 NVIDIA 包）
pip install torch torchvision --index-url https://download.pytorch.org/whl/cpu

# 2. 安装其余 Python 依赖（torch 已就位，跳过）
pip install -e .

# 开发/测试额外依赖：
#   pip install -e ".[dev]"

# 3. 解压谜题数据集（PGO 训练和测试需要）
unzip data.zip

# 4. 编译 C++ 求解器（PGO 推荐，性能提升约 17%）
bash build_pgo.sh

# 5. 启动服务
cd .. && python3 main.py
# 浏览器打开 http://localhost:8000，上传数独图片即可使用

CNN 模型（models/sudoku_cnn.pth、models/cell_binary.pth）已纳入版本控制，安装后可直接使用图像识别。

如需用自己的数据重新训练或微调，见下方 训练 CNN 模型。

清理构建产物（仅清理 lib/*.so、build/、__pycache__/，不影响模型文件）：

cmake --build build --target clean_artifacts

编译 C++ 求解器

推荐使用 PGO (Profile-Guided Optimization) 构建，可额外获得约 17% 的性能提升：

# 一键 PGO 构建（默认生成 lib/solver_bitmask.so）
bash build_pgo.sh

# 自定义训练数据集（多文件）
PUZZLE_FILES="data/puzzles2_17_clue data/puzzles6_forum_hardest_1106" bash build_pgo.sh

PGO 构建流程：

1. 插桩编译 (-fprofile-generate)：生成带计数器插桩的 .so
2. 训练运行：逐题求解训练集谜题，收集 profile 数据（默认用 49,162 个 17-clue 谜题）
3. 优化编译 (-fprofile-use)：基于 profile 数据重新编译，优化分支预测、内联决策和代码布局

环境要求：g++（需支持 -fprofile-generate/-fprofile-use）。

常规编译（无 g++ 或快速构建时使用）：

mkdir build && cd build && cmake .. && cmake --build .

编译产物输出到 lib/ 目录：

• lib/solver_bitmask.so — 位运算回溯求解器（SudokuBitmaskSolver 接口，81 字符输入）
• lib/solver_tdoku.so — Tdoku SIMD 求解器（需 AVX512VL/BITALG）

训练 CNN 模型

cd training
python3 train.py           # 数字分类 CNN（识别 1-9）
python3 train_binary.py    # 二分类 CNN（判别空格 / 有数字）

数字分类训练流程：

1. MNIST 数据集预训练（数字 1-9，5 个 epoch）
2. 自定义数据微调（30 个 epoch）
3. GT 数据微调（15 个 epoch，从 ground truth 图片提取）
4. 最优模型保存至 models/sudoku_cnn.pth

二分类训练保存至 models/cell_binary.pth。

启动 API 服务

python3 main.py --help                  # 查看所有选项
python3 main.py                         # 默认：8 workers, warning 日志
python3 main.py --workers 1             # 单 worker
python3 main.py --port 9000             # 指定端口
python3 main.py --log-level info        # INFO 级别日志（每请求可见）

API 接口

POST / — 求解数独

请求体：

{"asks": [8,0,0,0,0,0,0,0,0, 0,0,3,6,0,0,0,0,0, ...]}

81 个整数的一维数组，0 表示空格。校验：必须恰好 81 个元素，每格 0-9，否则返回 422。

POST /uploadfile/ — 图片识别

上传数独图片（multipart form-data），返回识别出的 9×9 矩阵。

GET / — Web GUI

启动服务后浏览器打开 http://localhost:8000，提供完整的可视化操作界面：

┌─────────────────────────────────────────────────────┐
│  [上传区域]  点击或拖拽数独图片                        │
│  ┌──────────────────────────────────────────────┐   │
│  │              📋 图片预览                       │   │
│  └──────────────────────────────────────────────┘   │
│  [上传并识别]  [求解]  [清空]                         │
│                                                     │
│  ┌─────── 题目（可编辑） ──────┐  ┌─── 解答 ───────┐ │
│  │  8  ·  · │ ·  ·  · │ ·  ·  · │  │ 8  1  2 │ 7 … │ │
│  │  ·  ·  3 │ 6  ·  · │ ·  ·  · │  │ 9  4  3 │ 6 … │ │
│  │  ·  7  · │ ·  9  · │ 2  ·  · │  │ 5  7  6 │ 1 … │ │
│  │  ────────┼─────────┼──────── │  │ ────────┼───── │ │
│  │  ·  5  · │ ·  ·  7 │ ·  ·  · │  │ 1  5  4 │ 3 … │ │
│  │  …       │         │         │  │  …      │      │ │
│  └──────────────────────────────┘  └────────────────┘ │
└─────────────────────────────────────────────────────┘

交互流程：

1. 上传图片：点击、拖拽数独照片到上传区域，或 Ctrl+V 粘贴剪贴板中的图片
2. 识别：点击「上传并识别」，CNN 自动提取数字填入左侧网格（蓝色）
3. 编辑修正：点击格子直接修改识别错误的数字（绿色），方向键导航
4. 求解：点击「求解」，C++ 求解器计算结果，右侧展示解答（紫色=求解器填入）

启用反馈模式 (--enable-feedback) 后，额外提供：

1. 更正识别结果：手动修正后的题目可保存为基准真相（Ground Truth），附带原图
2. 自动对比：再次上传同一张图时，自动加载已保存的更正结果，标出与 AI 识别的差异（橙色虚线=不同，绿色=一致）
3. 切换视图：双击「题目」标题可在更正结果和 AI 识别结果之间切换

测试

求解器性能

cd tests && python3 test_solver.py                   # bitmask（默认）
cd tests && python3 test_solver.py --solver tdoku     # tdoku
cd tests && python3 test_solver.py --list             # 列出可用数据集

求解精度验证

验证 49,162 个 17-clue 谜题的行/列/宫完整性及线索保留：

cd build && cmake --build . --target verify -j$(nproc) && ./verify
# 预期: Verified 49162 puzzles: 49162 passed, 0 failed

C++ 性能基准

绕过 Python ctypes 开销，测量纯 C++ 求解时间：

cd build && g++ -O2 -std=c++17 -o ../tests/bench_single ../tests/bench_single.cpp -ldl
cd tests && ./bench_single

E2E 测试

通过 HTTP 请求测试 main.py 的可用性和性能（自动启动/关闭服务）：

python3 tests/test_e2e.py                                         # 功能测试
python3 tests/test_e2e.py --mode stress --requests 100            # 压测
python3 tests/test_e2e.py --mode stress-curl --requests 100       # 仅 curl 压测
python3 tests/test_e2e.py --mode stress-curl --requests 200 --concurrency 30
python3 tests/test_e2e.py --mode stress-ir --requests 100         # 仅图像识别压测

图像识别

python3 -m sudoku.pipeline --image path/to/image.jpg

更多测试细节（PGO 训练、perf 采样、添加新测试等）见 tests/README.md。

Docker 部署

docker build -t sudoku-api .
docker run -p 80:80 sudoku-api

产物说明

项目中各目录下的文件按性质分为源码（git 追踪）和产物（通过脚本/构建生成，gitignore 排除）。以下是全部产物的来源与清理方式。