俄罗斯方块的 AI 通常被当作”落点评估问题”：枚举每个方块的所有旋转与落点，用高度、空洞、Bumpiness 等特征打分选最优。但真正让高手和程序拉开差距的是另一类目标——Perfect Clear（完美清除）：用若干块把整个 10×20 的场地清空，得到极高的分数加成。
Perfect Clear 不是”评估”能解决的问题，它是一个精确覆盖（Exact Cover）问题：给定场地当前被占用的格子集合，问”由接下来 k 个方块组成的形状集合，能否恰好铺满所有空格且互不重叠”。本文用 Java 实现一个 PC 求解器：位棋盘表示 + 方块形状预生成 + 精确覆盖回溯 + 奇偶性不变式剪枝，并说明为什么奇偶判定能在搜索开始前就否掉大量无解局面。
一、位棋盘：10 列用位掩码，行用数组
10 列刚好可以塞进一个 short 的低 10 位。整块场地用 int[] rows（20 行）表示，每行一个 10 位掩码。这样一行”是否满”就是一次整数比较，一次”落地”就是一次数组拷贝。
public class Field {
public static final int W = 10, H = 20, FULL_ROW = 0x3FF; // 低 10 位全 1
public final int[] rows = new int[H]; // rows[y] 的第 x 位为 1 表示 (x,y) 已占用
public boolean isFree(int x, int y) {
return y >= 0 && y < H && (rows[y] & (1 << x)) == 0;
}
public int empties() {
int n = 0;
for (int y = 0; y < H; y++) n += W - Integer.bitCount(rows[y]);
return n;
}
public Field copy() {
Field f = new Field();
System.arraycopy(rows, 0, f.rows, 0, H);
return f;
}
public void restore(Field f) { System.arraycopy(f.rows, 0, rows, 0, H); }
}
二、方块形状：预生成全部旋转与平移位掩码
七种方块（I, O, T, S, Z, J, L），每种最多 4 个旋转，每个旋转在 10 列内最多约 10 种水平平移，总形状数不到 200 个。把它们预先枚举成”占据相对坐标列表”，搜索时只需做一次合法性检查：
import java.util.*;
public class Shapes {
/** 一个形状 = 若干 (dx, dy) 相对坐标；dy 向下为正 */
public static final class Piece {
public final int[][] cells;
public final String name;
Piece(String name, int[][] cells) { this.name = name; this.cells = cells; }
public int height() {
int h = 0;
for (int[] c : cells) h = Math.max(h, c[1] + 1);
return h;
}
public int width() {
int w = 0;
for (int[] c : cells) w = Math.max(w, c[0] + 1);
return w;
}
}
/** 生成某方块的全部旋转 + 全部水平平移，用于精确覆盖枚举 */
public static List<Piece> variants(String name) {
List<int[][]> bases = switch (name) {
case "I" -> List.of(new int[][]{{0,0},{1,0},{2,0},{3,0}},
new int[][]{{0,0},{0,1},{0,2},{0,3}});
case "O" -> List.of(new int[][]{{0,0},{1,0},{0,1},{1,1}});
case "T" -> List.of(new int[][]{{0,0},{1,0},{2,0},{1,1}},
new int[][]{{1,0},{0,1},{1,1},{1,2}},
new int[][]{{0,1},{1,1},{2,1},{1,0}},
new int[][]{{0,0},{0,1},{0,2},{1,1}});
default -> throw new IllegalArgumentException(name);
};
// S/Z/J/L 同理，此处从略；核心是"把每个旋转的坐标相对化后整体平移 0..W-width"
List<Piece> out = new ArrayList<>();
for (int[][] base : bases) {
Piece p0 = new Piece(name, base);
for (int dx = 0; dx + p0.width() <= W; dx++) {
int[][] shifted = new int[base.length][2];
for (int i = 0; i < base.length; i++)
shifted[i] = new int[]{base[i][0] + dx, base[i][1]};
out.add(new Piece(name, shifted));
}
}
return out;
}
}
关键点：形状的规范化。同一个方块的不同旋转可能产生坐标重复，必须先按 (dx,dy) 排序去重，否则精确覆盖会把同一形状算成多个候选，导致分支数翻倍。
三、精确覆盖回溯：选最”受限”的空格
Perfect Clear 的标准解法不是”枚举方块放置位置”，而是枚举空格：每次取一个必须被覆盖的空格（选候选最少的那个），尝试所有能覆盖它的方块放置，然后递归。这与数独的 DLX 思路一致，只是覆盖集合是”方块 × 位置”。
public class PerfectClearSolver {
private final Field field;
private int nodes = 0;
private final int[] order; // 待放置方块的顺序（可重排以加速）
public PerfectClearSolver(Field field, String queue) {
this.field = field;
this.order = queue.chars().map(c -> c - '0').toArray();
}
public boolean solve() {
nodes = 0;
return dfs(0);
}
private boolean dfs(int depth) {
nodes++;
if (depth == order.length) return field.empties() == 0; // 全部用完且恰好铺满
if (field.empties() != 4 * (order.length - depth)) return false; // 面积不匹配，立即失败
// 找到"可覆盖候选最少"的空格（MRV：Minimum Remaining Values）
int bestX = -1, bestY = -1, bestCount = Integer.MAX_VALUE;
for (int y = 0; y < Field.H; y++) {
for (int x = 0; x < Field.W; x++) {
if (!field.isFree(x, y)) continue;
int cnt = 0;
for (Shapes.Piece p : Shapes.variants(nameOf(order[depth]))) {
if (canPlace(p, x, y)) cnt++;
}
if (cnt < bestCount) { bestCount = cnt; bestX = x; bestY = y; }
}
}
if (bestX < 0) return false; // 已经没有空格但方块还没用完
if (bestCount == 0) return false; // 该空格无法被当前方块覆盖
for (Shapes.Piece p : Shapes.variants(nameOf(order[depth]))) {
if (!canPlace(p, bestX, bestY)) continue;
Field snap = field.copy();
place(p, bestX, bestY);
if (dfs(depth + 1)) return true;
field.restore(snap);
}
return false;
}
/** 该形状能否以 (x,y) 为**第一个格子**的锚点放置且不越界、不重叠 */
private boolean canPlace(Shapes.Piece p, int x, int y) {
for (int[] c : p.cells) {
int nx = x + c[0], ny = y + c[1];
if (!field.isFree(nx, ny)) return false;
}
return true;
}
private void place(Shapes.Piece p, int x, int y) {
for (int[] c : p.cells) field.rows[y + c[1]] |= 1 << (x + c[0]);
}
private static String nameOf(int idx) { return "ITOSZJL".substring(idx, idx + 1); }
}
dfs 里的 empties() != 4 * 剩余块数 是一句极划算的剪枝：每块恰好 4 格，面积必须严格匹配，否则无论怎么放都不可能铺满。这一步在回溯早期就能砍掉大量无效分支。
四、奇偶性不变式：先判”有没有可能”
Perfect Clear 的一个经典结论来自棋盘着色奇偶性。把场地按 (x+y) % 2 染成两种颜色（黑白相间），设空格中黑格数为 B、白格数为 W，则：
- 每个方块（除 O 之外）无论怎么旋转，覆盖的黑格与白格之差恒为 ±1 或 0；I 型横放在不同起点可覆盖 (2,2) 或 (1,3)/(3,1)。
- 因此一个必要条件可以精确写成：存在一组方块的”颜色签名”之和，等于场地的 (B, W)。
在没有 O 块时，这条不变式等价于 |B − W| ≤ 可用块数，且 (B − W) 与块数同奇偶。工程上实现为极快的预判：
/** 棋盘着色计数：返回 {黑格空位数, 白格空位数} */
public static int[] colorCount(Field f) {
int black = 0, white = 0;
for (int y = 0; y < Field.H; y++)
for (int x = 0; x < Field.W; x++)
if (f.isFree(x, y)) {
if (((x + y) & 1) == 0) black++; else white++;
}
return new int[]{black, white};
}
/** 奇偶性与面积双重必要条件；返回 false 说明必然无解，可直接跳过搜索 */
public static boolean feasible(int black, int white, int pieces) {
if ((black + white) != 4 * pieces) return false; // 面积不匹配
int diff = Math.abs(black - white);
return diff <= pieces && ((diff & 1) == (pieces & 1)); // 奇偶与上界约束
}
这两个条件都是必要非充分：通过检查不代表能铺满，但不通过就一定无解。在随机场地上，它们能在进入回溯前就否掉相当比例的局面——这正是”棋型知识”在搜索问题中的典型用法：用数学结构换时间。
五、完整项目结构与运行
tetris-perfect-clear/
├── src/main/java/com/example/pc/
│ ├── Field.java # 10 位行掩码棋盘
│ ├── Shapes.java # 方块旋转/平移预生成
│ ├── PerfectClearSolver.java # MRV 精确覆盖回溯
│ └── Main.java # 演示：给定场地与方块序列，判断能否 PC
public class Main {
public static void main(String[] args) {
Field f = new Field();
// 构造一个 2 行已填满、其余全空的场地（10x18 空格）
for (int x = 0; x < Field.W; x++) { f.rows[18] |= 1 << x; f.rows[19] |= 1 << x; }
int[] c = PerfectClearSolver.colorCount(f);
System.out.println("空位黑格=" + c[0] + " 白格=" + c[1]);
String queue = "123456"; // 六块：I T O S Z J
if (!PerfectClearSolver.feasible(c[0], c[1], queue.length())) {
System.out.println("奇偶/面积条件不满足，必然无解，直接跳过搜索");
return;
}
PerfectClearSolver solver = new PerfectClearSolver(f, queue);
boolean ok = solver.solve();
System.out.println(ok ? "存在 Perfect Clear 方案" : "不存在 Perfect Clear 方案");
}
}
六、复杂度与工程要点
- 状态数：每次递归选最受限空格，分支数约等于”能覆盖该空格的形状放置数”，通常 4~12。理论最坏 O(12^k)，但 MRV 顺序让它平均大幅下降。
- 面积剪枝是首层过滤：
empties != 4 × 剩余块数一次比较即返回，收益极高。 - 奇偶不变式是搜索前置门槛：不满足则直接判定无解，避免了整棵树的无用展开。
- 位掩码成本：
Field.copy()是 20 个 int 的数组拷贝（80 字节），比对象深拷贝快一个数量级；这让”每分支快照 + 回溯”的开销几乎可以忽略。 - 形状去重必须做：同一旋转重复生成会让分支数成倍增加，且不影响正确性，只是白做。
Perfect Clear 把俄罗斯方块从”猜哪个落点更好”的评估问题，变成了”能不能恰好铺满”的组合搜索问题。它提醒我们：同一个游戏，可以对应完全不同的算法范式——评估面向”近似最优”，精确覆盖面向”存在性证明”。
