Breadth-First Search Algorithm JAVA 8-puzzle

Question

Im trying to implement the Breadth-First algorithm for 8 puzzle game. I know that it is not a new case and theres a bunch of solutions on web, but I want to make it on my way of thinking.

This code already finds the node result, which is

123
456
780

But it takes 350,000 steps to do it!

Any thoughts would be appreciated! =)

    //This method receives a Collection of `Nodo` objects, each one will be checked and compare with the finalGoal

     public void percorreNodos(Collection<Nodo> nodosBase)
            {
                //In this class a have an array that has all the IDs os nodes that already has been checked
                //The ID of a Node, is the representation: 123456780, 354126870 , etc..
                System.out.println("idsPercorrido.size() = " + idsPercorridos.size());
                //Check if the collection nodosBase contains the finalGoal
                Iterator<Nodo> iterator =  nodosBase.iterator();
                while( iterator.hasNext() )
                {
                    Nodo nodoBase = (Nodo) iterator.next();
                    //If this current node has already been checked, we dont have to check it again
                    idsPercorridos.add( nodoBase.getId() );
                            //Just print the node (sysout)
                    nodoBase.print();
                    contPassos++;
                    System.out.println( "\n" + contPassos + " STEPS(number of nodes checked)..." );
                    //Check if this node is the final goal
                    if( nodoBase.isObjetivoFinal() )
                    {
                                    //set the variable indicating that the result has been found
                        encontrouObjetivo = true;
                        System.out.println( "Resultado alcancado EM " + contPassos + " PASSOS..." );
                        nodoBase.print();
                        break;
                    }
                }

                // Now that we know that no one Node of nosoBase collection is the final goal, we are going to generate the next children to be checked, and call this function recursively 
                //Just confirm that we didnt find the goal 
                if(encontrouObjetivo == false)
                {
                            //Creates the next frontier
                    Collection<Nodo> novaFronteira = new HashSet<Nodo>();

                    for(Nodo nodoPai : nodosBase)
                    {
                                    //Generate each Node its childrens and add to a collection called "novaFronteira"
                        Collection<Nodo> filhos = nodoPai.gerarFilhos();
                        for(Nodo filho : filhos)
                        {
//idsPercorridos is a collection<String> which contains all the nodes ids that we checked, we dont want to check a node more than one time !
                            if( idsPercorridos.contains( filho.getId() ) == false )
                            {
                                novaFronteira.add( filho );

                            }
                        }
                    }
                    this.percorreNodos( novaFronteira );
                }

            }

Answer 1

You could make sure you don't add duplicate elements to novaFronteira.

There's nothing preventing this code:

for(Nodo nodoPai : nodosBase)
{
    Collection<Nodo> filhos = nodoPai.gerarFilhos();
    for(Nodo filho : filhos)
    {
        if( idsPercorridos.contains( filho.getId() ) == false )
        {
            novaFronteira.add( filho );
        }
    }
}

From adding many duplicate nodes to novaFronteira.

If you were to add to idsPercorridos inside the if-statement, that would prevent this from happening, and result in less steps, although, depending on exactly what your data and data structures looks like, the added running time of this call may actually make it take longer than it did originally.

---

If the problem is running time, you should make sure that idsPercorridos is a TreeSet or HashSet, as these allow for efficient contains calls, as opposed to ArrayList or LinkedList, which don't.

---

If this doesn't help, you could try using the A* algorithm instead, which involves adding a heuristic function to each node, which is the distance to the target - this allows us to explore the nodes closer to the target first, often resulting in less steps to get there.

A good heuristic function might be the sum of Manhattan distances between each tile and its target location.

Note that this would involve quite a few changes to your current code.

Answer 2

According to Wikipedia there are 9!/2 = 181440 possible solvable combinations to this puzzle. If you check each node for each of these combinations (which you don't, but it makes the calculation easier), it makes about (9!/2) * 9 = 1,632,960 steps. Therefore, there I don't see an issue if it takes your algorithm 350,000 steps because a computer can do those steps really fast.