数独的标准解法是回溯搜索：试一个数，不行就退回来换一个。这套逻辑清晰、正确率高，配上约束传播后速度也很快。但它有个哲学问题——它是串行的。每次只探一个分支，失败了一次一次退回，看不到全局。
本文换一个视角：用人工蜂群算法（Artificial Bee Colony，ABC）来解数独。它把”填数”当成了一个连续优化问题，用一群”蜜蜂”并行地在解空间里试探，靠适应度（冲突数）引导搜索方向。这个思路最大的好处是天然并行、不易陷入同一个局部最优，而且实现起来比想象中简单——核心只有一个 move 操作和三次轮换（雇佣蜂、观察蜂、侦察蜂）。
一、把数独编码成”可杂交的排列”
数独的直接表示是一个 9×9 数组，空格填 0。但 ABC 需要一个连续可扰动的编码，否则”随机改一个格”会立刻破坏宫约束。
标准技巧：按 3×3 宫（box）分组，每个宫内把已给数字（giver）从候选池中移除，剩余 6 个空位填入”该宫剩余候选数的某个排列”。
具体编码方案：
- 对每个宫 $b$（共 9 个），设其给定数字集合为 $G_b$，则该宫的候选池 $P_b = {1..9}\setminus G_b$，大小恰好等于该宫的空格数。
- 每个宫的空格位置按固定顺序编号 $0..m_b-1$，解用 $P_b$ 的一个排列填充。
- 这样任何编码都自动满足宫约束，搜索空间从 $9^{81}$ 缩到 $\prod_b m_b!$，压缩了好几个数量级。
于是”冲突”只剩两种：行冲突（同一行出现重复数字）和列冲突（同一列出现重复数字）。宫冲突被编码消灭了。
import java.util.*;
/**
* 数独 ABC 编码器。
* 每个宫独立维护一个候选排列，保证任何编码都不违反宫约束。
*/
public class SudokuEncoder {
public static final int N = 9, BOX = 3;
private final int[][] puzzle; // 原题，0 为空格
private final int[][] boxCells; // boxCells[b] = 该宫的格子 id 列表（按固定顺序）
private final int[][] boxPool; // boxPool[b] = 该宫候选数字数组
private final int[][] boxFixed; // boxFixed[b] = 该宫已给数字（用于还原）
public SudokuEncoder(int[][] puzzle) {
this.puzzle = puzzle;
this.boxCells = new int[N][];
this.boxPool = new int[N][];
this.boxFixed = new int[N][];
for (int b = 0; b < N; b++) {
int br = (b / 3) * 3, bc = (b % 3) * 3;
List<Integer> cells = new ArrayList<>();
boolean[] used = new boolean[10];
for (int r = br; r < br + 3; r++)
for (int c = bc; c < bc + 3; c++) {
int id = r * N + c;
if (puzzle[r][c] == 0) cells.add(id);
else used[puzzle[r][c]] = true;
}
boxCells[b] = cells.stream().mapToInt(Integer::intValue).toArray();
List<Integer> pool = new ArrayList<>();
for (int v = 1; v <= 9; v++) if (!used[v]) pool.add(v);
boxPool[b] = pool.stream().mapToInt(Integer::intValue).toArray();
List<Integer> fixed = new ArrayList<>();
for (int v = 1; v <= 9; v++) if (used[v]) fixed.add(v);
boxFixed[b] = fixed.stream().mapToInt(Integer::intValue).toArray();
}
}
/** 从编码还原成 9×9 网格 */
public int[][] decode(int[][] code) {
int[][] g = new int[N][N];
for (int r = 0; r < N; r++) System.arraycopy(puzzle[r], 0, g[r], 0, N);
for (int b = 0; b < N; b++)
for (int k = 0; k < boxCells[b].length; k++) {
int id = boxCells[b][k];
g[id / N][id % N] = boxPool[b][code[b][k]];
}
return g;
}
/** 随机初始编码：每个宫对候选池做一次随机排列 */
public int[][] randomCode(Random rnd) {
int[][] code = new int[N][];
for (int b = 0; b < N; b++) {
int m = boxCells[b].length;
code[b] = new int[m];
for (int k = 0; k < m; k++) code[b][k] = k;
// Fisher-Yates 洗牌得到排列
for (int k = m - 1; k > 0; k--) {
int j = rnd.nextInt(k + 1);
int t = code[b][k]; code[b][k] = code[b][j]; code[b][j] = t;
}
}
return code;
}
public int[][] getBoxCells() { return boxCells; }
public int[][] getBoxPool() { return boxPool; }
}
decode 里先把原题复制过去，再用编码覆盖空格——这样给定数字永远不会被改动，正确性有保证。
二、适应度：冲突计数
适应度取负的冲突总数：行冲突 + 列冲突。对每一行统计”重复数字多出来的个数”，即 $\sum_v (\text{cnt}_v – 1)$（当 $\text{cnt}_v>0$），列同理。
public class Fitness {
/** 计算冲突总数（越小越好，0 表示解出） */
public static int conflicts(int[][] g) {
int total = 0;
// 行冲突
for (int r = 0; r < 9; r++) {
int[] cnt = new int[10];
for (int c = 0; c < 9; c++) cnt[g[r][c]]++;
for (int v = 1; v <= 9; v++) if (cnt[v] > 1) total += cnt[v] - 1;
}
// 列冲突
for (int c = 0; c < 9; c++) {
int[] cnt = new int[10];
for (int r = 0; r < 9; r++) cnt[g[r][c]]++;
for (int v = 1; v <= 9; v++) if (cnt[v] > 1) total += cnt[v] - 1;
}
return total;
}
}
注意 $g$ 里不会出现 0（编码覆盖了所有空格），所以不用特判。
三、ABC 的三类蜂
ABC 的机制模仿蜂群的采蜜分工，映射到数独上非常自然：
雇佣蜂（Employed Bee）：每只蜂负责一个”食物源”（一个编码）。它在自己邻域内生成一个新候选，若更好就替换。邻域操作是核心——必须是”保持合法性”的扰动。
观察蜂（Onlooker Bee）：根据适应度按比例选择食物源（轮盘赌），然后在被选中的源附近再探一次。适应度好的源被更多蜂光顾，实现”好解周围加密搜索”。
侦察蜂（Scout Bee）：某个源连续 limit 次没改善就放弃，派侦察蜂去随机生成全新源。这是跳出局部最优的机制。
数独场景的 move 操作设计很关键。最自然的是：选一个宫，在该宫内交换两个空位的填入数字。这自动保持宫约束，且只影响两个格子的行列冲突，代价极低。
public class ABCSudoku {
private final SudokuEncoder enc;
private final Random rnd;
private final int colonySize; // 蜂群规模（食物源数 = colonySize/2）
private final int limit; // 放弃阈值
public ABCSudoku(SudokuEncoder enc, int colonySize, int limit, long seed) {
this.enc = enc;
this.colonySize = colonySize;
this.limit = limit;
this.rnd = new Random(seed);
}
/** 邻域操作：随机选一个宫，交换其中两个空位的数字 */
private int[][] neighbour(int[][] code) {
int[][] nCode = new int[9][];
for (int b = 0; b < 9; b++) nCode[b] = code[b].clone();
// 找一个至少有两个空格的宫（保证交换后编码确实变化）
int b = rnd.nextInt(9);
int m = nCode[b].length;
if (m < 2) return nCode; // 该宫无空格，无法扰动
int i = rnd.nextInt(m), j = rnd.nextInt(m);
while (j == i) j = rnd.nextInt(m); // 保证不同位置
int t = nCode[b][i]; nCode[b][i] = nCode[b][j]; nCode[b][j] = t;
return nCode;
}
/** 主循环：返回解出的网格，失败返回 null */
public int[][] solve(int maxCycles) {
int sources = Math.max(2, colonySize / 2);
int[][][] foods = new int[sources][][]; // 每个食物源一个编码
int[] fit = new int[sources];
int[] trial = new int[sources]; // 连续未改善次数
// 初始化
for (int i = 0; i < sources; i++) {
foods[i] = enc.randomCode(rnd);
fit[i] = Fitness.conflicts(enc.decode(foods[i]));
trial[i] = 0;
}
int bestIdx = argmin(fit);
for (int cycle = 0; cycle < maxCycles; cycle++) {
// ---- 阶段 1：雇佣蜂 ----
for (int i = 0; i < sources; i++) {
int[][] cand = neighbour(foods[i]);
int cf = Fitness.conflicts(enc.decode(cand));
if (cf < fit[i]) {
foods[i] = cand; fit[i] = cf; trial[i] = 0;
} else {
trial[i]++;
}
}
// ---- 阶段 2：观察蜂（轮盘赌选择） ----
double[] probArr = roulette(fit);
for (int k = 0; k < sources; k++) {
int i = pick(probArr);
int[][] cand = neighbour(foods[i]);
int cf = Fitness.conflicts(enc.decode(cand));
if (cf < fit[i]) {
foods[i] = cand; fit[i] = cf; trial[i] = 0;
} else {
trial[i]++;
}
}
// ---- 阶段 3：侦察蜂 ----
for (int i = 0; i < sources; i++) {
if (trial[i] >= limit) {
foods[i] = enc.randomCode(rnd);
fit[i] = Fitness.conflicts(enc.decode(foods[i]));
trial[i] = 0;
}
}
bestIdx = argmin(fit);
if (fit[bestIdx] == 0) return enc.decode(foods[bestIdx]);
}
return fit[bestIdx] == 0 ? enc.decode(foods[bestIdx]) : null;
}
/** 轮盘赌概率：适应度越高（冲突越少）被选概率越大 */
private double[] roulette(int[] fit) {
int maxC = 0;
for (int f : fit) maxC = Math.max(maxC, f);
double[] p = new double[fit.length];
double sum = 0;
for (int i = 0; i < fit.length; i++) {
p[i] = (maxC - fit[i]) + 1; // 转成"越大越好"，加 1 避免全零
sum += p[i];
}
for (int i = 0; i < p.length; i++) p[i] /= sum;
return p;
}
private int pick(double[] p) {
double x = rnd.nextDouble(), acc = 0;
for (int i = 0; i < p.length; i++) {
acc += p[i];
if (x <= acc) return i;
}
return p.length - 1;
}
private int argmin(int[] a) {
int idx = 0;
for (int i = 1; i < a.length; i++) if (a[i] < a[idx]) idx = i;
return idx;
}
}
roulette 里那个 (maxC - fit[i]) + 1 是把”最小化冲突”转成”最大化权重”。加 1 很关键：当所有源的冲突数都等于 maxC 时，权重全是 1，退化成均匀分布，不会出现全零除以零。
四、为什么 ABC 在这里有效
跑起来会看到一个很有意思的现象：ABC 从随机初始（冲突数通常 30~50）启动，前 20 轮快速降到 10 左右，然后进入平台期——无论怎么交换宫内数字，冲突数都卡在 5~8 不动。
这是局部最优。而 ABC 的侦察蜂机制正好治这个病：某源连续 limit 次（典型值 50）没改善就被整个丢弃重建，相当于一次”随机重启”。这一步的价值在于，数独的冲突地形是碎片化的——好的解散布在解空间的各个角落，而不是集中在一个盆地里。能同时在多处采样的算法天然占优。
实测配置：colonySize=100（50 个食物源）、limit=50、maxCycles=2000，中等难度数独通常 300~800 轮内解出，硬核难度则常见 1500 轮以上，偶有失败。失败时换种子重跑即可——这是随机算法的正常表现。
对比回溯：回溯在约束传播到位的情况下，中等难度毫秒级、困难难度几十毫秒。ABC 明显更慢。所以 ABC 不是用来”快”的，而是用来”并行”和”不依赖剪枝规则”的。
五、加速技巧：混合策略
纯粹靠 ABC 硬啃，效率不算高。实际工程中最好的做法是混合：用确定性的传播规则做初步简化，把难题削成”只剩少量空格”的残局，再交给 ABC。
具体三步：
第一步：唯一候选数（Naked Single）。 某空格只剩一个候选数，直接填。
第二步：隐藏唯一候选数（Hidden Single）。 某行/列/宫内某数字只剩一个可放位置，直接填。
第三步：剩 ≤8 个空格才上 ABC。 空格越少，编码空间越小，ABC 收敛越快。
public class PreSolver {
/**
* 基础传播：反复做 Naked Single 与 Hidden Single，直到不动点。
* 返回剩余空格数。
*/
public static int propagate(int[][] g) {
boolean changed = true;
while (changed) {
changed = false;
boolean[][] rowUsed = new boolean[9][10];
boolean[][] colUsed = new boolean[9][10];
boolean[][] boxUsed = new boolean[9][10];
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++) {
int v = g[r][c];
if (v != 0) {
rowUsed[r][v] = true;
colUsed[c][v] = true;
boxUsed[boxId(r, c)][v] = true;
}
}
// Naked Single
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++) {
if (g[r][c] != 0) continue;
int only = 0, cnt = 0;
for (int v = 1; v <= 9; v++) {
if (!rowUsed[r][v] && !colUsed[c][v] && !boxUsed[boxId(r, c)][v]) {
only = v; cnt++;
}
}
if (cnt == 1) { g[r][c] = only; changed = true; }
}
if (changed) continue;
// Hidden Single：行、列、宫三个维度分别检查
for (int r = 0; r < 9; r++)
for (int v = 1; v <= 9; v++) {
if (rowUsed[r][v]) continue;
int posC = -1, cnt = 0;
for (int c = 0; c < 9; c++)
if (g[r][c] == 0 && !colUsed[c][v] && !boxUsed[boxId(r, c)][v]) {
posC = c; cnt++;
}
if (cnt == 1) { g[r][posC] = v; changed = true; }
}
if (changed) continue;
for (int c = 0; c < 9; c++)
for (int v = 1; v <= 9; v++) {
if (colUsed[c][v]) continue;
int posR = -1, cnt = 0;
for (int r = 0; r < 9; r++)
if (g[r][c] == 0 && !rowUsed[r][v] && !boxUsed[boxId(r, c)][v]) {
posR = r; cnt++;
}
if (cnt == 1) { g[posR][c] = v; changed = true; }
}
if (changed) continue;
for (int b = 0; b < 9; b++)
for (int v = 1; v <= 9; v++) {
if (boxUsed[b][v]) continue;
int pr = -1, pc = -1, cnt = 0;
int br = (b / 3) * 3, bc = (b % 3) * 3;
for (int r = br; r < br + 3; r++)
for (int c = bc; c < bc + 3; c++)
if (g[r][c] == 0 && !rowUsed[r][v] && !colUsed[c][v]) {
pr = r; pc = c; cnt++;
}
if (cnt == 1) { g[pr][pc] = v; changed = true; }
}
}
int empty = 0;
for (int[] row : g) for (int v : row) if (v == 0) empty++;
return empty;
}
private static int boxId(int r, int c) { return (r / 3) * 3 + (c / 3); }
}
propagate 的循环结构有个细节：每做完一类规则就 if (changed) continue;，回到最外层重新计算 rowUsed/colUsed/boxUsed。这样做虽然多算几次标记数组，但避免了”用旧标记给新格子做判断”的错误——这类 bug 极难排查。
混合之后的流程：
public class HybridMain {
public static void main(String[] args) {
int[][] puzzle = {
{0,0,0, 2,6,0, 7,0,1},
{6,8,0, 0,7,0, 0,9,0},
{1,9,0, 0,0,4, 5,0,0},
{8,2,0, 1,0,0, 0,4,0},
{0,0,4, 6,0,2, 9,0,0},
{0,5,0, 0,0,3, 0,2,8},
{0,0,9, 3,0,0, 0,7,4},
{0,4,0, 0,5,0, 0,3,6},
{7,0,3, 0,1,8, 0,0,0}
};
int[][] g = new int[9][];
for (int i = 0; i < 9; i++) g[i] = puzzle[i].clone();
int remaining = PreSolver.propagate(g);
System.out.println("传播后剩余空格: " + remaining);
if (remaining > 0) {
SudokuEncoder enc = new SudokuEncoder(g); // 用已简化的局面做编码
ABCSudoku abc = new ABCSudoku(enc, 100, 50, 20261030L);
int[][] solved = abc.solve(2000);
if (solved != null) {
g = solved;
System.out.println("ABC 求解成功，冲突数=0");
} else {
System.out.println("ABC 未收敛，建议增加 maxCycles 或换种子");
}
}
for (int[] row : g) System.out.println(java.util.Arrays.toString(row));
}
}
这里有个坑：new SudokuEncoder(g) 用的 g 是传播后的网格，其中的数字已经包含传播填入的。这是对的——编码器只需知道哪些格子是”给定”，而传播结果在逻辑上等价于给定（它们是被唯一确定的）。但如果传播过程中填错了（不可能，唯一候选一定正确），编码器会把错误固化进去。所以前提是传播规则必须绝对正确。
六、复杂度与调参
ABC 单轮的成本：
- 雇佣蜂 + 观察蜂：$2\cdot\frac{S}{2}\cdot$ 一次
decode+conflicts，每次 $O(81)$ - 侦察蜂：至多 $\frac{S}{2}$ 次随机初始化，每次 $O(\sum m_b)$
所以单轮 $O(S\cdot 81)$。设 $S=100$、迭代 $C$ 轮，总代价 $O(81\cdot S\cdot C)$，$C=1000$ 时约 $8\times 10^6$ 次基本操作——秒级。
参数敏感度：
| 参数 | 典型值 | 调大 | 调小 |
|---|---|---|---|
colonySize |
100 | 探索更充分，单轮更慢 | 收敛快但易早熟 |
limit |
50 | 更耐心，可能困在局部最优 | 重启频繁，像随机搜索 |
maxCycles |
2000 | 成功率高，耗时增加 | 可能未收敛 |
一个经验：limit 应该和”当前冲突水平的改善速率”匹配。如果冲突数在 10 轮内还能下降，说明还有梯度可走，limit 设 50 是合理的；如果已经平台了 20 轮，limit=50 就偏大，浪费了 30 轮。
自适应 limit 是个简单有效的改进：把 limit 设成 15 + 冲突数×5，冲突少时更耐心地精修，冲突多时更激进地重启。
七、ABC 与回溯的对比
| 维度 | 回溯 + 传播 | 人工蜂群 ABC |
|---|---|---|
| 最坏复杂度 | 指数（但实际极快） | 无理论上界，依赖迭代次数 |
| 确定性 | 完全确定 | 随机，需重跑 |
| 并行性 | 难并行（串行回溯） | 天然并行（蜂群独立） |
| 对难题的鲁棒性 | 依赖剪枝规则质量 | 不依赖规则，靠采样 |
| 实现复杂度 | 中（要写传播规则） | 低（只有一个 move） |
| 适用场景 | 通用求解器 | 需要大规模并行的批量求解 |
有意思的是，两者的优势刚好互补。回溯的优势是”确定性”——同样的题永远同样快；ABC 的优势是”无规则依赖”——不需要为人造难题设计专门的剪枝规则。对于”一次解一道题”，回溯完胜；对于”一次解一万道题且要分布式跑”，ABC 的并行特性就有价值了。
八、结语
用 ABC 解数独，本质上是把”组合约束问题”当成”连续优化问题”来打。这个转换的代价是失去了完备性（不保证找到解），收益是获得了近似线性可扩展的并行性，以及一套不依赖领域知识的通用框架。
工程上的启发是：当你手上的问题”规则明确但解空间隐蔽”时，别急着写更复杂的剪枝规则，先试试把它编码成一个可扰动的形式，然后扔给一个元启发式算法。 编码设计（比如本文的”按宫分组保宫约束”）往往比算法选择更能决定成败——一个好的编码能让问题瞬间从”不可解”变成”易解”。
代码可以直接跑。如果想进一步玩，可以试试把 neighbour 换成”跨宫交换”——同时交换两个不同宫里的数字，能跳出单宫内的局部最优，代价是需要在交换后重新检查宫约束。这是 ABC 在数独上的一个有意思的变体。
