Untitled

import java.util.*;

//A state is represented by an array of rods.
//Rods are represented by stacks of integers.
//Integers represent disks. Their values are disks sizes.
class State implements Cloneable
{
    public Stack<Integer>[] rods;
    public State parent = null;
    public String displayText = "START"; //The text shown by the toString() method.
    public  State(Stack<Integer>[] rods)
    {
        this.rods = rods;
    }

    @Override
    public String toString()
    {
        return displayText;
    }

    public ArrayList<State> GenerateStates()
    {
        ArrayList<State> states = new ArrayList<>();

        for (int fromIndex = 0; fromIndex < 3; fromIndex++)
        {
            if(rods[fromIndex].size() != 0)
            {
                for (int toIndex = 0; toIndex < 3; toIndex++)
                {
                    //Cannot put a disk on the same rod
                    if(toIndex == fromIndex) continue;

                    //Cannot put bigger disks over smaller ones
                    if(rods[toIndex].size() != 0 && rods[fromIndex].peek() > rods[toIndex].peek()) continue;
                    State newState = this.MakeNew();
                    newState.rods[toIndex].push(newState.rods[fromIndex].pop());
                    states.add(newState);
                    //Showing rods names as A, B, C
                    newState.displayText = "Move disk "+ newState.rods[toIndex].peek() +" from rod " + (char)(65 + fromIndex) + " to rod " + (char)(65 + toIndex);
                }
            }
        }
            return  states;
    }

    //Cloning current state
    private State MakeNew()
    {
        State newState =  new State(new Stack[]{
                (Stack) this.rods[0].clone(),
                (Stack) this.rods[1].clone(),
                (Stack) this.rods[2].clone()});
        newState.parent = this;
        return  newState;
    }

    //Comparing two states
    public boolean IsSameAs(State otherState)
    {
        for(int i = 0; i < rods.length; i++)
        {
            if(!rods[i].equals(otherState.rods[i])){
                return  false;
            }
        }
        return  true;
    }

    public boolean IsGoal()
    {
        if(rods[2].size() != 3) return  false;
        if(rods[2].pop() != 1) return false;
        if(rods[2].pop() != 2) return false;
        if(rods[2].pop() != 3) return false;
        return true;
    }
}

class mainClass
{
    //Removing all states that are already contained in Open or Closed
    private static ArrayList<State> FilterNewStates(ArrayList<State> newStates, Queue<State> open, ArrayList<State> closed)
    {
        ArrayList<State> filteredStates = new ArrayList<State>();
        for (State state: newStates)
        {
            if(open.contains(state) || closed.contains(state)) continue;
            filteredStates.add(state);
        }
        return  filteredStates;
    }

    private static State BFS(State start)
    {
        Queue<State> open = new LinkedList<State>();
        ArrayList<State> closed = new ArrayList<State>();
        open.add(start);

        while(!open.isEmpty())
        {
            State x = open.poll();
            if(x.IsGoal()) {
                return x;
            }
            else
            {
                ArrayList<State> newStates = x.GenerateStates();
                closed.add(x);
                newStates = FilterNewStates(newStates,open, closed);
                open.addAll(newStates);
            }
        }
        return null;
    }

    public static void main(String[] args)
    {
        Stack<State> path = new Stack<State>();

        //Creating the starting state
        Stack<Integer> rodA = new Stack<Integer>();
        rodA.push(3);
        rodA.push(2);
        rodA.push(1);
        State startState =  new State(new Stack[]{ rodA, new Stack<Integer>(), new Stack<Integer>() });


        State goal = BFS(startState);
        State state = goal;

        //Put states in stack in order to be shown in reversed order after that
        while (state != null)
        {
            path.add(state);
            state = state.parent;
        }

        //Display path
        while(!path.isEmpty())
        {
            System.out.println(path.pop());
        }

    }
}