Clickomania游戏回溯算法优化：通过单例块检测提升性能

public class ClickomaniaBacktracking extends Backtracking {
    private ClickomaniaPuzzle clickomania; // 当前谜题状态
    private List<Pair<Integer, Integer>> sol; // 找到的解决方案

    // ... 构造函数及其他辅助方法 ...

    @Override
    protected boolean backtracking(Object state) {
        // state 包含当前棋盘状态 (ClickomaniaPuzzle) 和已进行的移动序列 (List<Pair<Integer, Integer>>)
        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;

        // 终止条件1：棋盘已清空，找到解决方案
        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;
    }

    /**
     * 获取给定棋盘配置下所有可点击的移动。
     * 避免重复计算，并对等效移动进行去重。
     */
    private List<Pair<Integer, Integer>> getMoves(ClickomaniaPuzzle board) {
        int m = board.getRows();
        int n = board.getColumns();
        List<Pair<Integer, Integer>> moves = new LinkedList<>();
        Set<Set<Pair<Integer, Integer>>> seenBlocks = new HashSet<>(); // 用于去重已考虑的块

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                Set<Pair<Integer, Integer>> currentBlock = board.getBlock(i, j);
                // 只有大小大于1的块才能被点击消除
                if (currentBlock != null && currentBlock.size() > 1 && !seenBlocks.contains(currentBlock)) {
                    // 将该块的任意一个位置作为代表性移动
                    moves.add(currentBlock.iterator().next()); 
                    seenBlocks.add(currentBlock);
                }
            }
        }
        // 按照列进行排序，保持一致性，但对算法正确性非必需
        moves.sort((o1, o2) -> {
            int cmpCol = Integer.compare(o1.getSecond(), o2.getSecond());
            if (cmpCol != 0) return cmpCol;
            return Integer.compare(o1.getFirst(), o2.getFirst()); // 列相同则按行排序
        });
        return moves;
    }

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

    // ... getSolution() 方法 ...
}

 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 

@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 (board.hasSingleton()) { // 新增的剪枝条件：如果只剩下1x1的块，此路径无解
        return false; 
    } 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;
}