Résolution du jeu rush hour
Description
Ce programme java permet de résoudre une position du jeu appelé communément Rush Hour (parfois unblock)
C'est une sorte de puzzle
C'est une sorte de puzzle
Source / Exemple :
public class srush
{
static public srush ici;//le jeu de base (au début)
public jeu io;//le jeu
public String txt;//le mouvement
public int niveau;//profondeur de recherche
public srush parent;//le jeu parent dont celui-ci est issu
public srush frere;//toute les possibilités de mouvements (les fils)
public srush(String s)//construction du jeu avec une String (voir la class jeu plus bas)
{
io=new jeu(s);
parent=frere=null;
niveau=0;
txt="";
if(ici==null)ici=this;//le premier objet srush
}
public srush(jeu s)//construction du jeu avec un jeu identique
{
io=new jeu(s);
parent=frere=null;
niveau=0;
txt="";
if(ici==null)ici=this;
}
public void print()
{//on écrit le jeu "à l'écran"
io.print();
System.out.print("------ "+niveau);
if(this!=ici)//si ce n'est pas le jeu de début
{
ici.txt=txt+" "+ici.txt;//on cumule les mouvements
System.out.println(" "+txt);
parent.print();
}
else
{
System.out.println();
System.out.println(txt);
}
}
public boolean deja(jeu la)
{
if(la.compare(io))return true;//cette position est déjà analysée
return (frere!=null)&&frere.deja(la);//on essaye toutes les positions déjà répertoriées
}
public boolean test(int niv)//on "teste" le niveau
{
if(run(niv))return true;//solution trouvée
return (frere!=null)&&frere.test(niv);//pour tous les "frere"
}
public srush getFrere()
{
return frere==null?this:frere.getFrere();
}
public boolean addFrere(srush dummy,String t)
{
try
{
if(ici.deja(dummy.io)==false)
{
getFrere().frere=dummy;
dummy.parent=this;
dummy.niveau=niveau+1;
dummy.txt=t;
}
if(dummy.io.goal()){dummy.print();return true;}
}
catch(java.lang.StackOverflowError e){}
return false;
}
public boolean run(int niv)
{
if(io.goal()){print();return true;}//au cas ou le niveau 0 est déjà résolu
if(niv!=niveau)return false;//pour chaque niveau de profondeur de recherche uniquement
for(char c='A';c<='X';c++)//on essaye tout les mouvements pour chaque "véhicule"
{
for(int y=0;y<6;y++)//pour toutes les colonnes
{
for(int x=0;x<6;x++)//pour toute la ligne
{
if(io.je[y][x]==c)//on trouve un véhicule
{
int len;//longueur du véhicule
if((x<5)&&(io.je[y][x+1]==c))
{//H
if((x<4)&&(io.je[y][x+2]==c))len=3;else len=2;
for(int n=io.mouveg(c,x,y,len);n>0;n--)
{//left
srush dummy=new srush(io);
dummy.io.bougeH(c,x,y,len,-n);
if(addFrere(dummy,c+"g"+n))return true;
}
for(int n=io.mouved(c,x,y,len);n>0;n--)
{//right
srush dummy=new srush(io);
dummy.io.bougeH(c,x,y,len,n);
if(addFrere(dummy,c+"d"+n))return true;
}
}
else if((y<5)&&(io.je[y+1][x]==c))
{//V
if((y<4)&&(io.je[y+2][x]==c))len=3;else len=2;
for(int n=io.mouveh(c,x,y,len);n>0;n--)
{//up
srush dummy=new srush(io);
dummy.io.bougeV(c,x,y,len,-n);
if(addFrere(dummy,c+"h"+n))return true;
}
for(int n=io.mouveb(c,x,y,len);n>0;n--)
{//down
srush dummy=new srush(io);
dummy.io.bougeV(c,x,y,len,n);
if(addFrere(dummy,c+"b"+n))return true;
}
}//else erreur
x=y=6;//véhicule suivant
}
}
}
}
return false;
}
public boolean resoud()
{
for(int n=0;n<50;n++)//à priori, il n'y a pas plus de 50 mouvements
if(ici.test(n))
return true;
ici.txt="Pas de solution";
System.out.println(ici.txt+" pour ce tableau");
return false;
}
static public void main(String[] args)
{
/**/
ici=new srush("OAA.B.OCD.BPOCDXXPQQQE.P..FEGGHHFII.");
/** /
ici=new srush(
"OAA.B."+
"OCD.BP"+
"OCDXXP"+ //la voiture XX doit sortir par la droite
"QQQE.."+
"..FEGG"+
"HHFII.");
/**/
ici.resoud();
}
}
class jeu
{
char je[][];//le jeu sous forme d'un tableau de char
public jeu(String s)//constructeur avec des "véhicules" de A à X et des case vides de '.'
{
je=new char[6][6];
int c=0;
for(int y=0;y<6;y++)for(int x=0;x<6;x++)je[y][x]=s.charAt(c++);
}
public jeu(jeu jj)//constructeur copie
{
je=new char[6][6];
for(int y=0;y<6;y++)for(int x=0;x<6;x++)je[y][x]=jj.je[y][x];
}
public boolean compare(jeu jj)
{
for(int y=0;y<6;y++)for(int x=0;x<6;x++)if(je[y][x]!=jj.je[y][x])return false;
return true;
}
public void print()
{//on "écrit" le jeu à l'écran
for(int y=0;y<6;y++)
{
for(int x=0;x<6;x++)System.out.print(je[y][x]);
System.out.println();
}
}
public boolean goal()//la voiture XX peut-elle sortir par la droite ?
{
for(int x=5;x>0;x--)
{
if(je[2][x]=='X')return true;
if(je[2][x]!='.')return false;
}
return false;
}
public int mouveg(char c,int x,int y,int len)
{//retourne le nombre de mouvement à gauche
int g=0;
for(int n=x-1;n>=0;n--)if(je[y][n]=='.')g++;else return g;
return g;
}
public int mouved(char c,int x,int y,int len)
{//retourne le nombre de mouvement à droite
int d=0;
for(int n=x+len;n<6;n++)if(je[y][n]=='.')d++;else return d;
return d;
}
public int mouveh(char c,int x,int y,int len)
{//retourne le nombre de mouvement en haut
int h=0;
for(int n=y-1;n>=0;n--)if(je[n][x]=='.')h++;else return h;
return h;
}
public int mouveb(char c,int x,int y,int len)
{//retourne le nombre de mouvement en bas
int b=0;
for(int n=y+len;n<6;n++)if(je[n][x]=='.')b++;else return b;
return b;
}
public void bougeH(char c,int x,int y,int len,int m)
{//bouge un "véhicule" de m places à l'horizontal
for(int n=0;n<len;n++)je[y][x+n]='.';
for(int n=0;n<len;n++)je[y][x+n+m]=c;
}
public void bougeV(char c,int x,int y,int len,int m)
{//bouge un "véhicule" de m places en vertical
for(int n=0;n<len;n++)je[y+n][x]='.';
for(int n=0;n<len;n++)je[y+n+m][x]=c;
}
}
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.