每日算法 — 使用java实现妙探寻凶：三值逻辑与可能性矩阵推理

一个纯粹的逻辑游戏

妙探寻凶（Cluedo）的规则简单到可以一句话说完：庄园里发生了一桩命案，凶手在 6 名嫌疑人中、凶器在 6 件道具中、案发地点在 9 个房间中。玩家通过提问”我认为是 X（嫌疑人）+ Y（凶器）+ Z（房间）”来收集信息：被问到的人如果有其中任意一张牌，就必须私下展示给你一张。

整局游戏就是一场逐步缩小候选集合的推理。真正有意思的地方在于信息的不对称性：别人给你看的那张牌只有你知道，而”某人手上没有某张牌”这个否定信息，才是推理的主力。

用算法语言表述：这是一个带否定的约束推理问题。每个对象（嫌疑人/凶器/房间）有 3 种状态：

• POSSIBLE：仍可能是答案
• IMPOSSIBLE：已被证明不是答案
• UNKNOWN：当前信息不足（初始状态对所有对象都成立，但一个组里恰好有且仅有 1 个 POSSIBLE）

关键洞察：这三值不是独立的。某个对象一旦被标记为 POSSIBLE 且该组其余全部为 IMPOSSIBLE，它就必须是答案。这种”组内唯一性”的约束会在推理中反复触发，形成一条条传播链。

本文实现一个完整推理引擎，核心是可能性矩阵（Possibility Matrix）—— 一个”玩家 × 牌”的二维表，每格是一个三值状态。

可能性矩阵的建模

九宫格式的三元组：(suspect, weapon, room)。每张牌有归属：

• 我的牌：已知，直接排除
• 对手的牌：未知
• 信封里的牌：就是答案

用 -1 表示”我在手上”、-2 表示”已被证明不在信封”、>=0 表示”在某位玩家手上”。

package com.example.cluedo;

/** 牌的种类。用 "类型 + 索引" 编码成单一 int，方便做数组下标。 */
public final class Card {
    public static final int SUSPECT = 0, WEAPON = 1, ROOM = 2;
    public static final int N_SUSPECT = 6, N_WEAPON = 6, N_ROOM = 9;

    public final int type, index;

    public Card(int type, int index) {
        this.type = type; this.index = index;
    }

    /** 全局唯一 id：0~5 嫌疑人、6~11 凶器、12~20 房间。 */
    public int id() {
        return switch (type) {
            case SUSPECT -> index;
            case WEAPON  -> N_SUSPECT + index;
            default      -> N_SUSPECT + N_WEAPON + index;
        };
    }

    public static final int TOTAL = N_SUSPECT + N_WEAPON + N_ROOM;   // 21
}

三值状态：

package com.example.cluedo;

/**
 * 一张牌相对"信封"（答案）的三种状态。
 * 注意：我们关心的是"它是否在信封里"，而不是"它在谁手上"。
 */
public enum Tri {
    POSSIBLE,    // 可能是答案
    IMPOSSIBLE,  // 已证明不是答案
    CERTAIN      // 已证明就是答案（每组恰好一个）
}

可能性矩阵的核心结构：

package com.example.cluedo;

import java.util.*;

/**
 * 可能性矩阵推理引擎。
 *
 * 维护两套信息：
 *   envelope[21]  —— 每张牌是否为答案（三值）
 *   owner[21]     —— 每张牌已知在谁手上（-1 未知，0..n-1 玩家，-2 已排除所有玩家即必在信封）
 *
 * 核心推理规则只有三条：
 *   R1  我知道自己手上有牌 → 它不在信封（IMPOSSIBLE）
 *   R2  某组只剩一个 POSSIBLE → 它 CERTAIN
 *   R3  某牌被所有玩家排除 → 它必在信封 → 该组其余全部 IMPOSSIBLE
 */
public final class DeductionEngine {

    private final int nPlayers;
    private final int myIndex;

    /** envelope[c] ∈ {POSSIBLE, IMPOSSIBLE, CERTAIN} */
    private final Tri[] envelope = new Tri[Card.TOTAL];

    /** owner[c]：-1 = 未知归属；-2 = 不为任何玩家所有（即必在信封）；否则为玩家编号 */
    private final int[] owner = new int[Card.TOTAL];

    /** 每组的牌 id 列表 */
    private final List<Integer>[] groups = new List[3];

    public DeductionEngine(int nPlayers, int myIndex) {
        this.nPlayers = nPlayers;
        this.myIndex = myIndex;
        Arrays.fill(envelope, Tri.POSSIBLE);
        Arrays.fill(owner, -1);

        groups[Card.SUSPECT] = new ArrayList<>();
        for (int i = 0; i < Card.N_SUSPECT; i++) groups[Card.SUSPECT].add(i);

        groups[Card.WEAPON] = new ArrayList<>();
        for (int i = 0; i < Card.N_WEAPON; i++)
            groups[Card.WEAPON].add(Card.N_SUSPECT + i);

        groups[Card.ROOM] = new ArrayList<>();
        for (int i = 0; i < Card.N_ROOM; i++)
            groups[Card.ROOM].add(Card.N_SUSPECT + Card.N_WEAPON + i);
    }
}

owner 与 envelope 是互为对偶的两张表：owner[c] == -2 蕴含 envelope[c] == CERTAIN，反之亦然。双向维护是避免推理断裂的关键——很多实现只维护一边，结果在”某张牌被所有人排除”这种关键推理上漏掉结论。

三条推理规则

R1：已知手牌 → 排除

/** 我确定手上有的牌：它不在信封。 */
public void markInMyHand(List<Integer> myCards) {
    for (int c : myCards) {
        owner[c] = myIndex;                 // 我知道在我这
        envelope[c] = Tri.IMPOSSIBLE;
        for (int p = 0; p < nPlayers; p++) {
            if (p != myIndex && owner[c] == p) owner[c] = -1;
        }
    }
    propagate();
}

R2：组内唯一 → 确定

/** 若某组只剩一个可能项，它就是答案。 */
private boolean applyGroupUniqueness() {
    boolean changed = false;
    for (List<Integer> g : groups) {
        int possible = 0, lastPossible = -1, certain = 0;
        for (int c : g) {
            if (envelope[c] == Tri.POSSIBLE) { possible++; lastPossible = c; }
            else if (envelope[c] == Tri.CERTAIN) certain++;
        }
        // 若已有 CERTAIN，则同组其它全部 IMPOSSIBLE（这由收敛保证，不重复做）
        if (certain >= 1) continue;

        if (possible == 1) {
            envelope[lastPossible] = Tri.CERTAIN;
            owner[lastPossible] = -2;
            changed = true;
        } else if (possible == 0) {
            throw new IllegalStateException("推理矛盾：组内无可选项");
        }
    }
    return changed;
}

R3：全员排除 → 必在信封

这是整个引擎里最强但最不直观的一条规则。如果某张牌已经证明不在任何玩家手上（包括不在我手上、也不在对手手上），那它只能在信封里。

/**
 * 若某张牌被所有玩家排除（owner 全部为"不持有"），则它必在信封。
 * 实现方式：为每张牌维护"已确认不持有它的玩家数"。
 */
private final int[] excludedByPlayers = new int[Card.TOTAL];

public void markNotHeldBy(int player, int card) {
    // 该玩家明确表示"我没有这张牌"
    owner[card] = -1;
    excludedByPlayers[card]++;   // 计数（需保证不重复计数，见 set 版）
    checkAllPlayersExcluded(card);
}

private void checkAllPlayersExcluded(int card) {
    // 若除"未知归属"外，所有玩家都被排除，则只能在信封
    if (excludedByPlayers[card] >= nPlayers) {
        envelope[card] = Tri.CERTAIN;
        owner[card] = -2;
    }
}

生产实现应该用 BitSet 记录”哪些玩家已排除该牌”，而不是计数器——因为同一玩家可能被重复告知同一信息（例如两轮提问里都展示了他没有某牌）。用 BitSet 天然幂等。

信息对称性：提问的价值计算

在妙探寻凶里，”该问什么”是一个期望信息增益问题。一次提问涉及三张牌（一人、一器、一室），对手会展示其中”他手上有的”任意一张。因此一次提问能带来多少信息，取决于对手手上有几张牌落在这次提问的三元组里。

package com.example.cluedo;

import java.util.*;

/**
 * 提问选择器。
 * 目标：在"最可能得到否定信息"的前提下，最大化"确定答案"的期望收益。
 */
public final class QueryPlanner {

    /** 对手持有某张牌的概率估计（基于剩余候选集合的均匀先验）。 */
    public static double holdProbability(DeductionEngine e, int player, int card) {
        if (e.ownerOf(card) == player) return 1.0;
        if (e.ownerOf(card) == -2) return 0.0;
        // 未知归属：按"剩余玩家剩余槽位"均摊
        int unknown = 0, available = 0;
        for (int c = 0; c < Card.TOTAL; c++) {
            if (e.ownerOf(c) == -1) {
                unknown++;
                if (e.envelopeOf(c) == Tri.POSSIBLE) available++;
            }
        }
        double p = (double) playerSlotsLeft(e, player) / Math.max(1, unknown);
        return Math.min(1.0, Math.max(0.0, p));
    }

    private static int playerSlotsLeft(DeductionEngine e, int player) {
        int hand = 0;
        for (int c = 0; c < Card.TOTAL; c++) if (e.ownerOf(c) == player) hand++;
        // 每局每人手牌数固定（这里假设 6 张，实际从规则算出）
        return Math.max(0, 6 - hand);
    }

    /**
     * 枚举所有三元组提问，按"期望信息量"排序。
     * 期望信息量 = P(至少展示一张) × 该展示带来的排除数量
     */
    public static List<int[]> rankQueries(DeductionEngine e, int targetPlayer,
                                          int topK) {
        List<int[]> cands = new ArrayList<>();
        List<Double> scores = new ArrayList<>();

        for (int s = 0; s < Card.N_SUSPECT; s++) {
            for (int w = 0; w < Card.N_WEAPON; w++) {
                for (int r = 0; r < Card.N_ROOM; r++) {
                    int cs = s;
                    int cw = Card.N_SUSPECT + w;
                    int cr = Card.N_SUSPECT + Card.N_WEAPON + r;
                    int[] q = {cs, cw, cr};

                    // 已经是 CERTAIN 的项不值得问
                    if (e.envelopeOf(cs) == Tri.CERTAIN
                            && e.envelopeOf(cw) == Tri.CERTAIN
                            && e.envelopeOf(cr) == Tri.CERTAIN) continue;

                    double pAny = 1.0;
                    for (int c : q) {
                        pAny *= (1.0 - holdProbability(e, targetPlayer, c));
                    }
                    pAny = 1.0 - pAny;    // 至少展示一张的概率

                    // 信息价值：展示后能让多少张牌被排除
                    int infoValue = 0;
                    for (int c : q) {
                        if (e.envelopeOf(c) == Tri.POSSIBLE) infoValue++;
                    }

                    // 分数：把"问已知是答案的牌"降权（浪费一次提问机会）
                    double score = pAny * infoValue;
                    cands.add(q);
                    scores.add(score);
                }
            }
        }

        // 按分数降序取前 topK
        Integer[] idx = new Integer[cands.size()];
        for (int i = 0; i < idx.length; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> Double.compare(scores.get(b), scores.get(a)));

        List<int[]> out = new ArrayList<>();
        for (int i = 0; i < Math.min(topK, idx.length); i++) out.add(cands.get(idx[i]));
        return out;
    }
}

这段逻辑有个反直觉的结论：提问的最优策略不是”把所有可能项都问一遍”，而是”优先问那些对手手上没有的”。因为对手展示一张牌，你只得到”他有这张”这条信息（弱信息：只是排除它）；而对手无法展示时，你一次性得到”这三张他都没有”（强信息：三张同时排除）。所以 pAny 越低、infoValue 越高的组合，才是真正的宝藏提问。

传播循环：直到不动点

/** 反复应用全部规则，直到不再产生新结论（求不动点）。 */
private void propagate() {
    int rounds = 0;
    boolean changed = true;
    while (changed) {
        changed = false;
        changed |= applyGroupUniqueness();
        changed |= applyOwnerToEnvelope();
        changed |= applyEnvelopeToOwner();
        rounds++;
        if (rounds > 100) throw new IllegalStateException("推理不收敛，规则存在循环");
    }
}

/** owner == -2 → envelope CERTAIN */
private boolean applyOwnerToEnvelope() {
    boolean changed = false;
    for (int c = 0; c < Card.TOTAL; c++) {
        if (owner[c] == -2 && envelope[c] != Tri.CERTAIN) {
            envelope[c] = Tri.CERTAIN;
            changed = true;
        }
    }
    return changed;
}

/** envelope CERTAIN → 同组其他 IMPOSSIBLE */
private boolean applyEnvelopeToOwner() {
    boolean changed = false;
    for (List<Integer> g : groups) {
        int certain = -1;
        for (int c : g) if (envelope[c] == Tri.CERTAIN) { certain = c; break; }
        if (certain < 0) continue;
        for (int c : g) {
            if (c != certain && envelope[c] != Tri.IMPOSSIBLE) {
                envelope[c] = Tri.IMPOSSIBLE;
                changed = true;
            }
        }
    }
    return changed;
}

三个规则交替应用、直到不动点，是约束传播的标准范式。它的正确性来自”单调性”：每条规则只会把 POSSIBLE 推向 IMPOSSIBLE/CERTAIN，永不回退，所以循环必然终止（最多 21×3 次状态转移）。

可运行的入口

package com.example.cluedo;

import java.util.*;

public final class Main {
    public static void main(String[] args) {
        // 3 人局：我(0)、甲(1)、乙(2)
        DeductionEngine e = new DeductionEngine(3, 0);

        // 我的手牌：嫌疑人1、凶器2、房间4（用 id 表示）
        List<Integer> myHand = List.of(1, Card.N_SUSPECT + 2,
                                       Card.N_SUSPECT + Card.N_WEAPON + 4);
        e.markInMyHand(myHand);
        // 我手上有 6 张，其余 3 张省略（此处只演示逻辑）
        System.out.println("初始：已知答案数 = " + e.countCertain());

        // 假设连续多次提问，每次得到"对手无法展示"或"展示了某张"
        // 场景：我向甲提问 (嫌疑人0, 凶器0, 房间0)，甲展示了凶器0
        e.markNotHeldBy(1, Card.N_SUSPECT + 0);  // 占位：实际应由展示逻辑处理
        e.markHeldBy(1, Card.N_SUSPECT + 0);

        // 我向乙提问 (嫌疑人0, 凶器0, 房间0)，乙无法展示
        // → 该三元组不在乙手上
        List<Integer> q = List.of(0, Card.N_SUSPECT, Card.N_SUSPECT + Card.N_WEAPON);
        e.recordNoShow(2, q);   // 三张都不在乙手上

        e.printMatrix();

        List<int[]> top = QueryPlanner.rankQueries(e, 1, 5);
        System.out.println("\n推荐提问（对甲）：");
        for (int[] q2 : top) {
            System.out.printf("  %s + %s + %s%n",
                    e.cardName(q2[0]), e.cardName(q2[1]), e.cardName(q2[2]));
        }
    }
}

配套补全 recordNoShow 与打印方法：

/** 记录"某玩家无法展示这三张"，等价于三次 markNotHeldBy。 */
public void recordNoShow(int player, List<Integer> cards) {
    for (int c : cards) {
        if (owner[c] != player) {          // 幂等保护
            excludedSet[player].set(c);
            owner[c] = -1;
        }
    }
    // 每张牌都检查"是否所有玩家均已排除"
    for (int c : cards) {
        if (allPlayersExcluded(c)) {
            envelope[c] = Tri.CERTAIN;
            owner[c] = -2;
        }
    }
    propagate();
}

/** 是否所有玩家都已被排除持有该牌。 */
private boolean allPlayersExcluded(int card) {
    for (int p = 0; p < nPlayers; p++) {
        if (!excludedSet[p].get(card) && owner[card] != p) return false;
    }
    return true;
}

/** 打印可读的三值矩阵。 */
public void printMatrix() {
    System.out.println("牌\t\t状态\t归属");
    for (int c = 0; c < Card.TOTAL; c++) {
        System.out.printf("%-12s\t%-10s\t%s%n",
                cardName(c), envelope[c],
                owner[c] == -2 ? "信封" : (owner[c] == -1 ? "未知" : "玩家" + owner[c]));
    }
}

public String cardName(int id) {
    String[] SUS = {" Scarlet", " Mustard", " White", " Green", " Peacock", " Plum"};
    String[] WEA = {" Candlestick", " Dagger", " LeadPipe", " Revolver", " Rope", " Wrench"};
    String[] ROO = {" Kitchen", " Ballroom", " Conservatory", " DiningRoom",
                    " Billiard", " Library", " Lounge", " Hall", " Study"};
    if (id < Card.N_SUSPECT) return SUS[id];
    if (id < Card.N_SUSPECT + Card.N_WEAPON) return WEA[id - Card.N_SUSPECT];
    return ROO[id - Card.N_SUSPECT - Card.N_WEAPON];
}

概率增强：当三值逻辑不够用时

纯三值逻辑在信息充分时非常强，但真实对局常常卡在”每组都有 2~3 个 POSSIBLE”的僵局。这时需要引入概率。

做法是利用”每人手牌数固定”这个额外约束：如果 3 人局、每人 6 张牌，那么 18 张牌在手、3 张在信封。给定所有已知信息后，剩下的未知牌必须在剩余手牌槽位中均匀分配：

/**
 * 在全部"POSSIBLE"的候选上做精确计数：
 * 枚举所有满足已知约束的"信封组合"，统计每张牌出现在信封里的频率。
 * 组数小（6+6+9）时可直接三重循环。
 */
public Map<Integer, Double> exactProbabilities(DeductionEngine e) {
    Map<Integer, Double> freq = new HashMap<>();
    int total = 0;

    for (int s : e.candidatesOf(Card.SUSPECT)) {
        for (int w : e.candidatesOf(Card.WEAPON)) {
            for (int r : e.candidatesOf(Card.ROOM)) {
                if (!e.consistentWithHands(s, w, r)) continue;
                total++;
                freq.merge(s, 1.0, Double::sum);
                freq.merge(w, 1.0, Double::sum);
                freq.merge(r, 1.0, Double::sum);
            }
        }
    }
    Map<Integer, Double> p = new HashMap<>();
    for (var en : freq.entrySet()) p.put(en.getKey(), en.getValue() / total);
    return p;
}

consistentWithHands 检查”这三张牌都不在任何人手上”这一条，加上手牌数守恒。当候选集合缩小到每种 ≤ 3 个时，最多 3×3×3 = 27 种组合，枚举成本可忽略，但得到的精确后验概率比任何启发式都可靠——这就是这类推理游戏的”终局杀招”。

复杂度分析

整体是线性于状态空间的，单次推理在微秒级。真正的开销反而在”提问选择”这一步——但 324 个候选完全可以暴力枚举。

与其他推理游戏的关系

妙探寻凶的这套”三值逻辑 + 可能性矩阵”可以平移到很多同类游戏：

• 数独：三值逻辑退化为”候选数集合”，组内唯一性规则就是”唯一候选数法”（Naked Single / Hidden Single）。
• 数织（Nonogram）：三值变成”黑/白/未知”，传播靠”行约束的可行位置区间”。
• Mastermind：三值逻辑换成”每位的可能颜色集合 + 计数约束”。
• 扫雷：三值变成”雷/安全/未知”，传播靠”邻域计数减去已知雷数”。

所以把本文的 DeductionEngine 抽象一下，只需要替换两样东西：组（group）的定义和规则集合，就能变成上述任一游戏的推理内核。

小结

妙探寻凶把”不确定性推理”压缩到了最干净的形态：每一张牌只有三种状态（可能是答案、不可能、确定），每一条新信息都是一个集合交集的运算。本文的三条规则——已知手牌排除、组内唯一确定、全员排除归信封——交替应用至不动点，就是完整的演绎闭包。而当演绎卡住时，切换到”枚举候选三元组 + 精确计数”，就能得到后验概率，把”猜”变成”算”。

这套结构最值得带走的一点是：信息的价值不在于”我知道了什么”，而在于”我排除了什么”。对手无法展示的那一次，才是真正的信息富矿。