每日算法 — 使用java实现点灯游戏：BFS状态空间搜索与最少步数求解

游戏简介

点灯游戏（Lights Out）是一款经典的益智解谜游戏。玩家面对一个由灯泡组成的矩形网格，每次点击某个灯泡，该灯泡及其上下左右相邻的灯泡状态都会翻转（亮变灭、灭变亮）。游戏目标是在最少的步数内将所有灯泡点亮或熄灭。本文将用Java实现点灯游戏的核心求解算法，重点讲解BFS状态空间搜索与最少步数求解策略。

核心算法思路

状态表示

对于一个m×n的灯泡网格，每个灯泡有亮（1）和灭（0）两种状态，因此整个棋盘可以用一个长度为m×n的二进制串表示。在Java中，我们可以使用int或long类型来存储状态（最多支持64个灯泡）。

BFS状态空间搜索

从初始状态出发，每次尝试点击一个灯泡，生成新的状态。使用BFS可以确保找到最短的操作序列。关键在于：

• 状态去重：使用HashSet记录已访问的状态，避免重复搜索
• 状态转移：点击位置(i,j)时，翻转该位置及四邻域的灯泡状态
• 目标检测：检查当前状态是否全部灯泡达到目标状态

最少步数求解

BFS天然具有最短路径性质，即第一次到达目标状态时，对应的操作步数即为最少步数。我们通过记录每个状态的前驱状态和操作，可以在找到解后回溯输出完整的操作序列。

Java实现

import java.util.*;

/**
 * 点灯游戏求解器 - BFS状态空间搜索
 */
public class LightsOutSolver {

    private final int rows;
    private final int cols;
    private final int totalCells;
    // 预计算每个位置点击时影响的状态掩码
    private final int[] clickMasks;

    public LightsOutSolver(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.totalCells = rows * cols;
        this.clickMasks = new int[totalCells];
        precomputeMasks();
    }

    /**
     * 预计算每个位置点击时的状态翻转掩码
     * 点击位置(i,j)会翻转自身及上下左右邻居
     */
    private void precomputeMasks() {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int pos = i * cols + j;
                int mask = 0;
                // 自身
                mask |= (1 << pos);
                // 上
                if (i > 0) mask |= (1 << ((i - 1) * cols + j));
                // 下
                if (i < rows - 1) mask |= (1 << ((i + 1) * cols + j));
                // 左
                if (j > 0) mask |= (1 << (i * cols + (j - 1)));
                // 右
                if (j < cols - 1) mask |= (1 << (i * cols + (j + 1)));
                clickMasks[pos] = mask;
            }
        }
    }

    /**
     * BFS求解最少步数解法
     * @param initialState 初始状态，每位表示灯泡亮灭
     * @param targetState 目标状态，通常为0（全灭）或全1（全亮）
     * @return 操作序列，每个元素为点击的位置编号；若无解返回null
     */
    public List<Integer> solve(int initialState, int targetState) {
        // 已访问的状态集合
        Set<Integer> visited = new HashSet<>();
        // 记录每个状态的前驱状态及操作
        Map<Integer, Integer> prevState = new HashMap<>();
        Map<Integer, Integer> prevAction = new HashMap<>();

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(initialState);
        visited.add(initialState);

        while (!queue.isEmpty()) {
            int state = queue.poll();

            // 到达目标状态
            if (state == targetState) {
                return reconstructPath(prevState, prevAction, initialState, targetState);
            }

            // 尝试点击每一个位置
            for (int pos = 0; pos < totalCells; pos++) {
                int newState = state ^ clickMasks[pos];
                if (!visited.contains(newState)) {
                    visited.add(newState);
                    prevState.put(newState, state);
                    prevAction.put(newState, pos);
                    queue.offer(newState);
                }
            }
        }

        return null; // 无解（理论上点灯游戏总有解）
    }

    /**
     * 回溯重建操作路径
     */
    private List<Integer> reconstructPath(Map<Integer, Integer> prevState,
                                          Map<Integer, Integer> prevAction,
                                          int initialState, int targetState) {
        List<Integer> path = new ArrayList<>();
        int state = targetState;
        while (state != initialState) {
            path.add(prevAction.get(state));
            state = prevState.get(state);
        }
        Collections.reverse(path);
        return path;
    }

    /**
     * 打印状态为网格形式
     */
    public void printState(int state) {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int pos = i * cols + j;
                System.out.print(((state >> pos) & 1) == 1 ? "○ " : "● ");
            }
            System.out.println();
        }
    }

    /**
     * 将操作序列应用到初始状态，验证结果
     */
    public int applyMoves(int state, List<Integer> moves) {
        for (int pos : moves) {
            state ^= clickMasks[pos];
        }
        return state;
    }

    public static void main(String[] args) {
        // 5x5点灯游戏
        LightsOutSolver solver = new LightsOutSolver(5, 5);

        // 随机生成初始状态
        Random rand = new Random(42);
        int initialState = rand.nextInt(1 << 25);
        int targetState = 0; // 目标：全部熄灭

        System.out.println("初始状态：");
        solver.printState(initialState);

        long start = System.currentTimeMillis();
        List<Integer> solution = solver.solve(initialState, targetState);
        long end = System.currentTimeMillis();

        if (solution != null) {
            System.out.println("\n找到最少步数解法，共 " + solution.size() + " 步");
            System.out.println("搜索耗时：" + (end - start) + "ms");
            System.out.println("操作序列（位置编号）：" + solution);

            // 验证
            int result = solver.applyMoves(initialState, solution);
            System.out.println("\n验证结果：");
            solver.printState(result);
            System.out.println("是否达到目标：" + (result == targetState));
        } else {
            System.out.println("未找到解法");
        }
    }
}

算法优化：双向BFS

对于较大的棋盘（如6×6），状态空间达到2^36，单向BFS可能内存不足。此时可以采用双向BFS：

/**
 * 双向BFS求解，从初始状态和目标状态同时搜索
 */
public List<Integer> solveBidirectional(int initialState, int targetState) {
    if (initialState == targetState) return new ArrayList<>();

    Set<Integer> visitedFromStart = new HashSet<>();
    Set<Integer> visitedFromTarget = new HashSet<>();
    Map<Integer, Integer> prevStart = new HashMap<>();
    Map<Integer, Integer> prevTarget = new HashMap<>();
    Map<Integer, Integer> actionStart = new HashMap<>();
    Map<Integer, Integer> actionTarget = new HashMap<>();

    Queue<Integer> queueStart = new LinkedList<>();
    Queue<Integer> queueTarget = new LinkedList<>();
    queueStart.offer(initialState);
    queueTarget.offer(targetState);
    visitedFromStart.add(initialState);
    visitedFromTarget.add(targetState);

    while (!queueStart.isEmpty() || !queueTarget.isEmpty()) {
        // 扩展起点方向
        if (!queueStart.isEmpty()) {
            Integer meet = expandLayer(queueStart, visitedFromStart, visitedFromTarget,
                    prevStart, actionStart);
            if (meet != null) {
                return mergePaths(meet, prevStart, actionStart, prevTarget, actionTarget,
                        initialState, targetState);
            }
        }
        // 扩展终点方向
        if (!queueTarget.isEmpty()) {
            Integer meet = expandLayer(queueTarget, visitedFromTarget, visitedFromStart,
                    prevTarget, actionTarget);
            if (meet != null) {
                return mergePaths(meet, prevStart, actionStart, prevTarget, actionTarget,
                        initialState, targetState);
            }
        }
    }
    return null;
}

private Integer expandLayer(Queue<Integer> queue, Set<Integer> visited, Set<Integer> otherVisited,
                            Map<Integer, Integer> prev, Map<Integer, Integer> action) {
    int size = queue.size();
    for (int s = 0; s < size; s++) {
        int state = queue.poll();
        for (int pos = 0; pos < totalCells; pos++) {
            int newState = state ^ clickMasks[pos];
            if (!visited.contains(newState)) {
                visited.add(newState);
                prev.put(newState, state);
                action.put(newState, pos);
                if (otherVisited.contains(newState)) {
                    return newState;
                }
                queue.offer(newState);
            }
        }
    }
    return null;
}

复杂度分析

总结

本文通过Java实现了点灯游戏的BFS状态空间搜索算法。核心要点包括：

• 使用二进制掩码紧凑表示棋盘状态，利用位运算实现高效状态翻转
• BFS保证找到最少步数的操作序列
• 双向BFS可将搜索空间从O(b^d)降至O(b^(d/2))
• 预计算点击掩码避免重复计算，提升运行效率

读者可以通过扩展本代码，进一步探索线性代数方法（高斯消元）求解点灯游戏，体会不同算法思想的差异。