Résolution du jeu rush hour parfois appelé unblock
Description
Résolution du jeu Rush Hour
Construction d'un arbre avec niveau de profondeur de recherche
On essaye tous les mouvements possibles à chaque niveau de profondeur
Le jeu est résolu en 50 "coups" ou moins
Construction d'un arbre avec niveau de profondeur de recherche
On essaye tous les mouvements possibles à chaque niveau de profondeur
Le jeu est résolu en 50 "coups" ou moins
Source / Exemple :
#include <cstdio>
#include <string.h>
class vehicle
{
public:
char nom;//le "nom" du véhicule
bool V;//Vertical ou Horizontal
char x;//la colonne ou va rester le véhicule Vertical
char y;//la ligne ou va rester le véhicule Horizontal
char len;//la longueur du véhicule
vehicle(char name,bool Ve,char xx,char yy,char lon):nom(name),V(Ve),x(xx),y(yy),len(lon){}
};
class jeu
{
public:
char je[6][6];//le jeu sous forme d'un tableau de char
jeu(char*s)//constructeur avec des "véhicules" de A à X et des case vides de '.'
{
//char c=0;
memcpy(&je[0][0],s,36);//for(char y=0;y<6;y++)for(char x=0;x<6;x++)je[y][x]=s[c++];
}
jeu(jeu*jj)//constructeur copie
{
memcpy(&je[0][0],&jj->je[0][0],36);//for(char y=0;y<6;y++)for(char x=0;x<6;x++)je[y][x]=jj->je[y][x];
}
bool compare(jeu*jj)
{
return memcmp(&je[0][0],&jj->je[0][0],36)==0;//for(char y=0;y<6;y++)for(char x=0;x<6;x++)if(je[y][x]!=jj->je[y][x])return false;
//return true;
}
void print()
{//on "écrit" le jeu à l'écran
for(char y=0;y<6;y++)
{
for(char x=0;x<6;x++)printf("%c",je[y][x]);
printf("\n");
}
}
bool goal()//la voiture XX peut-elle sortir par la droite ?
{
for(char x=5;x>0;x--)
{
if(je[2][x]=='X')return true;
if(je[2][x]!='.')return false;
}
return false;
}
char getx(char c,char y)
{
for(char n=0;n<6;n++)if(je[y][n]==c)return n;
}
char gety(char c,char x)
{
for(char n=0;n<6;n++)if(je[n][x]==c)return n;
}
char mouveg(char c,char x,char y,char len)
{//retourne le nombre de mouvement à gauche
char g=0;
for(char n=x-1;n>=0;n--)if(je[y][n]=='.')g++;else return g;
return g;
}
char mouved(char c,char x,char y,char len)
{//retourne le nombre de mouvement à droite
char d=0;
for(char n=x+len;n<6;n++)if(je[y][n]=='.')d++;else return d;
return d;
}
char mouveh(char c,char x,char y,char len)
{//retourne le nombre de mouvement en haut
char h=0;
for(char n=y-1;n>=0;n--)if(je[n][x]=='.')h++;else return h;
return h;
}
char mouveb(char c,char x,char y,char len)
{//retourne le nombre de mouvement en bas
char b=0;
for(char n=y+len;n<6;n++)if(je[n][x]=='.')b++;else return b;
return b;
}
void bougeH(char c,char x,char y,char len,char m)
{//bouge un "véhicule" de m places à l'horizontal
for(char n=0;n<len;n++)je[y][x+n]='.';
for(char n=0;n<len;n++)je[y][x+n+m]=c;
}
void bougeV(char c,char x,char y,char len,char m)
{//bouge un "véhicule" de m places en vertical
for(char n=0;n<len;n++)je[y+n][x]='.';
for(char n=0;n<len;n++)je[y+n+m][x]=c;
}
};
class srush;//provisoirement pour la variable qui suit
srush*ici;//le jeu de base (au début)
char icitxt[400];//le texte de toute la solution
char ddd[400];//buffer intermediaire
vehicle*vehicles[24];//tous les véhicules du jeu
char nbre=0;//nombre de véhicules
long nbrposition=0;
class srush
{
public:
jeu*io;//le jeu
char txt[4];//le mouvement
char niveau;//profondeur de recherche
srush*parent;//le jeu parent dont celui-ci est issu
srush*frere;//toute les possibilités de mouvements (les fils)
srush(char*s):parent(0),frere(0),niveau(0)//construction du jeu avec une String (voir la class jeu plus bas) et mise en place des "véhicules"
{
io=new jeu(s);
nbre=0;
for(char c='A';c<='X';c++)//on essaye tous les "véhicules" possibles
for(char y=0;y<6;y++)//pour toutes les lignes
for(char x=0;x<6;x++)//pour toute la ligne
if(io->je[y][x]==c)//on trouve un véhicule
{
if((x<5)&&(io->je[y][x+1]==c))
{//H
vehicles[nbre++]=new vehicle(c,false,x,y,(x<4)&&(io->je[y][x+2]==c)?3:2);
}
else if((y<5)&&(io->je[y+1][x]==c))
{//V
vehicles[nbre++]=new vehicle(c,true,x,y,(y<4)&&(io->je[y+2][x]==c)?3:2);
}//else erreur
x=y=6;//véhicule suivant
}
}
srush(jeu*s):frere(0)//construction du jeu avec un jeu identique
{
io=new jeu(s);
txt[3]=0;
}
~srush()
{
if(ici==this)for(char n=0;n<nbre;n++)delete vehicles[n];
if(io)delete io;
if(frere)delete frere;
}
void print()
{//on écrit le jeu "à l'écran"
io->print();
printf("------ %u",niveau);
if(this!=ici)//si ce n'est pas le jeu de début
{
sprintf(ddd,"%s %s",txt,icitxt);
sprintf(icitxt,"%s",ddd);//on cumule les mouvements
printf(" %s\n",txt);
parent->print();
}
else printf("\n%s\nNombre de positions : %lu",icitxt,nbrposition);
}
bool deja(jeu*la)
{
if(la->compare(io))return true;//cette position est déjà analysée
return frere&&frere->deja(la);//on essaye toutes les positions déjà répertoriées
}
bool test(char niv)//on "teste" le niveau
{
if(run(niv))return true;//solution trouvée
return frere&&frere->test(niv);//pour tous les "frere"
}
srush*getFrere()
{
return frere?frere->getFrere():this;
}
bool addFrere(srush*dummy,char c,char t,char n)
{
nbrposition++;
// try{
if(ici->deja(dummy->io))delete dummy;
else
{
getFrere()->frere=dummy;
dummy->parent=this;
dummy->niveau=niveau+1;
dummy->txt[0]=c;
dummy->txt[1]=t;
dummy->txt[2]=n+'0';
if(dummy->io->goal()){dummy->print();return true;}
}
// }catch(...){}
return false;
}
bool run(char niv)
{
if(niv!=niveau)return false;//pour chaque niveau de profondeur de recherche uniquement
for(char nb=0;nb<nbre;nb++)//recherche de mouvements pour tous les véhicules
{
char c=vehicles[nb]->nom;
char len=vehicles[nb]->len;
if(vehicles[nb]->V)
{//V
char x=vehicles[nb]->x;
char y=io->gety(c,x);
for(char 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(char 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
{//H
char y=vehicles[nb]->y;
char x=io->getx(c,y);
for(char 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(char 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;
}
}
}
return false;
}
bool resoud()
{
for(char n=0;n<50;n++)//à priori, il n'y a pas plus de 50 mouvements
if(ici->test(n))
return true;
printf("Pas de solution pour ce tableau");
return false;
}
};
int main(int argc,char**argv)
{
icitxt[0]=0;
/** /
char msg[]="OAA.B.OCD.BPOCDXXPQQQE.P..FEGGHHFII.";
/** /
char msg[]=
"OAA.B."
"OCD.BP"
"OCDXXP" //la voiture XX doit sortir par la droite
"QQQE.."
"..FEGG"
"HHFII.";
/**/
char msg[]=
"AAABCL"
"IDDBCL"
"I.XXCL"
"EEJ..."
".KJ.FF"
".KGGHH";
/**/
printf("Veuillez attendre une trentaine de secondes\n");
if((argc==2)&&(strlen(argv[1])==36))
{
printf("Un argument :\n%s\n\n",argv[1]);
ici=new srush(argv[1]);
}
else
{
printf("%s\n\n",msg);
ici=new srush(msg);
}
ici->resoud();
delete ici;
return 0;
}
Codes Sources
A voir également
- Résolution du jeu rush hour parfois appelé unblock
- Generateur de nom de jeu ✓ - Forum Flash
- Grp - groupe de résolution de problèmes - Forum PHP
- Jeu solitaire carte - Forum C / C++ / C++.NET
- Overload resolution failed - Forum VB.NET
- Créer jeu tetris - Forum Visual Basic 6
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.