import java.util.*;

public class PacmanAStar implements Pacman {

    Stack<Position> plan;

    public Position chooseAction(PacmanState state) {
        if (plan != null){
            return plan.pop();
        }
        HashSet<PacmanState> visited = new HashSet<>();
        //...
        plan = new Stack<>();
        while(previousState.containsKey(currentState)){
            plan.add(currentState.findPacman());
            currentState = previousState.get(currentState);
        }
        return plan.pop();
    }

    //...

}