Clickomania游戏回溯算法的性能优化与实现

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;

public class ClickomaniaBacktracking extends Backtracking {
    private ClickomaniaPuzzle clickomania;
    private List<Pair<Integer, Integer>> sol;

    public ClickomaniaBacktracking() {
        super();
        clickomania = null;
        sol = null;
    }

    public ClickomaniaBacktracking (ClickomaniaPuzzle clickomania) {
        this();
        this.clickomania = clickomania.clone();
    }

    // ... 其他辅助方法如 getPuzzle, setPuzzle, getName, initialState ...

    @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;
    }

    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>>();

        // 遍历棋盘，寻找可点击的方块组
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 只有大小大于1的方块组才可点击
                if (board.getBlock(j, i).size() > 1) {
                    // 检查当前移动是否与已添加的移动等价（即属于同一个方块组）
                    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)); // 添加非等价移动
                }
            }
        }

        // 按列排序移动，可能有助于确定性或特定优化
        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>>());
    }

    public List<Pair<Integer, Integer>> getSolution() {
        return sol;
    }
}

@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 (board.hasSingleton()) { // 新增的剪枝条件：如果棋盘包含1x1的孤立方块，则此路径无解
        return false; // 立即返回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;
}