我正在尝试制作一个可以解决 8puzzle 问题的 Java 程序
解决过程如下：
-首先我创建一个包含初始网格（初始状态）的初始节点
我将节点放入队列
我测试节点是否是目标，所以我使用堆栈来保存解决方案路径（从节点到初始根）
否则我将在队列中添加他的继任者（代表可能的 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)