var AX=new Array('A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X');//les noms des véhicules
function newjeu(s)
{//construit un jeu 6x6
var je=new Array();
if(s instanceof Array)
{
for(var y=0;y<6;y++)
{
je[y]=new Array();
for(var x=0;x<6;x++)je[y][x]=s[y][x];
}
}
else//string
{
var c=0;
for(var y=0;y<6;y++)
{
je[y]=new Array();
for(var x=0;x<6;x++)je[y][x]=s.charAt(c++);
}
}
return je;
}
function compare(je,jj)//compare 2 jeux, true si identiques
{
for(var y=0;y<6;y++)for(var x=0;x<6;x++)if(je[y][x]!=jj[y][x])return false;
return true;
}
function ecrit(je)
{//on "écrit" le jeu à l'écran
for(var y=0;y<6;y++)
{
for(var x=0;x<6;x++)document.write(je[y][x]);
document.write("<br ></6>");
}
}
function goal(je)//la voiture XX peut-elle sortir par la droite ?
{
for(var x=5;x>0;x--)
{
if(je[2][x]=='X')return true;
if(je[2][x]!='.')return false;
}
return false;
}
function mouveg(je,c,x,y,len)
{//retourne le nombre de mouvement à gauche
var g=0;
for(var n=x-1;n>=0;n--)if(je[y][n]=='.')g++;else return g;
return g;
}
function mouved(je,c,x,y,len)
{//retourne le nombre de mouvement à droite
var d=0;
for(var n=x+len;n<6;n++)if(je[y][n]=='.')d++;else return d;
return d;
}
function mouveh(je,c,x,y,len)
{//retourne le nombre de mouvement en haut
var h=0;
for(var n=y-1;n>=0;n--)if(je[n][x]=='.')h++;else return h;
return h;
}
function mouveb(je,c,x,y,len)
{//retourne le nombre de mouvement en bas
var b=0;
for(var n=y+len;n<6;n++)if(je[n][x]=='.')b++;else return b;
return b;
}
function bougeH(je,c,x,y,len,m)
{//bouge un "véhicule" de m places à l'horizontal
for(var n=0;n<len;n++)je[y][x+n]='.';
for(var n=0;n<len;n++)je[y][x+n+m]=c;
}
function bougeV(je,c,x,y,len,m)
{//bouge un "véhicule" de m places en vertical
for(var n=0;n<len;n++)je[y+n][x]='.';
for(var n=0;n<len;n++)je[y+n+m][x]=c;
}
var ici=null;//le jeu de base (au début), un objet srush
function srush(s)
{
this.io=newjeu(s);//le jeu
this.txt="";//le mouvement
this.niveau=0;//profondeur de recherche
this.parent=null;//le jeu parent dont celui-ci est issu
this.frere=null;//toute les possibilités de mouvements (les fils)
this.print=function()
{//on écrit le jeu "à l'écran"
ecrit(this.io);
document.write("------ "+this.niveau);
if(this!=ici)//si ce n'est pas le jeu de début
{
ici.txt=this.txt+" "+ici.txt;//on cumule les mouvements
document.write(" "+this.txt+"<br ></6>");
this.parent.print();
}
else
{
document.write("<br />");
document.write(this.txt+"<br />");
}
}
this.deja=function(la)
{
if(compare(this.io,la))return true;//cette position est déjà analysée
return (this.frere!=null)&&this.frere.deja(la);//on essaye toutes les positions déjà répertoriées
}
this.test=function(niv)//on "teste" le niveau
{
if(this.run(niv))return true;//solution trouvée
return (this.frere!=null)&&this.frere.test(niv);//pour tous les "freres"
}
this.getFrere=function()
{
return this.frere==null?this:this.frere.getFrere();
}
this.addFrere=function(dummy,t)
{
if(ici.deja(dummy.io)==false)
{
this.getFrere().frere=dummy;
dummy.parent=this;
dummy.niveau=this.niveau+1;
dummy.txt=t;
}
if(goal(dummy.io)){dummy.print();return true;}
return false;
}
this.run=function(niv)
{
if(goal(this.io)){print();return true;}//au cas ou le niveau 0 est déjà résolu
if(niv!=this.niveau)return false;//pour chaque niveau de profondeur de recherche uniquement
for(var i=0;i<AX.length;i++)//on essaye tout les mouvements pour chaque "véhicule"
{
var c=AX[i];
for(var y=0;y<6;y++)//pour toutes les colonnes
{
for(var x=0;x<6;x++)//pour toute la ligne
{
if(this.io[y][x]==c)//on trouve un véhicule
{
var len;//longueur du véhicule
if((x<5)&&(this.io[y][x+1]==c))
{//H
if((x<4)&&(this.io[y][x+2]==c))len=3;else len=2;
for(var n=mouveg(this.io,c,x,y,len);n>0;n--)
{//left
var dummy=new srush(this.io);
bougeH(dummy.io,c,x,y,len,-n);
if(this.addFrere(dummy,c+"g"+n))return true;
}
for(var n=mouved(this.io,c,x,y,len);n>0;n--)
{//right
var dummy=new srush(this.io);
bougeH(dummy.io,c,x,y,len,n);
if(this.addFrere(dummy,c+"d"+n))return true;
}
}
else if((y<5)&&(this.io[y+1][x]==c))
{//V
if((y<4)&&(this.io[y+2][x]==c))len=3;else len=2;
for(var n=mouveh(this.io,c,x,y,len);n>0;n--)
{//up
var dummy=new srush(this.io);
bougeV(dummy.io,c,x,y,len,-n);
if(this.addFrere(dummy,c+"h"+n))return true;
}
for(var n=mouveb(this.io,c,x,y,len);n>0;n--)
{//down
var dummy=new srush(this.io);
bougeV(dummy.io,c,x,y,len,n);
if(this.addFrere(dummy,c+"b"+n))return true;
}
}//else erreur
x=y=6;//véhicule suivant
}
}
}
}
return false;
}
this.resoud=function()
{
for(var 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";
document.write(ici.txt+" pour ce tableau");
return false;
}
}
/**/
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.P"+
"..FEGG"+
"HHFII.");
/**/
ici.resoud();
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.