拉密（Rummikub）是一款风靡全球的数字牌游戏，规则比麻将简单，但计算难度被严重低估：手里 14 张牌，每张都要能拼进”顺子”或”同数三张”里，还得算清桌面上的牌组能不能被打散重组。高手和新手的差距几乎全在”拆解”这一步——同一手牌，新手只能看到两个牌组，高手能拆出四个。
这篇文章用 Java 实现拉密的两个计算内核：牌组合法性判定（含通配牌 Joker）与最大拆解动态规划（把手牌切成尽可能多的合法牌组）。
一、牌的表示与规范形式
拉密共 106 张牌：4 种颜色 × 数字 1~13 × 2 套 = 104 张，加上 2 张通配牌。用位编码表示一张牌：
bit 0..12 -> 数字 1..13（13 位）
bit 13..15 -> 颜色 0..3（2 位）
bit 16 -> 是否通配
或者更简单：用两个字段 number（1~13，0 表示通配）和 color（0~3，-1 表示通配）。
public final class Tile implements Comparable<Tile> {
public final int number; // 1..13；通配牌为 0
public final int color; // 0..3；通配牌为 -1
public final boolean joker;
public Tile(int number, int color) {
this.number = number;
this.color = color;
this.joker = (number == 0);
}
public static Tile joker() { return new Tile(0, -1); }
@Override public int compareTo(Tile o) {
if (joker != o.joker) return joker ? 1 : -1;
return color != o.color ? Integer.compare(color, o.color)
: Integer.compare(number, o.number);
}
@Override public String toString() {
if (joker) return "JK";
return new String[]{"R","B","Y","K"}[color] + number;
}
}
二、牌组合法性：顺子与同数
拉密的合法牌组只有两种：
同数组（Group）：3 或 4 张牌，数字相同、颜色互不相同。
顺子（Run）：至少 3 张连续数字的同色牌，长度 3~13。
通配牌可以替代任意数字与颜色，每张牌组最多用 2 张通配（多数规则约定），且通配不能相邻使用（不同规则版本略有差异，此处按”最多 2 张且不限制位置”实现）。
public final class MeldValidator {
/** 判定一组牌是否为合法同数组 */
public static boolean isGroup(java.util.List<Tile> tiles) {
if (tiles.size() < 3 || tiles.size() > 4) return false;
int number = -1;
java.util.Set<Integer> colors = new java.util.HashSet<>();
int jokers = 0;
for (Tile t : tiles) {
if (t.joker) { jokers++; continue; }
if (number == -1) number = t.number;
else if (number != t.number) return false;
if (!colors.add(t.color)) return false; // 颜色重复即非法
}
// 通配牌数量上限 2，且同数组总张数不超过 4
if (jokers > 2) return false;
return number != -1 || jokers <= 2;
}
/** 判定一组牌是否为合法顺子（需要先按数字排序，通配插空） */
public static boolean isRun(java.util.List<Tile> tiles) {
if (tiles.size() < 3) return false;
java.util.List<Tile> solids = new java.util.ArrayList<>();
int jokers = 0;
int color = -1;
for (Tile t : tiles) {
if (t.joker) { jokers++; continue; }
if (color == -1) color = t.color;
else if (color != t.color) return false; // 顺子必须同色
solids.add(t);
}
if (jokers > 2) return false;
solids.sort(java.util.Comparator.comparingInt(t -> t.number));
// 数字必须严格递增且无重复
for (int i = 1; i < solids.size(); i++) {
if (solids.get(i).number <= solids.get(i - 1).number) return false;
}
// 用通配填满空隙，剩余通配延伸两端
int span = solids.isEmpty() ? 0
: solids.get(solids.size() - 1).number - solids.get(0).number + 1;
int needed = span - solids.size(); // 内部空隙数
if (needed > jokers) return false;
int left = jokers - needed; // 剩余通配用于两端延伸
int minNum = solids.isEmpty() ? 1 : solids.get(0).number;
int maxNum = solids.isEmpty() ? 0 : solids.get(solids.size() - 1).number;
// 两端延伸不能越界 1..13
int canExtendLeft = Math.max(0, minNum - 1);
int canExtendRight = Math.max(0, 13 - maxNum);
return left <= canExtendLeft + canExtendRight
&& maxNum - minNum + 1 + left <= 13
&& maxNum - minNum + 1 + left >= 3;
}
public static boolean isValid(java.util.List<Tile> tiles) {
return isGroup(tiles) || isRun(tiles);
}
}
这里有一个容易被忽略的边界：顺子长度不能超过 13（1~13）。加了通配延伸之后必须重新检查上限，否则会出现”9,10,J,通配,通配 只能在 13 以内”这类越界判定错误。
三、规范形式：避免同一牌组重复枚举
一手 14 张牌能组成多少种牌组？如果不去重，DP 的候选集会被同质化组合撑爆。
做法是对牌组做规范化排序：同数组按颜色升序、顺子按数字升序、通配统一排在末尾。再拼成字符串作为唯一键。
public final class MeldCanonicalizer {
/** 生成牌组的规范字符串，同构牌组得到同一 key */
public static String key(java.util.List<Tile> tiles) {
java.util.List<Tile> solids = new java.util.ArrayList<>();
java.util.List<Tile> jokers = new java.util.ArrayList<>();
for (Tile t : tiles) (t.joker ? jokers : solids).add(t);
if (MeldValidator.isGroup(tiles)) {
solids.sort(java.util.Comparator.comparingInt(t -> t.color));
} else {
solids.sort(java.util.Comparator.comparingInt(t -> t.number));
}
StringBuilder sb = new StringBuilder();
for (Tile t : solids) sb.append(t).append('|');
for (int i = 0; i < jokers.size(); i++) sb.append("JK|");
return sb.toString();
}
}
规范化的好处不止去重：它让”同一手牌的不同排列”在 DP 里共享同一个状态，把搜索空间从”排列数”降到”集合数”，这是指数级到组合级的量级差异。
四、核心算法：最大拆解 DP
问题的正式表述：给定一手牌（多重集），求把它划分成最多数量的合法牌组的方案。这是集合划分问题，一般情形是 NP 难的，但拉密的牌数小（通常 ≤ 14 张待出牌，加桌面牌更多），可以用”子集枚举 + 记忆化”精确求解。
状态用一个位掩码表示”已使用哪些牌”，f[mask] 表示用 mask 中的牌能拼出的最大牌组数：
f[0] = 0
f[mask] = max over sub ⊆ mask, sub 合法牌组 { 1 + f[mask \ sub] }
为避免重复枚举（A∪B 与 B∪A 是同一划分），强制”必须包含 mask 中编号最小的那张牌”，这条剪枝能把枚举量降一个数量级。
public final class MaxMeldPartition {
private final java.util.List<Tile> hand;
private final int[] memo;
private final int[][] choice; // 记录最优选择，用于回溯方案
public MaxMeldPartition(java.util.List<Tile> hand) {
this.hand = hand;
int n = hand.size();
this.memo = new int[1 << n];
this.choice = new int[1 << n][];
java.util.Arrays.fill(memo, -1);
memo[0] = 0;
}
/** 返回最多能拼出的合法牌组数 */
public int solve() {
return dp((1 << hand.size()) - 1);
}
private int dp(int mask) {
if (memo[mask] >= 0) return memo[mask];
int low = Integer.numberOfTrailingZeros(mask); // 必含的最低位
int best = 0;
int[] bestSub = null;
// 枚举所有包含 low 的子集
int rest = mask & ~(1 << low);
for (int sub = rest; ; sub = (sub - 1) & rest) {
int candidate = sub | (1 << low);
java.util.List<Tile> group = toTiles(candidate);
if (group.size() >= 3 && MeldValidator.isValid(group)) {
int remain = mask & ~candidate;
int val = 1 + dp(remain);
if (val > best) { best = val; bestSub = new int[]{candidate}; }
}
if (sub == 0) break;
}
memo[mask] = best;
choice[mask] = bestSub;
return best;
}
private java.util.List<Tile> toTiles(int mask) {
java.util.List<Tile> out = new java.util.ArrayList<>();
for (int i = 0; i < hand.size(); i++) {
if ((mask & (1 << i)) != 0) out.add(hand.get(i));
}
return out;
}
/** 回溯出具体方案 */
public java.util.List<java.util.List<Tile>> buildSolution() {
java.util.List<java.util.List<Tile>> out = new java.util.ArrayList<>();
int mask = (1 << hand.size()) - 1;
dp(mask);
while (mask != 0 && choice[mask] != null) {
int sub = choice[mask][0];
out.add(toTiles(sub));
mask &= ~sub;
}
return out;
}
}
复杂度分析很重要：子集枚举的单次代价是 O(2^k)，k 为当前 mask 的位数。总代价近似 O(3^n)——n=14 时约 4.8×10⁶，Java 里几十毫秒；n=20 时涨到 3.5×10⁹，必须换算法。
n 较大时的替代方案是贪心 + 局部搜索：先按”长度优先”贪心切分出牌组，再用模拟退火随机打散重组，接受使牌组数不减的改动。拉密实战中 14 张手牌的规模，精确 DP 完全够用。
五、桌面重组：更难的那一半
真正让拉密成为高手游戏的是”桌面操作”——你不只能出自己的牌，还能把桌面上已有的牌组打散重新组合，只要重组后所有牌组依然合法。
这是一个全局可行性判定问题：把桌面所有牌 + 手中待出的牌合成一个大池，要求存在一个划分方案，使得每个牌组合法，且每一张出的牌都被用上。
public final class TableReorganizer {
/**
* 判断在桌面牌 pool 中加入 hand 中的牌后，是否存在合法划分
* pool 是桌面所有牌（含原牌组），hand 是本次要打出的牌
*/
public static boolean canPlaceAll(java.util.List<Tile> pool) {
int n = pool.size();
if (n > 22) return heuristicCheck(pool); // 规模过大时降级
int full = (1 << n) - 1;
boolean[] reachable = new boolean[1 << n];
reachable[0] = true;
// 按 popcount 递增顺序做可达性 DP
for (int mask = 0; mask <= full; mask++) {
if (!reachable[mask]) continue;
int low = Integer.numberOfTrailingZeros(~mask & full);
if (low >= n) continue;
int rest = full & ~mask & ~(1 << low);
for (int sub = rest; ; sub = (sub - 1) & rest) {
int cand = sub | (1 << low);
if (Integer.bitCount(cand) >= 3
&& MeldValidator.isValid(toTiles(pool, cand))) {
reachable[mask | cand] = true;
}
if (sub == 0) break;
}
}
return reachable[full];
}
/** 大规模降级：贪心 + 一次局部改进 */
private static boolean heuristicCheck(java.util.List<Tile> pool) {
java.util.List<Tile> remain = new java.util.ArrayList<>(pool);
boolean progress = true;
while (progress) {
progress = false;
for (int i = 0; i < remain.size() && !progress; i++) {
for (int j = i + 1; j < remain.size() && !progress; j++) {
for (int k = j + 1; k < remain.size() && !progress; k++) {
java.util.List<Tile> g = java.util.Arrays.asList(
remain.get(i), remain.get(j), remain.get(k));
if (MeldValidator.isValid(g)) {
remain.remove(k); remain.remove(j); remain.remove(i);
progress = true;
}
}
}
}
}
return remain.isEmpty();
}
private static java.util.List<Tile> toTiles(java.util.List<Tile> pool, int mask) {
java.util.List<Tile> out = new java.util.ArrayList<>();
for (int i = 0; i < pool.size(); i++) {
if ((mask & (1 << i)) != 0) out.add(pool.get(i));
}
return out;
}
}
注意 reachable 数组在 n=22 时是 4M 个 boolean，约 4MB，可以接受；n=24 就 16MB，必须换方案。这个”可达性 DP”比”最大拆解 DP”更省，因为它只需布尔值而非最优值，且可以在找到 reachable[full] 后立即返回。
六、AI 出牌决策
把上面三块拼起来，一个能打的 AI 就成立：
public final class RummikubAI {
public static java.util.List<java.util.List<Tile>> bestMove(
java.util.List<Tile> hand, java.util.List<java.util.List<Tile>> table,
int minInitialMeld) {
MaxMeldPartition mp = new MaxMeldPartition(hand);
int count = mp.solve();
java.util.List<java.util.List<Tile>> plan = mp.buildSolution();
// 首次出牌门槛：牌面点数之和需达到 minInitialMeld（通常 30）
int sum = 0;
for (java.util.List<Tile> g : plan) {
for (Tile t : g) if (!t.joker) sum += t.number;
}
if (table.isEmpty() && sum < minInitialMeld) {
return java.util.Collections.emptyList(); // 不够门槛，跳过
}
// 若桌面可重组，尝试把多余牌塞进已有牌组
java.util.List<Tile> pool = new java.util.ArrayList<>();
for (java.util.List<Tile> g : table) pool.addAll(g);
for (java.util.List<Tile> g : plan) pool.addAll(g);
if (!TableReorganizer.canPlaceAll(pool)) {
return java.util.Collections.emptyList(); // 方案不可行，保守跳过
}
return plan;
}
}
真正的强 AI 还会做一个”留牌评估”：出牌后剩余手牌的”最大拆解数”越高，说明留牌越灵活。这个指标本质上是 f[剩余mask]，DP 已经算好了，直接查表即可——这是记忆化 DP 的额外红利：一次求解得到全部子集的最优值。
七、复杂度与实战建议
| 环节 | 复杂度 | 说明 |
|---|---|---|
| 牌组合法性 | O(k log k) | k ≤ 13，排序主导 |
| 最大拆解 DP | O(3ⁿ) 记忆化 | n ≤ 14 时毫秒级 |
| 桌面重组判定 | O(3ⁿ) 布尔 DP | n ≤ 22 可承受 |
| 贪心降级 | O(n³) 每轮 | 大规模兜底 |
四条实战建议：
- 通配牌单独记账。通配不参与排序键，只记录”可用数量”，判定时统一插空，能显著简化边界处理。
- 优先枚举含最低位的子集。这条剪枝让划分枚举从”所有子集”降到”含固定元素的子集”，实测加速 5~10 倍。
- 顺子长度上限 13 要显式检查。通配延伸后忘记检查上限，是这类求解器最常见的正确性 bug。
- 桌面重组的判定要”全牌参与”。拉密规则要求重组后桌面上不能有孤儿牌，因此必须做整体可达性判断，而不能逐组独立验证。
拉密的算法内核其实回答了一个朴素问题：“这一手牌能不能全部用掉？” 答案藏在集合划分的指数空间里。把它压进 O(3ⁿ) 的记忆化 DP，你就能看见高手眼中的那张牌桌——每一张牌都不是孤立的，它们在等待一次重组。
