Clickomania回溯算法节点膨胀问题：优化getMoves与backtracking函数

我为Clickomania游戏实现了回溯解法，代码能正确求解测试用例，但节点展开数量远多于同事的实现。比如针对如下测试棋盘：

5 5 4
1 3 2 1 3
3 4 2 2 4
4 1 4 2 3
3 4 4 4 2
2 1 4 1 2

我的解法展开了187个节点，而合理的节点展开数应为30个。现在聚焦于getMoves和backtracking函数，以下是具体优化建议：

原代码实现 #

import java.util.LinkedList;
import java.util.List;
import java.util.Set;


import es.uma.ada.backtracking.Backtracking;
import es.uma.ada.datastructures.tuple.Pair;
import es.uma.ada.problem.puzzle.clickomania.ClickomaniaPuzzle;

/**
 * Backtracking for clickomania. Based in backtracking for Latin squares
 *
 */
public class ClickomaniaBacktracking extends Backtracking {
    /**
     * The puzzle being solved
     */
    private ClickomaniaPuzzle clickomania;
    /**
     * Solution found   
     */
    private List<Pair<Integer, Integer>> sol;

    /**
     * Creates the solver
     */
    public ClickomaniaBacktracking() {
        super();
        clickomania = null;
        sol = null;
    }

    /**
     * Creates the solver with a specific puzzle
     * @param clickomania a clickomania puzzle
     */
    public ClickomaniaBacktracking (ClickomaniaPuzzle clickomania) {
        this();
        this.clickomania = clickomania.clone();
    }

    /**
     * Returns the puzzle being solved
     * @return the puzzle being solved
     */
    public ClickomaniaPuzzle getPuzzle() {
        return clickomania;
    }


    /**
     * Defines the original puzzle
     * @param puzzle the original puzzle
     */
    public void setPuzzle(ClickomaniaPuzzle puzzle) {
        clickomania = puzzle.clone(); // a copy is created
        sol = null;
    }

    @Override
    public String getName() {
        return "Clickomania backtracking";
    }

    @SuppressWarnings("unchecked")
    @Override
    protected boolean backtracking(Object state) {
        Pair<ClickomaniaPuzzle, List<Pair<Integer, Integer>>> p = (Pair<ClickomaniaPuzzle, List<Pair<Integer, Integer>>>) state;
        ClickomaniaPuzzle board = p.getFirst();
        List<Pair<Integer, Integer>> currentSol = p.getSecond();

        boolean ok = false;

        if (board.isEmpty()) {
            sol = currentSol;
            ok = true;
        } else {
            nodes++;
            List<Pair<Integer, Integer>> moves = getMoves(board);
            for (Pair<Integer, Integer> move : moves) {
                ClickomaniaPuzzle newBoard = board.clone();
                newBoard.click(move.getFirst(), move.getSecond());
                List<Pair<Integer, Integer>> newSol = new LinkedList<>(currentSol);
                newSol.add(move);
                ok = backtracking(new Pair<>(newBoard, newSol));
                if (ok) {
                    break;
                }
            }
        }
        return ok;
    }

    /**
     * Returns the possible moves in a given board configuration
     * @param board the board
     * @return a list of positions that can be clicked
     */
private List<Pair<Integer, Integer>> getMoves(ClickomaniaPuzzle board) {
        int m = board.getRows();
        int n = board.getColumns();
        List<Pair<Integer, Integer>> moves = new LinkedList<Pair<Integer, Integer>>();

        // TODO
        // Complete this function.
        // Hint: check the block associated with each position on the board, 
        // and keep those with a non-trivial size. Be careful not to include
        // equivalent moves (recall that clicking on any position of a certain
        // block will remove that block, and therefore all those clicks would
        // be equivalent).
        //


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board.getBlock(j, i).size() > 1) {
                    //check the move is not equivalent with one already in the list
                    boolean equivalent = false;
                    for (Pair<Integer, Integer> move : moves) {
                        if (board.getBlock(move.getFirst(), move.getSecond()).equals(board.getBlock(j, i))) {
                            equivalent = true;
                            break;
                        }
                    }
                    if (!equivalent) moves.add(new Pair<>(j, i));
                }
            }
        }

        //sort moves by column
        moves.sort((o1, o2) -> {
            if (o1.getSecond() < o2.getSecond()) return -1;
            else if (o1.getSecond() > o2.getSecond()) return 1;
            else return 0;
        });


        return moves;
    }

    @Override
    protected Object initialState() {
        return new Pair<ClickomaniaPuzzle, List<Pair<Integer, Integer>>> (clickomania, new LinkedList<Pair<Integer, Integer>>());
    }

    /**
     * Returns the solution found
     * @return the solution
     */
    public List<Pair<Integer, Integer>> getSolution() {
        return sol;
    }

}

具体优化措施 #

1. 重构getMoves函数，避免等价重复move #

原代码通过遍历已选move对比块的方式去重，效率低且可能因getBlock返回新集合导致equals判断失效。改为标记已处理单元格，每个块仅生成一个代表move：

private List<Pair<Integer, Integer>> getMoves(ClickomaniaPuzzle board) {
    int rows = board.getRows();
    int cols = board.getColumns();
    List<Pair<Integer, Integer>> moves = new LinkedList<>();
    boolean[][] visited = new boolean[rows][cols];

    for (int row = 0; row < rows; row++) {
        for (int col = 0; col < cols; col++) {
            if (!visited[row][col]) {
                Set<Pair<Integer, Integer>> block = board.getBlock(row, col);
                if (block.size() > 1) {
                    moves.add(new Pair<>(row, col));
                    // 标记整个块的单元格为已访问，避免重复处理
                    for (Pair<Integer, Integer> pos : block) {
                        visited[pos.getFirst()][pos.getSecond()] = true;
                    }
                } else {
                    visited[row][col] = true;
                }
            }
        }
    }

    // 按块大小降序+列升序排序，优先消除大块
    moves.sort((o1, o2) -> {
        int size1 = board.getBlock(o1.getFirst(), o1.getSecond()).size();
        int size2 = board.getBlock(o2.getFirst(), o2.getSecond()).size();
        int sizeCompare = Integer.compare(size2, size1);
        if (sizeCompare != 0) {
            return sizeCompare;
        }
        return Integer.compare(o1.getSecond(), o2.getSecond());
    });

    return moves;
}

2. 加入可行性剪枝 #

在回溯前检查棋盘是否存在无法消除的孤立单元格（或直接判断剩余单元格总数是否为奇数，若每次消除至少2个则无解），提前终止无效分支：

// 类中新增辅助方法
private boolean hasUnremovableCells(ClickomaniaPuzzle board) {
    int rows = board.getRows();
    int cols = board.getColumns();
    // 简单剪枝：若剩余单元格数为奇数，且游戏要求完全消除（最后一个块也需消除则不适用）
    int totalCells = 0;
    for (int row = 0; row < rows; row++) {
        for (int col = 0; col < cols; col++) {
            if (board.getCell(row, col) != 0) { // 假设0代表空单元格
                totalCells++;
            }
        }
    }
    // 若剩余单元格数为奇数，且当前没有可消除的块（所有块大小为1），则无解
    List<Pair<Integer, Integer>> moves = getMoves(board);
    return totalCells % 2 != 0 && moves.isEmpty();
}

// 修改backtracking函数
@SuppressWarnings("unchecked")
@Override
protected boolean backtracking(Object state) {
    Pair<ClickomaniaPuzzle, List<Pair<Integer, Integer>>> p = (Pair<ClickomaniaPuzzle, List<Pair<Integer, Integer>>>) state;
    ClickomaniaPuzzle board = p.getFirst();
    List<Pair<Integer, Integer>> currentSol = p.getSecond();

    boolean ok = false;

    if (board.isEmpty()) {
        sol = currentSol;
        ok = true;
    } else {
        // 剪枝：提前终止无解分支
        if (hasUnremovableCells(board)) {
            return false;
        }

        nodes++;
        List<Pair<Integer, Integer>> moves = getMoves(board);
        for (Pair<Integer, Integer> move : moves) {
            ClickomaniaPuzzle newBoard = board.clone();
            newBoard.click(move.getFirst(), move.getSecond());
            List<Pair<Integer, Integer>> newSol = new LinkedList<>(currentSol);
            newSol.add(move);
            ok = backtracking(new Pair<>(newBoard, newSol));
            if (ok) {
                break;
            }
        }
    }
    return ok;
}

3. 加入状态去重，避免重复处理相同棋盘 #

通过记录已处理的棋盘状态，避免递归到相同的棋盘配置：

// 类中新增成员变量
private Set<String> visitedStates = new HashSet<>();

// 修改backtracking函数
@SuppressWarnings("unchecked")
@Override
protected boolean backtracking(Object state) {
    Pair<ClickomaniaPuzzle, List<Pair<Integer, Integer>>> p = (Pair<ClickomaniaPuzzle, List<Pair<Integer, Integer>>>) state;
    ClickomaniaPuzzle board = p.getFirst();
    List<Pair<Integer, Integer>> currentSol = p.getSecond();

    boolean ok = false;

    if (board.isEmpty()) {
        sol = currentSol;
        ok = true;
    } else {
        // 生成唯一状态字符串，需确保toString能准确表示棋盘
        String stateStr = board.toString();
        if (visitedStates.contains(stateStr)) {
            return false;
        }
        visitedStates.add(stateStr);

        // 剪枝逻辑
        if (hasUnremovableCells(board)) {
            return false;
        }

        nodes++;
        List<Pair<Integer, Integer>> moves = getMoves(board);
        for (Pair<Integer, Integer> move : moves) {
            ClickomaniaPuzzle newBoard = board.clone();
            newBoard.click(move.getFirst(), move.getSecond());
            List<Pair<Integer, Integer>> newSol = new LinkedList<>(currentSol);
            newSol.add(move);
            ok = backtracking(new Pair<>(newBoard, newSol));
            if (ok) {
                break;
            }
        }
    }
    return ok;
}

内容的提问来源于stack exchange，提问作者Norhther