Попытка реализовать задачу 8 головоломок в Java с использованием BFS - Не искать целое дерево

Question

Я пытаюсь сделать алгоритм поиска в ширину для проблемы 8 головоломки в Java. Я посмотрел на реализации и думаю, что у меня есть все необходимые компоненты, но по какой-то причине узлы не проходят глубину 2 дерева поиска. Любая помощь будет оценена

У меня есть два класса: PuzzleSolver.java и State.java

State.java находится в нижней части прокрутки

public class PuzzleSolver {
                Set<String> explored = new HashSet<String>();
                Queue<State> frontier = new LinkedList<>();
                String goal_map = "123456780";

                int nodesExpanded = 0;

                int SearchDepth = 0;
                int FrontierSize = 0;
public PuzzleSolver(ArrayList<Integer> start_state)
{

    State current_node = new State(start_state, null, 0, 0);
    frontier.add(current_node);

    while(frontier.size() > 0)
    {
        current_node = frontier.poll();
        explored.add(current_node.map);
        if(goalTest(current_node))
        {
            SearchDepth = current_node.depth;
            break;

        }


        ArrayList<State> neighbors = expand(current_node);

        for(int i = 0; i < neighbors.size(); i++)
        {
            if(goalTest(neighbors.get(i)))
            {
                frontier.add(neighbors.get(i));
                explored.add(neighbors.get(i).map);


            }

            if(!explored.contains(neighbors.get(i).map) && !frontier.contains(neighbors.get(i)))
            {
                frontier.add(neighbors.get(i));
                explored.add(neighbors.get(i).map);


                if(neighbors.get(i).depth > SearchDepth)
                {
                    SearchDepth ++;
                }
            }
        }


        if(frontier.size() > FrontierSize)
        {
            FrontierSize = frontier.size();
        }

    }

}


private boolean goalTest(State node) {
    // TODO Auto-generated method stub
    boolean rv = false;
    ArrayList<Integer> goal = new ArrayList<Integer>();
    goal.add(1);
    goal.add(2);
    goal.add(3);
    goal.add(4);
    goal.add(5);
    goal.add(6);
    goal.add(7);
    goal.add(8);
    goal.add(0);
    //1 2 3
    //4 5 6
    //7 8 0
    if(goal.equals(node.state))
    {
        rv = true;
    }
    return rv;
}


public int getNodesExpanded(){
    return nodesExpanded;
}

public Set<String> getNodePath(){
    return explored;
}



private ArrayList<State> expand(State node) {
    // TODO Auto-generated method stub
    nodesExpanded ++;
    ArrayList<State> successors = new ArrayList<State>();
    successors.add(new State(move(node.state, 1), node, node.depth+1, node.cost+1));
    successors.add(new State(move(node.state, 2), node, node.depth+1, node.cost+1));
    successors.add(new State(move(node.state, 3), node, node.depth+1, node.cost+1));
    successors.add(new State(move(node.state, 4), node, node.depth+1, node.cost+1));

    return successors;
}




private ArrayList<Integer> move(ArrayList<Integer> state, int position) {
    // TODO Auto-generated method stub
    ArrayList<Integer> rv = new ArrayList<Integer>(); 
    ArrayList<Integer> lastrow = new ArrayList<Integer>();
    lastrow.add(8);
    lastrow.add(7);
    lastrow.add(6);
    ArrayList<Integer> firstrow = new ArrayList<Integer>();
    firstrow.add(0);
    firstrow.add(1);
    firstrow.add(2);
    int index = state.indexOf(0);

    //UP
    if(position == 1){
        //if not in first row
        if(firstrow.contains(index))
        {
            rv = null;
        }
        else
        {
            int temp = state.get(index - 3);
            state.set(index - 3, state.get(index));
            state.set(index, temp);
            rv = state;
        }
    }

    //DOWN
    if(position == 2)
    {
        if(lastrow.contains(index))
        {
            rv = null;
        }
        else
        {
            int temp = state.get(index + 3);
            state.set(index + 3, state.get(index));
            state.set(index, temp);
            rv = state;
        }
    }

    //Left
    if(position == 3)
    {
        if(0 == index%3)
        {
            rv = null;
        }
        else
        {
            int temp = state.get(index - 1);
            state.set(index - 1, state.get(index));
            state.set(index, temp);
            rv = state;
        }

    }

    //Right
    if(position == 4)
    {
        if(2 == index%3)
        {
            rv = null;
        }
        else
        {
            int temp = state.get(index + 1);
            state.set(index + 1, state.get(index));
            state.set(index, temp);
            rv = state;
        }
    }
    return rv; 
}


public static void main(String[] args)
{
    ArrayList<Integer> sample_input = new ArrayList<Integer>();
    sample_input.add(1);
    sample_input.add(4);
    sample_input.add(2);
    sample_input.add(3);
    sample_input.add(0);
    sample_input.add(5);
    sample_input.add(6);
    sample_input.add(7);
    sample_input.add(8);

    //1 4 2
    //3 0 5 
    //6 7 8
    PuzzleSolver solve = new PuzzleSolver(sample_input);
    int num_nodes = solve.getNodesExpanded();
    Set<String> nodes = solve.getNodePath();

    System.out.println(num_nodes);
    System.out.println(nodes);
}}







public class State {
                ArrayList<Integer> state;
                State parent;
                String map;
                int depth;
                int cost;
public State(ArrayList<Integer> state, State parent, int depth, int cost) {
    // TODO Auto-generated constructor stub
    this.state = state;
    this.map = "";
    this.parent = parent;
    if(state != null){
        for(int i = 0; i < state.size(); i++)
        {
            this.map += state.get(i).toString();
        }
    }
    this.depth = depth;
    this.cost = cost;
}

}

С моего основного () вызова:

Мой входной сигнал [1, 4, 2, 3, 0, 5, 6, 7, 8] и мой выходной сигнал: Расширенные узлы: 3 узла: [102345678, 142035678, 142305678]