奶牛摆放谜题 — 算法原理

本求解器（Solver）完全由程序自动完成，不需要借助任何深度学习或 OCR 大模型。整个处理流程可分为三个阶段：图像识别与网格提取、颜色聚类解析，以及最后的约束满足求解。

1. 图像识别与网格提取 (Image Parsing)

目标：从玩家上传的任意手机截图中，精准定位出游戏棋盘，并提取出每一个格子的像素信息。

寻找边界 (Bounding Box)：
算法通过设定一个“背景色阈值”（通常是游戏背景的浅蓝色），按行、按列扫描像素的“非背景密度”。
当某一行/列的非背景像素超过一定比例时，即认为触碰到了棋盘边界。
为了防止底部无关 UI（如广告、工具栏）的干扰，算法在确定上边界和左右宽度后，会限制下边界的搜索范围（假定棋盘是正方形的）。
自动尺寸识别 (Grid Size Detection)：
若用户没有显式指定棋盘边长，算法会在棋盘包围盒内直接数“连续色块条带”。
官方截图中的白色分隔缝、内置示例图中的深色网格线都会被识别为分隔区域。
当前使用侧支持 6 / 8 / 10 三种尺寸；无法稳定识别时返回明确错误，而不是按默认 8x8 误解。
提取格子 (Cell Sampling)：
找到棋盘包围盒 (x0, y0, x1, y1) 后，利用边长 $N$，将整个棋盘均分为 $N \times N$ 个小方格。
算法直接提取每个格子正中心的 RGB 像素值作为该格的颜色代表，从而避开边缘边框的干扰。

2. 颜色聚类 (Color Clustering)

目标：将提取出的 $N \times N$ 个 RGB 颜色像素，归类为 $N$ 种不同的整数 ID，形成供算法理解的二维矩阵。

算法使用 K-Means 聚类（n_clusters=N），对这 $N^2$ 个像素点进行分类。
聚类完成后，为了保证每次解析出的颜色 ID 稳定且符合人类直觉，算法会按从左到右、从上到下的顺序，将首次出现的颜色依次映射为 0, 1, 2... N-1。
最终，我们将得到一个 $N \times N$ 的整数矩阵，其中相同的数字代表属于同一个颜色区域。

3. 约束满足求解 (Constraint Satisfaction Problem, CSP)

目标：在一个 $N \times N$ 的整数矩阵上，放置 $N$ 头牛，满足游戏的所有规则。

算法将该问题抽象为标准的 CSP（约束满足问题），采用带剪枝的回溯搜索（Backtracking with Forward Checking）。

约束条件定义

算法维护了三个全局状态来加速判断： 1. row_used: 记录每一行是否已经放了牛。 2. col_used: 记录每一列是否已经放了牛。 3. grid: 记录棋盘上的占用情况。放牛后，不仅该格被标记，其周围的 8 个格子（上下左右及对角线）也会被标记为“禁止放置”（Forbidden）。

搜索策略：MRV (Minimum Remaining Values)

为了避免盲目搜索带来的指数级耗时，算法采用了 MRV 启发式策略： - 每一步，算法都会统计剩下还没放牛的颜色中，哪种颜色当前可放的格子最少。 - 优先去放置那个“选择最少”的颜色（如果某个颜色只剩 1 个格子能放，那就立刻放它；如果某个颜色没有格子能放了，说明走进了死胡同，立刻触发回溯）。 - 这种策略极大程度模拟了人类高手的推理过程，使得绝大多数关卡在几毫秒内即可求解。

总结

整个流程 截图 -> 定位 -> 识别尺寸 -> 采样 -> 聚类 -> CSP回溯求解 -> 生成标注图 高效轻量，通常在一瞬间即可完成从识别到答案的输出。

4. 求解结果分类

Web/API 侧会把求解结果分为三类，避免把“有解但非唯一”误报为失败：

无解：没有任何合法摆放，返回错误，提示检查截图清晰度或棋盘尺寸。
多解：至少找到 2 个合法解；接口返回其中一个标注解，并附带多解提示。
唯一解：只找到 1 个合法解，正常返回。

多解判断使用 find_solutions(limit=2)：找到第二个解后立即停止，所以返回“多解”表示至少有 2 个解，不做全量枚举。