Résolution du jeu rush hour

Soyez le premier à donner votre avis sur cette source.

Vue 5 812 fois - Téléchargée 1 111 fois

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

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;
	}
}

Codes Sources

A voir également

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.