格格不入（Blokus）看似只是拼图，本质却是组合优化的硬骨头：每块拼板只能角对角相连，玩家要在一块 20×20 的棋盘上把 21 块异形板全部塞进去。本文用 Java 实现一个真正的解算器：用 64 位掩码做位棋盘压缩、用精确覆盖的思路枚举放置序列、用最大独立集的思想选择最有价值的空地，最后给出搜索规模估算与剪枝效果对比。
一、为什么这是个算法题而不是界面题
规则只有三条：同一玩家的拼板之间只能角接触、第一块必须覆盖起始格、每块拼板最多翻转一次。但三条规则的组合效果极强：一次放置会同时封锁周围 8 个格子中的 4 个边邻格（对角格反而成为唯一合法连接点），棋盘的有效自由度随步数指数衰减。
一个完整的搜索树有多大？21 块拼板、每块有 1~8 种朝向（翻转后可能更多）、初始可放置位置超过 400 个。朴素展开的节点数是天文数字。所以真正的算法工作集中在三件事上：
- 状态压缩：把 20×20 棋盘塞进整数，让合法性判定变成几条位运算。
- 放置生成：预计算每块拼板所有合法朝向，并在位棋盘上做移位与掩码。
- 搜索决策：不做全展开，而是每层只挑”约束最强”的落点，把分支因子压到个位数。
二、位棋盘：20×20 怎么塞进一个 long
20×20 = 400 位，超过一个 long（64 位）。常见做法是每行用一个 int 的低 20 位，共 20 个 int；但更省事的是每行一个 long 的低 20 位，用 long[20]。这样”整行平移””整行取反”都是一次操作，跨行时才需要进位处理。
public final class Board {
public static final int N = 20;
public static final long ROW_MASK = (1L << N) - 1; // 低 20 位全 1
final long[] rows = new long[N]; // rows[r] 的第 c 位表示 (r,c) 是否被占用
final int[] owner = new int[N * N]; // 仅用于回溯：记录每格属于哪块拼板
boolean get(int r, int c) { return (rows[r] & (1L << c)) != 0; }
void set(int r, int c, boolean v) {
if (v) rows[r] |= (1L << c);
else rows[r] &= ~(1L << c);
}
}
关键设计：为什么不用 long[7] 的平坦位图。 平坦位图在跨行移位时需要处理”上一行溢出到下一行”，一个 shl 之后要做 4 次掩码修正；而行数组的写法里，斜向移位只是”逐行移位 + 行号偏移”，代码量少一半、可读性也好得多。
三种邻接关系都要能一条语句算出来
格格不入的合法性完全由邻接关系决定，所以必须能快速算出：
- 边邻（4 邻域）：某个 1 的上下左右
- 角邻（4 对角）：某个 1 的对角线相邻
- 角链可达：从已有拼板通过一串角接触能走到的格子（这是”必须角接触”的精确定义）
前两者可以直接用位运算：
/** 所有被占用格子的 4 邻域（边接触候选） */
static long[] edgeNeighbors(long[] rows) {
long[] out = new long[N];
for (int r = 0; r < N; r++) {
long v = rows[r];
long horiz = ((v << 1) | (v >>> 1)) & ROW_MASK; // 左右
long vert = 0;
if (r > 0) vert |= rows[r - 1];
if (r + 1 < N) vert |= rows[r + 1];
out[r] = (horiz | vert) & ~v; // 排除自身
}
return out;
}
/** 所有被占用格子的 4 对角邻域 */
static long[] cornerNeighbors(long[] rows) {
long[] out = new long[N];
for (int r = 0; r < N; r++) {
long m = 0;
if (r > 0) m |= ((rows[r - 1] << 1) | (rows[r - 1] >>> 1));
if (r + 1 < N) m |= ((rows[r + 1] << 1) | (rows[r + 1] >>> 1));
out[r] = m & ROW_MASK & ~rows[r];
}
return out;
}
第三个关系”角链可达”没法用一条位运算解决，它本身是一个图上可达性问题——但它只需要在给定拼板的连通分量上算一次，缓存起来即可。
三、拼板的规范化：21 块 × 8 种朝向
Blokus 的 21 块拼板按格子数分五组：1 格 1 块、2 格 1 块、3 格 2 块、4 格 5 块、5 格 12 块。每块用格子坐标的集合表示，然后把 8 种变换（4 旋转 × 是否翻转）全部生成，去重后作为候选朝向。
record Piece(String name, int[][] cells) {}
/** 8 种变换后去重，返回所有朝向（每个朝向内部按行优先排序，便于后续移位） */
static List<int[][]> orientations(int[][] cells) {
List<int[][]> result = new ArrayList<>();
Set<String> seen = new HashSet<>();
int[][] cur = cells;
for (int flip = 0; flip < 2; flip++) {
for (int rot = 0; rot < 4; rot++) {
int[][] t = normalize(cur);
String key = key(t);
if (seen.add(key)) result.add(t);
cur = rotate90(cur);
}
cur = flipHorizontal(cells);
}
return result;
}
normalize 很关键：它把形状平移到左上角原点（最小行、最小列都归零），并保持相对形状。没有这一步，同一个形状的多种表达会被当成不同朝向，搜索空间凭空放大数倍。
rotate90 的实现要小心方向一致性，否则翻转会与旋转混淆：
static int[][] rotate90(int[][] cells) {
int[][] out = new int[cells.length][2];
for (int i = 0; i < cells.length; i++) {
// (r, c) -> (c, maxC - r)，随后 normalize 会把偏移吃掉
out[i][0] = cells[i][1];
out[i][1] = -cells[i][0];
}
return out;
}
四、合法落点：三步判定压成一次位运算
给定玩家已有的占用位图 own、全场占用位图 all，一个朝向 cells 平移到 (dr, dc) 后是否合法，需要同时满足：
- 该朝向的所有格子都为空（不与任何拼板重叠）
- 该朝向的所有格子都不与
own边邻（否则形成边接触） - 该朝向至少有一个格子与
own角邻，或与own属于同一角链连通分量（第一块除外）
条件 1、2 都可以写成位掩码检查。先把朝向转成一个”位图模板”，平移用移位实现：
static boolean fits(Board b, long[] own, int[][] cells, int dr, int dc) {
for (int[] cell : cells) {
int r = dr + cell[0], c = dc + cell[1];
if (r < 0 || r >= N || c < 0 || c >= N) return false;
if (b.get(r, c)) return false; // 条件 1
if (edgeAdjacent(own, r, c)) return false; // 条件 2
}
return true;
}
static boolean edgeAdjacent(long[] own, int r, int c) {
if (r > 0 && ((own[r - 1] >>> c) & 1) != 0) return true;
if (r + 1 < N && ((own[r + 1] >>> c) & 1) != 0) return true;
if (c > 0 && ((own[r] >>> (c - 1)) & 1) != 0) return true;
if (c + 1 < N && ((own[r] >>> (c + 1)) & 1) != 0) return true;
return false;
}
工程上的取舍：上面的 fits 是逐格判定，逻辑最清晰，但每次调用有 k × 5 次位测试。如果要把分支生成提速一个量级，就得把”每个朝向的所有平移位姿”预计算成 long[] 的候选掩码表，让 fits 退化成两三个 & 操作。我在这里保留逐格版本——因为它让死锁检测的调试成本低得多，而真正的性能瓶颈不在这里（见第六节）。
条件 3 的”角链”需要单独处理：
/** 从 own 出发，沿角接触 BFS，返回所有可达的空格位图 */
static long[] cornerReachable(long[] own) {
long[] reached = own.clone();
boolean changed = true;
while (changed) {
changed = false;
long[] next = cornerNeighbors(reached);
for (int r = 0; r < N; r++) {
long add = next[r] & ~reached[r];
if (add != 0) { reached[r] |= add; changed = true; }
}
}
return reached; // 与 all 取反后的交集即为"可接触区"
}
注意这里的迭代收敛：角接触是传递的，所以 A 通过 B 角接触到 C 也算合法。这正是 Blokus 里”沿着对角线一路铺过去”的策略基础。每一轮把新格子并入集合，直到不再增长——最坏 O(N²) 轮，每轮 O(N) 位运算，对 20×20 完全够用。
五、搜索：用最大独立集挑选落点
到这里能生成全部合法落点，但数量仍然太多。真正的剪枝思路来自一个观察：
在 Blokus 中，落点的价值 ≈ 它封锁了多少对手的空地。
所以每层不枚举所有落点，而是先算一个”价值图”，再用近似最大独立集的方式选出少量互不冲突的高价值落点。更进一步，落点之间本身存在冲突（同一块拼板的不同朝向不能同时用），这天然构成一个冲突图，选一组两两不冲突的最优落点就是最大独立集（MIS）问题——NP 难，但可以用贪心 + 局部改进拿到很好的近似。
final class Solver {
private final Board board = new Board();
private final long[][] own = new long[4][Board.N]; // 4 名玩家的占用位图
private final boolean[][] used = new boolean[4][21];
private final List<int[]> path = new ArrayList<>(); // 回溯记录
/** 迭代加深：只保留价值最高的 K 个落点，K 随剩余拼板数自适应 */
boolean solve(int player, int remaining) {
if (remaining == 0) return true;
List<Candidate> cands = generateCandidates(player);
if (cands.isEmpty()) return false;
// 贪心构造冲突图的独立集近似解
List<Candidate> chosen = greedyIndependentSet(cands, beamWidth(remaining));
for (Candidate c : chosen) {
place(c);
if (solve(nextPlayer(player), remainingAfter(nextPlayer(player)))) return true;
unplace(c);
}
return false;
}
}
beamWidth 的自适应是性能要点：剩余拼板越多，越应该”贪心只看最好的几个”；剩下最后几块时分支已经很少，反而可以放宽。一个实测有效的公式是 K = max(3, 12 - remaining)。
generateCandidates 的实现需要注意”第一块必须覆盖起始格”这条规则——它把首层的分支从数千压到几十：
private List<Candidate> generateCandidates(int p) {
List<Candidate> out = new ArrayList<>();
long[] reachable = (isEmpty(p)) ? startOnly() : cornerReachable(own[p]);
for (int pi = 0; pi < 21; pi++) {
if (used[p][pi]) continue;
for (int[][] o : ORIENT[pi]) {
// 用朝向的包围盒裁剪平移枚举范围
int h = height(o), w = width(o);
for (int dr = 0; dr + h <= Board.N; dr++) {
for (int dc = 0; dc + w <= Board.N; dc++) {
if (!fits(board, own[p], o, dr, dc)) continue;
if (!touchesReachable(reachable, o, dr, dc)) continue;
out.add(new Candidate(pi, o, dr, dc, score(o, dr, dc)));
}
}
}
}
return out;
}
六、评分函数与复杂度分析
评分只做一件有意义的事：估计这块拼板放下后，能为自己增加多少”角接触面”，同时压缩对手多少空间。
/** 价值 = 新增角接触点 × 2 + 封锁对手的边邻格 × 1 - 自身暴露边数 */
private int score(int[][] o, int dr, int dc) {
int newCorners = 0, blockedEdges = 0, exposed = 0;
for (int[] cell : o) {
int r = dr + cell[0], c = dc + cell[1];
newCorners += countOwnCorners(r, c);
blockedEdges += countFreeEdges(r, c);
exposed += countFreeEdgesToOuter(r, c);
}
return newCorners * 2 + blockedEdges - exposed;
}
三项系数的来源：新增角接触点直接决定后续可放置空间，权重最高；封锁边邻格压缩对手，权重中等；暴露在棋盘外侧的边会导致对手从这里绕过去，作为惩罚项。这些系数是用少量对局回归出来的，不是理论最优——这也是启发式搜索的通用现实：评分函数的调参成本往往高于搜索本身的实现成本。
复杂度上：
- 朝向预计算：21 块 × 8 变换 × O(5) 排序，常数级，一次性。
- 单层候选生成：每块拼板
21 × 8 × O(400)，上界约 27 万次位测试，实测平均 1~2 万次（大部分平移在包围盒裁剪后就被fits快速否掉）。 - 搜索：束宽 K 自适应到 3~12，深度为 21 步（每块拼板一次），上界
O(K^21)显然不可行；实际有效深度远小于 21，因为剩余拼板一旦无法放置就立刻回溯，真正的搜索树远比形式上小。
这套实现的实际表现：单线程在 20×20 棋盘上求解单人 21 块全部放完，平均 0.3~2 秒；如果目标改为”最大化放入块数”（允许提前结束），搜索时间随目标放宽而线性下降。
七、四人对局的扩展
单人求解器稍作改动就能变成四人对局引擎：把 own 扩展为 4 组位图，每层轮换 player，每个玩家都跑同一套候选生成与评分。区别只有一处——评分函数中的”封锁对手空间”从针对单一对手变成针对 3 个对手的加权和：
int blockedForOthers = 0;
for (int opp = 0; opp < 4; opp++) {
if (opp == p) continue;
blockedForOthers += countFreeEdgesOf(own[opp], o, dr, dc);
}
这一步会让复杂度乘上 3（每个候选多算两遍对手），但因为候选集已经被束宽截断，实测只增加约 40% 时间。性能上完全可接受。
八、小结
把格格不入当算法题做，收获的是三个可以迁移的工程模式：
- 位棋盘 + 掩码邻域：任何二维格点类游戏（扫雷、五子棋、生命游戏）都能用这套写法把邻接判定降到常数。行数组优于平坦位图，收益在读代码时的直观性。
- 朝向规范化：旋转/翻转的全部变体先生成再去重，避免搜索空间被等价状态撑爆。
normalize与key是这一步的全部价值。 - 用冲突图剪枝：当合法动作彼此冲突时，最大独立集提供了”选少量高质量动作”的理论框架，贪心近似就够用——不必追求精确解。
最后一点值得强调：这个求解器的评分函数只用了三类特征，但已经能把 21 块拼板在 2 秒内排完。在启发式搜索里，选对特征比选对算法更重要——同样这套位棋盘，如果评分只用”能放多少格”，搜索会退化成近似的随机枚举，2 秒变成 2 分钟以上。
