NoSuchElementException в решателе 8Puzzle
Я пытаюсь сделать программу на Java, которая дает мне решение проблемы 8puzzle
Процедура решения выглядит следующим образом:
Сначала я создаю начальный узел, который содержит начальную сетку (начальное состояние).
Я поставил узел в очередь
Я проверяю, является ли узел целью, поэтому я использую стек для сохранения пути решения (от узла до исходного корня)
иначе я добавлю его преемников (который представляет возможную перестановку 0) в очередь, и я переделываю тест.
Это код: Класс 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);}
}
}
Класс 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");
}
}
}
}
Результат примерно такой:
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)
2 ответа
Из вашей трассировки стека видно, что LinkedList за permut Очередь пуста. То есть, permut пустой. Смотря на Noued.successeur, Мы видим, что permut исходит от taquin8.Test_permut(), И глядя на Taquin8.Test_permutмы видим, что default case возвращает пустую очередь. Итак, вам нужно выяснить, почему taquin8.Test_permut вводит регистр по умолчанию. Подсказка: g находится вне диапазона [0:8].
Я рекомендую запустить ваш код через отладчик или, по крайней мере, добавить несколько операторов print ln.
Хорошо, я решил проблему прецедента.
Но теперь у меня есть "бесконечный цикл" (класс Taquin8), он выглядит правильно со мной (со стороны Алго), я не знаю, в чем проблема!
Класс 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);}
}
}
Класс 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();
}
}
}