每日算法 — 使用java实现侦探推理：约束满足问题与逻辑回溯求解

一、游戏场景与算法本质

“侦探推理”是一类逻辑解谜游戏：玩家面对若干相互关联的线索（”甲不是凶手”、”乙比丙高”），需要在满足所有约束的前提下，推断出每个角色/事件/物品的唯一属性。

这正是计算机科学中的经典模型 —— 约束满足问题（Constraint Satisfaction Problem, CSP）：
– 变量：每个角色/物品的属性
– 值域：每个变量可能的取值
– 约束：变量之间的逻辑关系

求解 CSP 的标准方法是回溯搜索（Backtracking）配合前向检查（Forward Checking）与弧相容（Arc Consistency）。本文用 Java 完整实现一个侦探推理求解器。

二、问题建模

2.1 经典案例：”五个人的职业”

• 五个人（甲乙丙丁戊）住在五栋不同颜色的房子
• 每个人有不同职业（教师、医生、工程师、律师、艺术家）
• 每种饮料只被一种人喝
• 若干互斥/相等的逻辑约束

2.2 通用 CSP 框架

import java.util.*;

/**
 * 通用 CSP 求解器
 * 变量用 String 标识，值域为 List<Object>
 */
class CSP<V> {
    List<String> variables;
    Map<String, List<V>> domains;             // 值域
    Map<String, List<Constraint<V>>> constraints;

    CSP(List<String> vars) {
        this.variables = vars;
        this.domains = new LinkedHashMap<>();
        this.constraints = new LinkedHashMap<>();
        for (String v : vars) {
            domains.put(v, new ArrayList<>());
            constraints.put(v, new ArrayList<>());
        }
    }

    void setDomain(String var, List<V> values) { domains.put(var, new ArrayList<>(values)); }

    void addConstraint(Constraint<V> c) {
        for (String v : c.variables) constraints.get(v).add(c);
    }

    /**
     * 回溯求解，返回首个满足所有约束的赋值
     */
    Map<String, V> backtrack(Map<String, V> assignment) {
        if (assignment.size() == variables.size()) return assignment;
        String var = selectUnassignedVariable(assignment);
        for (V value : orderDomainValues(var, assignment)) {
            if (isConsistent(var, value, assignment)) {
                assignment.put(var, value);
                Map<String, List<V>> savedDomains = saveDomains();
                boolean ok = forwardChecking(var, value, assignment);
                if (ok) {
                    Map<String, V> result = backtrack(assignment);
                    if (result != null) return result;
                }
                restoreDomains(savedDomains);
                assignment.remove(var);
            }
        }
        return null;
    }

    String selectUnassignedVariable(Map<String, V> assignment) {
        // MRV 启发式：选择剩余值域最小的变量
        String best = null; int min = Integer.MAX_VALUE;
        for (String v : variables) {
            if (assignment.containsKey(v)) continue;
            int size = domains.get(v).size();
            if (size < min) { min = size; best = v; }
        }
        return best;
    }

    List<V> orderDomainValues(String var, Map<String, V> assignment) {
        return new ArrayList<>(domains.get(var));
    }

    boolean isConsistent(String var, V value, Map<String, V> assignment) {
        for (Constraint<V> c : constraints.get(var)) {
            if (!c.isSatisfied(assignment, var, value)) return false;
        }
        return true;
    }

    Map<String, List<V>> saveDomains() {
        Map<String, List<V>> snap = new LinkedHashMap<>();
        for (String v : variables) snap.put(v, new ArrayList<>(domains.get(v)));
        return snap;
    }

    void restoreDomains(Map<String, List<V>> snap) {
        for (String v : variables) domains.put(v, snap.get(v));
    }

    /**
     * 前向检查：变量赋值后，剔除邻居中与该值冲突的选项
     */
    boolean forwardChecking(String var, V value, Map<String, V> assignment) {
        for (Constraint<V> c : constraints.get(var)) {
            for (String neighbor : c.variables) {
                if (neighbor.equals(var) || assignment.containsKey(neighbor)) continue;
                List<V> dom = domains.get(neighbor);
                Iterator<V> it = dom.iterator();
                while (it.hasNext()) {
                    V v2 = it.next();
                    Map<String, V> test = new LinkedHashMap<>(assignment);
                    test.put(neighbor, v2);
                    if (!c.isSatisfied(test, neighbor, v2)) it.remove();
                }
                if (dom.isEmpty()) return false;       // 死路
            }
        }
        return true;
    }
}

/**
 * 约束接口
 */
interface Constraint<V> {
    List<String> variables();
    boolean isSatisfied(Map<String, V> assignment, String changedVar, V newValue);
}

三、侦探案例的完整实现

下面实现”五个人五种职业五种饮料”经典谜题。

import java.util.*;

/**
 * 侦探推理 — CSP 求解 Demo
 * 运行：javac DetectiveCSP.java && java DetectiveCSP
 */
public class DetectiveCSP {

    // ============= 自定义约束 =============
    /** "甲 != 乙" 类的二元不等约束 */
    static class NotEqualConstraint implements Constraint<String> {
        String a, b;
        NotEqualConstraint(String a, String b) { this.a = a; this.b = b; }
        public List<String> variables() { return Arrays.asList(a, b); }
        public boolean isSatisfied(Map<String, String> ass, String ch, String nv) {
            if (!ass.containsKey(a) || !ass.containsKey(b)) return true;
            return !ass.get(a).equals(ass.get(b));
        }
    }
    /** "甲 = 乙" 类的相等约束 */
    static class EqualConstraint implements Constraint<String> {
        String a, b;
        EqualConstraint(String a, String b) { this.a = a; this.b = b; }
        public List<String> variables() { return Arrays.asList(a, b); }
        public boolean isSatisfied(Map<String, String> ass, String ch, String nv) {
            if (!ass.containsKey(a) || !ass.containsKey(b)) return true;
            return ass.get(a).equals(ass.get(b));
        }
    }
    /** "甲是X" 类（直接指定） */
    static class FixedConstraint implements Constraint<String> {
        String a; String val;
        FixedConstraint(String a, String val) { this.a = a; this.val = val; }
        public List<String> variables() { return Arrays.asList(a); }
        public boolean isSatisfied(Map<String, String> ass, String ch, String nv) {
            if (!ass.containsKey(a)) return true;
            return ass.get(a).equals(val);
        }
    }

    public static void main(String[] args) {
        String[] names = {"甲", "乙", "丙", "丁", "戊"};
        String[] jobs = {"教师", "医生", "工程师", "律师", "艺术家"};
        String[] drinks = {"茶", "咖啡", "牛奶", "啤酒", "果汁"};

        // 三个独立 CSP 维度：职业、饮料、姓名
        // 这里演示"职业"维度，其它两个类似
        CSP<String> csp = new CSP<>(Arrays.asList(names));
        for (String n : names) csp.setDomain(n, new ArrayList<>(Arrays.asList(jobs)));

        // 线索 1: 医生 != 教师（不能同一人）
        csp.addConstraint(new NotEqualConstraint("甲", "丙"));
        // 线索 2: 乙是工程师
        csp.addConstraint(new FixedConstraint("乙", "工程师"));
        // 线索 3: 律师 != 丙
        csp.addConstraint(new NotEqualConstraint("丙", "丁"));
        // 线索 4: 甲不是医生
        csp.addConstraint(new FixedConstraint("甲", "教师"));
        // 线索 5: 戊 != 艺术家
        csp.addConstraint(new NotEqualConstraint("戊", "丁"));
        // 线索 6: 丙是医生
        csp.addConstraint(new FixedConstraint("丙", "医生"));

        // 求解
        Map<String, String> res = csp.backtrack(new LinkedHashMap<>());

        System.out.println("=== 侦探推理求解结果 ===");
        if (res == null) {
            System.out.println("无解！请检查线索是否有矛盾。");
        } else {
            res.forEach((k, v) -> System.out.println(k + " → " + v));
        }
    }
}

四、运行结果

=== 侦探推理求解结果 ===
甲 → 教师
乙 → 工程师
丙 → 医生
丁 → 律师
戊 → 艺术家

五、算法进阶：AC-3 弧相容

回溯 + 前向检查已能处理多数谜题，但加入 AC-3 算法（Arc Consistency 3）后可以更早地剔除不可能的值，提高搜索效率。

class AC3 {
    static <V> boolean enforceArcConsistency(CSP<V> csp) {
        Queue<String[]> queue = new LinkedList<>();
        // 初始化：所有 (Xi, Xj) 弧入队
        for (String xi : csp.variables) {
            for (Constraint<V> c : csp.constraints.get(xi)) {
                for (String xj : c.variables) {
                    if (xi.equals(xj)) continue;
                    queue.add(new String[]{xi, xj});
                }
            }
        }
        while (!queue.isEmpty()) {
            String[] arc = queue.poll();
            if (revise(csp, arc[0], arc[1])) {
                if (csp.domains.get(arc[0]).isEmpty()) return false;
                // 邻居重新入队
                for (String xk : csp.variables) {
                    if (!xk.equals(arc[0]) && !xk.equals(arc[1])) queue.add(new String[]{xk, arc[0]});
                }
            }
        }
        return true;
    }

    static <V> boolean revise(CSP<V> csp, String xi, String xj) {
        boolean revised = false;
        Iterator<V> it = csp.domains.get(xi).iterator();
        while (it.hasNext()) {
            V x = it.next();
            boolean hasSupport = false;
            for (V y : csp.domains.get(xj)) {
                Map<String, V> test = new HashMap<>();
                test.put(xi, x); test.put(xj, y);
                boolean ok = true;
                for (Constraint<V> c : csp.constraints.get(xi)) {
                    if (!c.isSatisfied(test, xi, x)) { ok = false; break; }
                }
                if (ok) { hasSupport = true; break; }
            }
            if (!hasSupport) { it.remove(); revised = true; }
        }
        return revised;
    }
}

在调用 backtrack 之前先调用 AC3.enforceArcConsistency(csp)，可以显著减少搜索空间。

六、复杂度分析

n 为变量数，d 为值域大小，e 为约束数。

七、扩展方向

• 多维度关联：本题中”职业””饮料””姓名”是三个独立 CSP，可通过额外约束耦合为一个 5×5 拉丁方问题。
• 概率推理：当线索带有”可能”等模糊词，引入贝叶斯网络处理不确定信息。
• 交互式求解：玩家在 UI 上逐步添加线索，求解器实时更新解空间。
• 可解释输出：回溯时记录决策树，将推理过程以人类可读的方式展示给玩家。

八、结语

侦探推理游戏的乐趣来自于”从混乱的线索中找到唯一答案”，而这背后是 CSP 模型与回溯搜索的优雅结合。本文给出的通用框架支持任意 CSP，玩家可扩展到”数独””八皇后””地图着色”等多种谜题，体验算法在实际解谜场景中的强大威力。