我为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;

/**
 * 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;
    }

}

关注函数getMoves和backtracking。这段代码实际上找到了测试用例的解，但是，与我的一个同事相比，它扩展了比所需更多的节点。

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个