每日算法 — 使用java实现推箱子：约束满足问题CSP建模与前向检查回溯

引言

推箱子（Sokoban）被公认为计算复杂性最高的益智游戏之一，其判定问题被证明是PSPACE完全问题。与华容道、迷宫等经典问题不同，推箱子的核心难点在于箱子只能推不能拉，导致大量状态为不可逆死锁。本文使用Java将推箱子建模为约束满足问题（Constraint Satisfaction Problem, CSP），通过变量定义、约束传播与前向检查回溯搜索，系统性地求解经典关卡。

核心算法原理

推箱子的CSP建模

传统推箱子求解使用BFS或A*搜索状态空间，但状态数随箱子数指数增长。CSP建模提供了另一种视角：

变量：每个箱子$X_i$的”目标目标点”分配，即每个箱子最终应推到哪个目标位置。

定义域：对于每个箱子，其可行目标位置需满足可达性约束——箱子在不被其他箱子阻挡的情况下，能够被推到该目标。

约束：
1. 唯一性约束：每个目标位置只能分配给一个箱子（All-Different）
2. 可达性约束：箱子$i$能到达目标$j$（考虑其他箱子的静态位置）
3. 死锁约束：箱子不能被推到角落或墙边非目标位置（Simple Deadlock）
4. 隧道约束：箱子在狭窄通道中不能互相阻挡

前向检查（Forward Checking）

前向检查是一种约束传播技术：每当为一个变量赋值时，立即检查所有相关未赋值变量的定义域，移除与当前赋值冲突的值。若某变量定义域为空，则立即回溯。

在推箱子中，当我们确定箱子$A$推到目标$T_1$后，其他箱子就不能再选择$T_1$。同时，箱子$A$到$T_1$的路径上经过的格子对其他箱子形成新的障碍物约束。

死锁检测

推箱子中大部分搜索时间都浪费在死锁状态上。常见死锁类型：

角落死锁：箱子被推到两个墙形成的角落且该角落不是目标
墙边死锁：箱子沿墙推到非目标位置且另一侧被其他箱子或墙堵住
冻结死锁：箱子被其他箱子完全包围，无法向任何方向推动

本文在CSP求解前预处理地图，标记所有潜在的死锁位置，从各箱子的定义域中预先排除会导致死锁的目标分配。

Java实现

项目结构

src/
├── sokoban/
│   ├── Level.java            // 关卡表示
│   ├── Position.java         // 坐标类
│   └── Direction.java        // 方向枚举
├── csp/
│   ├── CSPVariable.java      // CSP变量（箱子-目标分配）
│   ├── CSPConstraint.java    // 约束接口
│   ├── DeadlockDetector.java // 死锁检测器
│   ├── ForwardChecking.java  // 前向检查求解器
│   └── Reachability.java     // 可达性分析
└── solver/
    └── SokobanSolver.java    // 主求解器

关卡表示

package sokoban;

import java.util.*;

/**
 * 推箱子关卡，使用字符网格表示
 * #: 墙, @: 玩家, $: 箱子, .: 目标, +: 玩家站在目标上, *: 箱子在目标上
 */
public class Level {
    public static final char WALL = '#';
    public static final char FLOOR = ' ';
    public static final char BOX = '$';
    public static final char TARGET = '.';
    public static final char PLAYER = '@';
    public static final char PLAYER_ON_TARGET = '+';
    public static final char BOX_ON_TARGET = '*';

    private final char[][] grid;
    private final int rows, cols;
    private Position playerStart;
    private final List<Position> boxStarts;
    private final List<Position> targets;

    public Level(String[] lines) {
        this.rows = lines.length;
        this.cols = Arrays.stream(lines).mapToInt(String::length).max().orElse(0);
        this.grid = new char[rows][cols];
        this.boxStarts = new ArrayList<>();
        this.targets = new ArrayList<>();

        for (int r = 0; r < rows; r++) {
            String line = lines[r];
            for (int c = 0; c < cols; c++) {
                char ch = c < line.length() ? line.charAt(c) : FLOOR;
                grid[r][c] = ch;
                if (ch == PLAYER || ch == PLAYER_ON_TARGET) {
                    playerStart = new Position(r, c);
                }
                if (ch == BOX || ch == BOX_ON_TARGET) {
                    boxStarts.add(new Position(r, c));
                }
                if (ch == TARGET || ch == PLAYER_ON_TARGET || ch == BOX_ON_TARGET) {
                    targets.add(new Position(r, c));
                }
            }
        }
    }

    public boolean isWall(int r, int c) {
        return r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == WALL;
    }

    public boolean isTarget(int r, int c) {
        return targets.contains(new Position(r, c));
    }

    public int getRows() { return rows; }
    public int getCols() { return cols; }
    public Position getPlayerStart() { return playerStart; }
    public List<Position> getBoxStarts() { return boxStarts; }
    public List<Position> getTargets() { return targets; }
    public char[][] getGrid() { return grid; }
}

死锁检测器

package csp;

import sokoban.Level;
import sokoban.Position;

/**
 * 预计算所有可能的死锁位置
 */
public class DeadlockDetector {
    private final boolean[][] deadlock;
    private final Level level;

    public DeadlockDetector(Level level) {
        this.level = level;
        this.deadlock = new boolean[level.getRows()][level.getCols()];
        computeDeadlocks();
    }

    /**
     * 计算所有非目标角落死锁位置
     * 角落死锁：两个相邻方向都是墙（或地图边界）
     */
    private void computeDeadlocks() {
        for (int r = 0; r < level.getRows(); r++) {
            for (int c = 0; c < level.getCols(); c++) {
                if (level.isWall(r, c) || level.isTarget(r, c)) continue;

                // 检查四个方向的墙组合
                boolean[] wall = new boolean[4]; // 上右下左
                wall[0] = level.isWall(r - 1, c);
                wall[1] = level.isWall(r, c + 1);
                wall[2] = level.isWall(r + 1, c);
                wall[3] = level.isWall(r, c - 1);

                // 角落死锁：任意两个相邻方向都是墙
                for (int i = 0; i < 4; i++) {
                    if (wall[i] && wall[(i + 1) % 4]) {
                        deadlock[r][c] = true;
                        break;
                    }
                }
            }
        }
    }

    public boolean isDeadlock(int r, int c) {
        return deadlock[r][c];
    }

    /**
     * 检查将箱子推到目标位置是否会导致死锁
     */
    public boolean causesDeadlock(Position boxPos, Position pushDir, Level level) {
        int newR = boxPos.row + pushDir.row;
        int newC = boxPos.col + pushDir.col;
        return deadlock[newR][newC];
    }
}

可达性分析

package csp;

import sokoban.Level;
import sokoban.Position;
import java.util.*;

/**
 * 计算箱子在特定静态障碍物配置下的可达位置
 */
public class Reachability {

    /**
     * BFS计算玩家从起点可达的所有位置（考虑箱子为障碍物）
     */
    public static Set<Position> playerReachable(Level level, Position playerStart,
                                                  Set<Position> boxPositions) {
        Set<Position> visited = new HashSet<>();
        Queue<Position> queue = new LinkedList<>();
        queue.add(playerStart);
        visited.add(playerStart);

        int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        while (!queue.isEmpty()) {
            Position curr = queue.poll();
            for (int[] d : dirs) {
                int nr = curr.row + d[0];
                int nc = curr.col + d[1];
                Position next = new Position(nr, nc);
                if (level.isWall(nr, nc) || boxPositions.contains(next) || visited.contains(next)) {
                    continue;
                }
                visited.add(next);
                queue.add(next);
            }
        }
        return visited;
    }

    /**
     * 检查箱子能否从起始位置被推到目标位置
     * 核心思想：箱子向某方向移动的前提是玩家站在其反方向
     */
    public static boolean canPushBoxToTarget(Level level, Position boxStart,
                                              Position target, Set<Position> otherBoxes) {
        Set<Position> visited = new HashSet<>();
        Queue<BoxState> queue = new LinkedList<>();
        queue.add(new BoxState(boxStart, otherBoxes));
        visited.add(boxStart);

        int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};

        while (!queue.isEmpty()) {
            BoxState state = queue.poll();
            if (state.boxPos.equals(target)) return true;

            for (int[] d : dirs) {
                // 箱子新位置
                int newBoxR = state.boxPos.row + d[0];
                int newBoxC = state.boxPos.col + d[1];
                Position newBoxPos = new Position(newBoxR, newBoxC);

                // 玩家需要站的位置（箱子反方向）
                int playerR = state.boxPos.row - d[0];
                int playerC = state.boxPos.col - d[1];
                Position playerNeed = new Position(playerR, playerC);

                // 检查可行性
                if (level.isWall(newBoxR, newBoxC)) continue;
                if (state.otherBoxes.contains(newBoxPos)) continue;
                if (visited.contains(newBoxPos)) continue;

                // 检查玩家是否能到达所需位置
                Set<Position> allBoxes = new HashSet<>(state.otherBoxes);
                allBoxes.add(state.boxPos); // 当前箱子位置也是障碍
                Set<Position> reachable = playerReachable(level, playerNeed, allBoxes);
                // 简化：假设玩家总可以从某处到达push位置（实际需要完整状态搜索）
                // 这里使用简化判断：所需位置不是墙且不被其他箱子占据
                if (!level.isWall(playerR, playerC) && !state.otherBoxes.contains(playerNeed)) {
                    visited.add(newBoxPos);
                    Set<Position> newOthers = new HashSet<>(state.otherBoxes);
                    newOthers.remove(state.boxPos);
                    newOthers.add(newBoxPos);
                    queue.add(new BoxState(newBoxPos, newOthers));
                }
            }
        }
        return false;
    }

    private static class BoxState {
        Position boxPos;
        Set<Position> otherBoxes;
        BoxState(Position box, Set<Position> others) {
            this.boxPos = box; this.otherBoxes = others;
        }
    }
}

CSP变量与前向检查

package csp;

import sokoban.Level;
import sokoban.Position;
import java.util.*;

/**
 * CSP变量：每个箱子可以分配到的目标位置集合
 */
public class CSPVariable {
    public final int boxIndex;
    public List<Position> domain; // 可行目标位置

    public CSPVariable(int boxIndex, List<Position> domain) {
        this.boxIndex = boxIndex;
        this.domain = new ArrayList<>(domain);
    }
}

/**
 * 前向检查回溯求解器
 */
public class ForwardChecking {
    private final List<CSPVariable> variables;
    private final Level level;
    private final DeadlockDetector detector;

    public ForwardChecking(Level level, List<CSPVariable> variables) {
        this.level = level;
        this.variables = variables;
        this.detector = new DeadlockDetector(level);
    }

    /**
     * 主求解入口
     * @return 分配方案：箱子索引 -> 目标位置
     */
    public Map<Integer, Position> solve() {
        Map<Integer, Position> assignment = new HashMap<>();
        List<List<Position>> domainsBackup = new ArrayList<>();
        for (CSPVariable v : variables) {
            domainsBackup.add(new ArrayList<>(v.domain));
        }

        if (backtrack(0, assignment, domainsBackup)) {
            return assignment;
        }
        return Collections.emptyMap();
    }

    private boolean backtrack(int varIndex, Map<Integer, Position> assignment,
                               List<List<Position>> domains) {
        if (varIndex == variables.size()) {
            return true; // 所有变量已赋值
        }

        CSPVariable var = variables.get(varIndex);
        List<Position> currentDomain = new ArrayList<>(domains.get(varIndex));

        for (Position target : currentDomain) {
            // 检查唯一性：该目标是否已被分配
            if (assignment.values().contains(target)) continue;

            // 检查死锁：箱子到该目标的路径是否经过死锁区域
            boolean safe = true;
            for (Map.Entry<Integer, Position> entry : assignment.entrySet()) {
                // 简化检查：已分配箱子不在死锁位置
                if (detector.isDeadlock(entry.getValue().row, entry.getValue().col)) {
                    safe = false; break;
                }
            }
            if (!safe) continue;

            assignment.put(var.boxIndex, target);

            // 前向检查：更新后续变量的定义域
            boolean consistent = true;
            List<List<Position>> newDomains = new ArrayList<>();
            for (int i = 0; i < domains.size(); i++) {
                newDomains.add(new ArrayList<>(domains.get(i)));
            }

            for (int i = varIndex + 1; i < variables.size(); i++) {
                newDomains.get(i).remove(target); // 移除已被占用的目标
                if (newDomains.get(i).isEmpty()) {
                    consistent = false;
                    break;
                }
            }

            if (consistent) {
                if (backtrack(varIndex + 1, assignment, newDomains)) {
                    return true;
                }
            }

            assignment.remove(var.boxIndex);
        }

        return false;
    }
}

主求解器

package solver;

import sokoban.Level;
import sokoban.Position;
import csp.*;
import java.util.*;

/**
 * 推箱子CSP求解器主入口
 */
public class SokobanSolver {

    /**
     * 求解关卡：返回每个箱子的目标分配
     */
    public static Map<Integer, Position> solve(Level level) {
        List<Position> boxes = level.getBoxStarts();
        List<Position> targets = level.getTargets();

        if (boxes.size() != targets.size()) {
            throw new IllegalArgumentException("Boxes and targets count mismatch");
        }

        DeadlockDetector detector = new DeadlockDetector(level);
        List<CSPVariable> variables = new ArrayList<>();

        // 为每个箱子构建定义域：可达且非死锁的目标
        for (int i = 0; i < boxes.size(); i++) {
            List<Position> domain = new ArrayList<>();
            Set<Position> otherBoxes = new HashSet<>(boxes);
            otherBoxes.remove(boxes.get(i));

            for (Position target : targets) {
                if (detector.isDeadlock(target.row, target.col)) continue;
                // 可达性检查（简化版）
                if (Reachability.canPushBoxToTarget(level, boxes.get(i), target, otherBoxes)) {
                    domain.add(target);
                }
            }
            variables.add(new CSPVariable(i, domain));
        }

        // 按定义域大小排序（MRV启发式）
        variables.sort(Comparator.comparingInt(v -> v.domain.size()));

        ForwardChecking fc = new ForwardChecking(level, variables);
        return fc.solve();
    }

    public static void main(String[] args) {
        // 经典微线关卡 (XSB格式简化)
        String[] level1 = {
            "    #####",
            "    #   #",
            "    #$  #",
            "  ###  $##",
            "  #  $ $ #",
            "### # ## #",
            "#   # ## #",
            "#   $  . #",
            "#####  . #",
            "    #  . #",
            "    ######"
        };

        Level level = new Level(level1);
        Map<Integer, Position> solution = solve(level);

        System.out.println("=== Sokoban CSP Solution ===");
        for (Map.Entry<Integer, Position> entry : solution.entrySet()) {
            Position box = level.getBoxStarts().get(entry.getKey());
            Position target = entry.getValue();
            System.out.printf("Box %d at (%d,%d) -> Target (%d,%d)%n",
                    entry.getKey(), box.row, box.col, target.row, target.col);
        }
    }
}

算法复杂度分析

模块	时间复杂度	空间复杂度	说明
死锁预处理	$O(R \cdot C)$	$O(R \cdot C)$	$R$行$C$列，遍历所有格子
单箱子可达性	$O((R \cdot C)^2)$	$O(R \cdot C)$	BFS状态空间搜索
CSP前向检查	$O(D^B \cdot B^2)$	$O(B \cdot D)$	$B$箱子数，$D$平均定义域大小
最坏情况	指数级	多项式级	PSPACE完全问题的本质

对于小型关卡（$B \leq 5$），CSP方法能在合理时间内求解。对于大型关卡，需要结合A*启发式搜索与CSP约束传播。

与搜索方法的对比

方法	适用场景	优势	劣势
BFS状态搜索	简单关卡	完备、最优	状态爆炸
A*启发式搜索	中等关卡	有启发引导	启发函数设计困难
CSP+前向检查	箱子-目标匹配	结构化推理	不直接给出推动序列
混合方法	复杂关卡	结合两者优势	实现复杂

扩展方向

冲突导向回溯（Conflict-Directed Backjumping）：当发现约束冲突时，直接跳转到导致冲突的变量，而非逐步回溯。
弧一致性（AC-3）：在赋值前预先移除定义域中所有不一致的值，比前向检查更强的约束传播。
Macro动作：识别常见的推箱子模式（如”隧道推动”），将多个基本动作封装为宏动作，减少搜索深度。
模式数据库（Pattern Database）：预计算常见子问题的解，用于A*的 admissible 启发式估计。

总结

本文使用Java将推箱子问题建模为约束满足问题，通过死锁预处理、可达性分析与MRV启发式的前向检查回溯，实现了高效的箱子-目标分配求解。虽然CSP方法不直接输出推动序列，但它为推箱子提供了结构化的推理框架，能够有效剪枝状态空间，与A*搜索结合后可求解更复杂的关卡。推箱子作为PSPACE完全问题，其求解算法的设计充分体现了约束传播与智能搜索在组合优化中的强大威力。

Tagged with: CSP Java 前向检查推箱子死锁检测约束满足问题