Résolution du jeu rush hour parfois appelé unblock

Soyez le premier à donner votre avis sur cette source.

Vue 4 295 fois - Téléchargée 24 fois

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

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

Ajouter un commentaire

Commentaires

Commenter la réponse de Cmdu76

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.