TechQA.

NoSuchElementException in 8Puzzle solver

175 views Asked by At

I'm trying to make a Java program that gives me the solution of the 8puzzle problem

The solution procedure as the following:

-First I create an initial node that contains the initial grid (initial state)

  • I put the node in Queue

  • I test if the node is a goal so I use the stack to save the solution road(from the node to the initial root)

else I will add his successors (which represents the possible permutation of 0) in the Queue and I redo the test.

This is the code: Class Noued

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;


public class Noued {
int grille[]=new int[9];
int niveau;

Noued suiv1=null;
Noued suiv2=null;
Noued suiv3=null;
Noued suiv4=null;
Noued pred=null;


 static void successeur(Noued r)
{Queue<Integer> permut;
Integer elt;

    permut=taquin8.Test_permut(taquin8.zero(r.grille));

    if(permut.element()!=null){
        elt=permut.remove();
        r.suiv1=new Noued();
        r.suiv1.pred=r;
        for(int i=0;i<9;i++){r.suiv1.grille[i]=r.grille[i];}
        r.suiv1.niveau=r.niveau+1;
    r.suiv1.grille[taquin8.indice_ent(r.suiv1.grille,0)]=r.suiv1.grille[elt];
    r.suiv1.grille[elt]=0;

    if(permut.element()!=null){
        elt=permut.remove();
        r.suiv2=new Noued();
        r.suiv2.pred=r;
        for(int i=0;i<9;i++){r.suiv2.grille[i]=r.grille[i];}
        r.suiv2.niveau=r.niveau+1;
        r.suiv2.grille[taquin8.indice_ent(r.suiv2.grille,0)]=r.suiv2.grille[elt];
        r.suiv2.grille[elt]=0;


    }

    if(permut.element()!=null){
        elt=permut.remove();
        r.suiv3=new Noued();
        r.suiv3.pred=r;
        for(int i=0;i<9;i++){r.suiv3.grille[i]=r.grille[i];}
        r.suiv3.niveau=r.niveau+1;
        r.suiv3.grille[taquin8.indice_ent(r.suiv3.grille,0)]=r.suiv3.grille[elt];
        r.suiv3.grille[elt]=0;

        if(permut.element()!=null){
            elt=permut.remove();
            r.suiv4=new Noued();
            r.suiv4.pred=r;
            for(int i=0;i<9;i++){r.suiv4.grille[i]=r.grille[i];}
            r.suiv4.niveau=r.niveau+1;
            r.suiv4.grille[taquin8.indice_ent(r.suiv4.grille,0)]=r.suiv4.grille[elt];
            r.suiv4.grille[elt]=0;


        }       
    }
    }
}




//afficher un arbre
 static void affich_ab(Noued r)
{
if(r!=null){taquin8.affichertab(r.grille);}
if(r.suiv1!=null){System.out.println("\n***S1***"); affich_ab(r.suiv1);}
if(r.suiv2!=null){System.out.println("\n***S2***"); affich_ab(r.suiv2);}
if(r.suiv3!=null){System.out.println("\n***S3***"); affich_ab(r.suiv3);}
if(r.suiv4!=null){System.out.println("\n***S4***"); affich_ab(r.suiv4);}    

}

}

Class Taquin8:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;


public class taquin8 {
static Integer n1,n2;
static int start[] = {1,2,3,4,0,5,7,8,6};
static int goal[] = {1,2,3,4,5,6,7,8,0};


    //affichage d'une grille    
    static void affichertab(int t[])
    {
        for (int i=0;i<9;i++){ 
            if ((i%3)==2){System.out.println("["+t[i]+"]");}
            else {System.out.print("["+t[i]+"]");}
                                }

    }
    //rechercher l'indice d'un entier
    static int indice_ent(int t[],int x)
    {int ind = 10;
        for (int i=0;i<9;i++){ 
            if (t[i]==x) ind=i;
        }
        return ind;

    }

    //rechercher l'indice de zero
    static int zero(int t[])
    {int ind = 10;
        for (int i=0;i<9;i++){ 
            if (t[i]==0) ind=i;
        }
        return ind;

    }

    //egalité de tableau
        static boolean egal_tab(int t1[],int t2[])
        {int c=0;
            for (int i=0;i<9;i++){ 
                if (t1[i]!=t2[i]) c++;
            }
            if (c==0) {return true;}
            else return false;

        }

    //procedure pour faire la permutation de deux entier

    static  void permutaion(Integer n1, Integer n2)
    {Integer t;
    t=n1;
    taquin8.n1=n2;
    taquin8.n2=t;
    }



    //Test pour les possibilites de permutaion de 0
    static Queue<Integer> Test_permut(int g)
    {
        Queue<Integer> pp = new LinkedList<Integer>();


    switch (g)
    {
    case 0:
    {
        pp.add(1);
        pp.add(3);
    break;}

    case 1:
    {
        pp.add(0);
        pp.add(2);
        pp.add(4);
    break;}


    case 2:
    {
        pp.add(1);
        pp.add(5);
    break;}

    case 3:
    {
        pp.add(0);
        pp.add(4);
        pp.add(6);

    break;}

    case 4:
    {
        pp.add(1);
        pp.add(3);
        pp.add(5);
        pp.add(7);

    break;}

    case 5:
    {
        pp.add(2);
        pp.add(4);
        pp.add(8);

    break;
    }

    case 6:
    {
    pp.add(3);
    pp.add(7);
    break;}

    case 7:
    {
    pp.add(4);
    pp.add(6);
    pp.add(8);

    break;}

    case 8:
    {
    pp.add(5);
    pp.add(7);
    break;}
    default:{};            
    }

        return pp;
    }

static //largeur
    ArrayList<Noued> largeur(Noued r,ArrayList<Noued> f)
    {

        f=new ArrayList<Noued>();


    f.add(r);

if(!taquin8.egal_tab(r.grille,goal)){
    Noued.successeur(r);
if(r.suiv1!=null){f.add(r.suiv1);}
if(r.suiv2!=null){f.add(r.suiv2);}
if(r.suiv3!=null){f.add(r.suiv3);}
if(r.suiv4!=null){f.add(r.suiv4);}
}


return f;


    }







    //Programme Principal
    public static void main(String[] args) {
        Queue<Noued> queue = new LinkedList<Noued>();
         Stack<Noued> sol = new Stack<Noued>();

Noued rac=new Noued();
rac.grille=start;
rac.niveau=0;


queue.add(rac);

int but=0;

//XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXtest la file le but






while(but==0){  
    Noued   t=queue.element();
if(t.grille.equals(goal)){System.out.println("LE BUUUUUUUUUUUUt"); 
                                                Noued emp=t;
                                                while(emp.pred!=null){
                                                                        sol.push(emp);
                                                                        emp=emp.pred;
                                                                        }
                                                but=1;

                                                            }




else{Noued.successeur(t);
if(t.suiv1!=null){queue.add(rac.suiv1);}
if(t.suiv2!=null){queue.add(rac.suiv2);}
if(t.suiv3!=null){queue.add(rac.suiv3);}
if(t.suiv4!=null){queue.add(rac.suiv4);}
}
queue.remove(); 
}
//affichage de la frontiere
/*
if(queue!=null){
while(queue.size()!=0){
                    taquin8.affichertab(queue.remove().grille);
                    System.out.println("\n");
                    }

}

*/


if(sol!=null){
while(sol.size()!=0){
                    taquin8.affichertab(sol.pop().grille);
                    System.out.println("\n");
                    }

}           




    }
}

The result is something like:

Exception in thread "main" java.util.NoSuchElementException
    at java.util.LinkedList.getFirst(Unknown Source)
    at java.util.LinkedList.element(Unknown Source)
    at Noued.successeur(Noued.java:53)
    at taquin8.main(taquin8.java:208)
java sliding-tile-puzzle
Original Q&A
2

There are 2 answers

1
shoover On

From your stack trace, it appears that the LinkedList behind the permut Queue is empty. That is, permut is empty. Looking at Noued.successeur, we see that permut is coming from taquin8.Test_permut(). And looking at Taquin8.Test_permut, we see that the default case returns an empty Queue. So, you need to figure out why taquin8.Test_permut is entering the default case. Hint: g is outside the range [0:8].

I recommend running your code through a debugger, or at least adding some println statements.

1
user3101913 On

Ok, I solved the precedent problem.

But now I have An "infinite while loop" (Taquin8 class) it look correct form me (Algo side) I don't know where is the problem !

Class Noued :

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;


public class Noued {
int grille[]=new int[9];
int niveau;
int vis;
Noued suiv1=null;
Noued suiv2=null;
Noued suiv3=null;
Noued suiv4=null;
Noued pred=null;

static void successeur(Noued r)
{Queue<Integer> permut;
Integer elt;

    permut=taquin8.Test_permut(taquin8.zero(r.grille));
    if(permut!=null){

    if(!permut.isEmpty()){
        elt=permut.element();
        r.suiv1=new Noued();
        r.suiv1.pred=r;
        for(int i=0;i<9;i++){r.suiv1.grille[i]=r.grille[i];}
        r.suiv1.niveau=r.niveau+1;
    r.suiv1.grille[taquin8.indice_ent(r.suiv1.grille,0)]=r.suiv1.grille[elt];
    r.suiv1.grille[elt]=0;



    permut.remove();
    if(!permut.isEmpty()){
        elt=permut.element();
        r.suiv2=new Noued();
        r.suiv2.pred=r;
        for(int i=0;i<9;i++){r.suiv2.grille[i]=r.grille[i];}
        r.suiv2.niveau=r.niveau+1;
    r.suiv2.grille[taquin8.indice_ent(r.suiv2.grille,0)]=r.suiv2.grille[elt];
    r.suiv2.grille[elt]=0;



    permut.remove();
if(!permut.isEmpty()){
        elt=permut.element();
        r.suiv3=new Noued();
        r.suiv3.pred=r;
        for(int i=0;i<9;i++){r.suiv3.grille[i]=r.grille[i];}
        r.suiv3.niveau=r.niveau+1;
    r.suiv3.grille[taquin8.indice_ent(r.suiv3.grille,0)]=r.suiv3.grille[elt];
    r.suiv3.grille[elt]=0;


    permut.remove();
if(!permut.isEmpty()){
        elt=permut.element();
        r.suiv4=new Noued();
        r.suiv4.pred=r;
        for(int i=0;i<9;i++){r.suiv4.grille[i]=r.grille[i];}
        r.suiv4.niveau=r.niveau+1;
    r.suiv4.grille[taquin8.indice_ent(r.suiv4.grille,0)]=r.suiv4.grille[elt];
    r.suiv4.grille[elt]=0;



    permut.remove();

    }
    }
    }


    }




}else{System.out.println("\n PERMUT IS EMPTY");}
}
//afficher un arbre
 static void affich_ab(Noued r)
{
if(r!=null){taquin8.affichertab(r.grille);}
if(r.suiv1!=null){System.out.println("\n***S1***"); affich_ab(r.suiv1);}
if(r.suiv2!=null){System.out.println("\n***S2***"); affich_ab(r.suiv2);}
if(r.suiv3!=null){System.out.println("\n***S3***"); affich_ab(r.suiv3);}
if(r.suiv4!=null){System.out.println("\n***S4***"); affich_ab(r.suiv4);}    

}

}

Class Taquin8:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;


public class taquin8 {
static Integer n1,n2;
static int start[] = {1,2,3,4,5,6,7,0,8};
static int goal[] = {1,2,3,4,5,6,7,8,0};


    //affichage d'une grille    
    static void affichertab(int t[])
    {
        for (int i=0;i<9;i++){ 
            if ((i%3)==2){System.out.println("["+t[i]+"]");}
            else {System.out.print("["+t[i]+"]");}
                                }

    }
    //rechercher l'indice d'un entier
    static int indice_ent(int t[],int x)
    {int ind = 10;
        for (int i=0;i<9;i++){ 
            if (t[i]==x) ind=i;
        }
        return ind;

    }

    //rechercher l'indice de zero
    static int zero(int t[])
    {int ind = 10;
        for (int i=0;i<9;i++){ 
            if (t[i]==0) ind=i;
        }
        return ind;

    }

    //egalité de tableau
        static boolean egal_tab(int t1[],int t2[])
        {int c=0;
            for (int i=0;i<9;i++){ 
                if (t1[i]!=t2[i]) c++;
            }
            if (c==0) {return true;}
            else return false;

        }

    //procedure pour faire la permutation de deux entier

    static  void permutaion(Integer n1, Integer n2)
    {Integer t;
    t=n1;
    taquin8.n1=n2;
    taquin8.n2=t;
    }



    //Test pour les possibilites de permutaion de 0
    static Queue<Integer> Test_permut(int g)
    {
        Queue<Integer> pp = new LinkedList<Integer>();


    switch (g)
    {
    case 0:
    {
        pp.add(1);
        pp.add(3);
    break;}

    case 1:
    {
        pp.add(0);
        pp.add(2);
        pp.add(4);
    break;}


    case 2:
    {
        pp.add(1);
        pp.add(5);
    break;}

    case 3:
    {
        pp.add(0);
        pp.add(4);
        pp.add(6);

    break;}

    case 4:
    {
        pp.add(1);
        pp.add(3);
        pp.add(5);
        pp.add(7);

    break;}

    case 5:
    {
        pp.add(2);
        pp.add(4);
        pp.add(8);

    break;
    }

    case 6:
    {
    pp.add(3);
    pp.add(7);
    break;}

    case 7:
    {
    pp.add(4);
    pp.add(6);
    pp.add(8);

    break;}

    case 8:
    {
    pp.add(5);
    pp.add(7);
    break;}
    default:{};            
    }

        return pp;
    }

 //largeur







    //Programme Principal
    public static void main(String[] args) {
        Queue<Noued> queue = new LinkedList<Noued>();
         Stack<Noued> sol = new Stack<Noued>();

Noued rac=new Noued();
rac.grille=start;
rac.niveau=0;

int but=0;
queue.add(rac);

while((but!=1)&&(!queue.isEmpty())){
                                        Noued test=queue.element();
                                        System.out.println("\n---------");
                                        taquin8.affichertab(test.grille);

                                        if(test.grille.equals(goal)){
                                                                        System.out.println("GOAAAAAAL");
                                                                        but=1;
                                                                    }
                                        else{
                                                Noued.successeur(test);
                                                if(test.suiv1!=null){queue.add(test.suiv1);}
                                                if(test.suiv2!=null){queue.add(test.suiv2);}
                                                if(test.suiv3!=null){queue.add(test.suiv3);}
                                                if(test.suiv4!=null){queue.add(test.suiv4);}
                                            }

                                        queue.remove();
                                    }


    }
}

Related Questions in JAVA

Related Questions in SLIDING-TILE-PUZZLE

Popular Questions

Popular Tags

javascript python java c# php android html jquery c++ css ios sql mysql r reactjs node.js arrays c asp.net json python-3.x ruby-on-rails .net sql-server swift django angular objective-c pandas excel

Trending Questions