Algo de recherche de solution Myst 4, Pour Schlum et les autres

[SuperCed]

J'ai téléchargé hier la démo de Myst 4, et il y a un puzzle dans la pièce principale.

Il s'agit, je crois, de faire transformer tout un damier de 8*6 en rouge.
En fait, lorsque l'on clique sur une case, alors celle juste en haut change de couleur, celle du bas, celle de gauche et celle de droite aussi.

N'ayant pas trouvé la solution facilement, j'ai décidé d'essayer de faire un programme en C qui permet de faire la recherc à ma place. Le problème, c'est que mon algo est de complexité 48^N ou N est le nombre de clic sur une case.
Or, il parait évident qu'il faut au moins 12 clics pour y arriver, et mon algo peine déjà beaucoup à partir de N = 8.

Le mieux est de voir le problème directement dans Myst 4 pour mieux le comprendre. C'est dans une sorte de cheminé ou il y a une pierre précieuse rouge. Il faut se retourner et cliquer sur un bouton qui ferme une trappe et fait apparaitre le puzzle.

Je vais poster mon programme en C, et je voudrais savoir si quelqu'un a une idée pour optimiser ça. J'ai fait mon programme rapidement, et il y a certainement des meilleurs algos.

Par exemple, ne serait-il pas mieux de stocker les états rencontrés du puzzle (bien qu'il y en ait 2^48...). Ou peut-être réduire le nombre d'état par 4 en utilisant les symétries axiales? Si on stocke ainsi un état du puzzle, on pourrait ainsi comparer les nouveaux états et éliminer des branches de l'arbre de recherche.

Bon, je mets mon code (peut-être faux, je ne l'ai pas beaucoup testé non plus) :

CODE

#include <stdio.h>

#define COLS 6
#define VERBOSE 0

int recursiveSearch (unsigned char *tab, unsigned char level, unsigned char *solutionPath, unsigned char totalLevels, char verboseFlag);
int printTab(unsigned char *tab);
int testTab(unsigned char *tab);
int simulateTurn(unsigned char *tab, unsigned char x, unsigned char y);

int main (int argc, const char * argv[]) {
unsigned char levelMax;
unsigned char level;
unsigned char *solutionPath;
unsigned char myTab[COLS];
unsigned char test,i;
if (argc != 2) {
 printf("Bad argument number : ia deepLevel\n");
 return -1;
}
printf("IA is going to search a solution for you...\n");
levelMax = (unsigned char)atoi(argv[1]);
level = 1;
solutionPath = (unsigned char*)malloc(sizeof(unsigned char) * levelMax *2);
bzero(solutionPath, sizeof(unsigned char)*level*2);
bzero(myTab, sizeof(char)*COLS);
test = 0;
while ((!test) && (level<levelMax)) {
 test = recursiveSearch(myTab, level, solutionPath, level, VERBOSE);
 level++;
 printf("Level is : %d\n", level);
 bzero(solutionPath, sizeof(unsigned char)*level*2);
 bzero(myTab, sizeof(char)*COLS);
}
if (test) {
 printf("Solution :\n");
 for (i=0;i<levelMax-1;i++) {
  printf("(%d",*solutionPath);
  solutionPath++;
  printf(",%d),",*solutionPath);
  solutionPath++;
 }
 printf("\n\n");
}
return 0;
}

int printTab(unsigned char *tab) {
unsigned char i,j;
printf("\n####################");
for (i=0;i<COLS;i++) {
 printf("\n");
 for (j=0;j<sizeof(unsigned char)*8;j++) {
  if (tab[i] & (unsigned char)(0x1 << j)) {
   printf("#");
  } else {
   printf("O");
  }
 }
}
printf("####################\n");
return 0;
}

int testTab(unsigned char *tab) {
unsigned char i,j;
for (i=0;i<COLS;i++) {
 for (j=0;j<sizeof(unsigned char)*8;j++) {
  if (tab[i] | (unsigned char)(0x1 << j)) {
   return 0;
  }
 }
}
return 1;
}

int simulateTurn(unsigned char *tab, unsigned char x, unsigned char y) {
if (x>0) {
 tab[y] = tab[y] ^ (unsigned char)(0x1 << (x-1));
}
if (x<(COLS-1)) {
 tab[y] = tab[y] ^ (unsigned char)(0x1 << (x+1));
}
if (y>0) {
 tab[y-1] = tab[y-1] ^ (unsigned char)(0x1 << x);
}
if (y<(COLS-1)) {
 tab[y+1] = tab[y+1] ^ (unsigned char)(0x1 << x);
}
return 0;
}

int recursiveSearch (unsigned char *tab, unsigned char level, unsigned char *solutionPath, unsigned char totalLevels, char verboseFlag) {
unsigned char x,y;
unsigned char tabTemp[COLS];
if (verboseFlag) {
 printTab(tab);
}
if (testTab(tab)) {
 solutionPath[(totalLevels-level)*2] = x;
 solutionPath[(totalLevels-level)*2 +1] = y;
 return 1;
}
if (!level) {
 return 0;
}
for (x=0;x<(sizeof(unsigned char)*8);x++) {
 for (y=0;y<COLS;y++) {
  bcopy(tab, tabTemp, sizeof(unsigned char)*COLS);
  simulateTurn(tabTemp, x, y);
  if (recursiveSearch(tabTemp, level -1, solutionPath, level, verboseFlag)) {
   solutionPath[(totalLevels-level)*2] = x;
   solutionPath[(totalLevels-level)*2 +1] = y;
   return 1;
  }
 }
}
return 0;
}

[Philram]

Bonjour,
C'est bien de trouver des problèmes pratiques pour s'exercer au codage, mais même si tu arrives à remplir toutes les cases en rouge, c'est pas ça qui va actionner l'ascenseur.

La vérité est ailleurs

[SuperCed]

rahhh, zutr... Ben tant pis alors, je me disais que c'était plus dans le style de 7th Guest que de Myst. c'ets pas le genre de Myst de mettre un puzzle au millieu comme ça...

Mais ça ne remet pas en cause le programme...

[Benzebut]

rahhh, zutr... Ben tant pis alors, je me disais que c'était plus dans le style de 7th Guest que de Myst. c'ets pas le genre de Myst de mettre un puzzle au millieu comme ça...

Mais ça ne remet pas en cause le programme...

Non, bien sur, mais dans le jeu si on regarde attentivement les changements dans le puzzle, on remarque que chaque pression génére une réponse en croix, formée de 4 cases pleines ...
Un p'tit bout de code à modifier !

[SuperCed]

rahhh, zutr... Ben tant pis alors, je me disais que c'était plus dans le style de 7th Guest que de Myst. c'ets pas le genre de Myst de mettre un puzzle au millieu comme ça...

Mais ça ne remet pas en cause le programme...

Non, bien sur, mais dans le jeu si on regarde attentivement les changements dans le puzzle, on remarque que chaque pression génére une réponse en croix, formée de 4 cases pleines ...
Un p'tit bout de code à modifier !
[right][snapback]811221[/snapback][/right]

Ben c'est ce que j'ai fait dans mon code non?

[le grimpeur]

Je crois qu'il suffit de partir des angles, puis il y a un motif à répéter, et c'est bon...y'a ça dans Spyro sur Playstation et dans des vieux jeus macs

[schlum]

J'ai déjà programmé ce truc ... Si tu veux je te passe l'algo, mais le principe est simple
Il suffit de partir d'une ligne ou d'une colonne au bord (6 -> 2^6 = 64 possibilités), et pour chaque possibilité de compléter avec la ligne du dessus à chaque fois (ou la colonne d'à côté si on a pris une colonne) ... Si c'est possible à faire, une des possibilités complètera exactement la dernière ligne.
C'est donc en complexité n*m*2^min(n,m), soit pour 6*8, pas grand chose


[Edit] j'espère qu'on parle bien du même problème, le damier qu'il faut remplir et quand on touche une case, elle et ses 4 voisines (ou 3 pour un bord ou 2 pour un coin) changent d'état ...

[SuperCed]

J'ai déjà programmé ce truc ... Si tu veux je te passe l'algo, mais le principe est simple 
Il suffit de partir d'une ligne ou d'une colonne au bord (6 -> 2^6 = 64 possibilités), et pour chaque possibilité de compléter avec la ligne du dessus à chaque fois (ou la colonne d'à côté si on a pris une colonne) ... Si c'est possible à faire, une des possibilités complètera exactement la dernière ligne.
C'est donc en complexité n*m*2^min(n,m), soit pour 6*8, pas grand chose 


[Edit] j'espère qu'on parle bien du même problème, le damier qu'il faut remplir et quand on touche une case, elle et ses 4 voisines (ou 3 pour un bord ou 2 pour un coin) changent d'état ...
[right][snapback]812033[/snapback][/right]

Pas tout a fait car dans mon cas, la case du millieu ne change pas. ce qui est beaucoup plus difficile.
Mais bon, j'ai trouvé l'astuce de Myst sans trop de problème...
Par contre, ce topic était plus pour parler un peu optimisation combinatoire.

[schlum]

J'ai déjà programmé ce truc ... Si tu veux je te passe l'algo, mais le principe est simple 
Il suffit de partir d'une ligne ou d'une colonne au bord (6 -> 2^6 = 64 possibilités), et pour chaque possibilité de compléter avec la ligne du dessus à chaque fois (ou la colonne d'à côté si on a pris une colonne) ... Si c'est possible à faire, une des possibilités complètera exactement la dernière ligne.
C'est donc en complexité n*m*2^min(n,m), soit pour 6*8, pas grand chose 


[Edit] j'espère qu'on parle bien du même problème, le damier qu'il faut remplir et quand on touche une case, elle et ses 4 voisines (ou 3 pour un bord ou 2 pour un coin) changent d'état ...
[right][snapback]812033[/snapback][/right]

Pas tout a fait car dans mon cas, la case du millieu ne change pas. ce qui est beaucoup plus difficile.
Mais bon, j'ai trouvé l'astuce de Myst sans trop de problème...
Par contre, ce topic était plus pour parler un peu optimisation combinatoire.
[right][snapback]812071[/snapback][/right]

Qu'appelles-tu la case du millieu pour un damier 6*8 ? Et que veut dire "ne change pas" ?

[SuperCed]

Quand tu cliques sur une case, cette case ne change pas de couleur, ce sont les 4 cases autour qui changent de couleur.

Le mieux est de regarder Myst pour comprendre.

[schlum]

Quand tu cliques sur une case, cette case ne change pas de couleur, ce sont les 4 cases autour qui changent de couleur.

Le mieux est de regarder Myst pour comprendre.
[right][snapback]812653[/snapback][/right]

Ahh, ok ! Bah ça change pas grand chose
Il fait déjà remarquer que quand on appuie 2 fois sur la même touche, ça fait comme si on y avait pas appuyé (même si on réappuie à un autre moment) ; donc toutes les configurations possibles s'obtiennent en appuyant une et une seule fois sur un nombre de cases qui est un sous-ensemble de l'ensemble des cases. Ca réduit déjà ta complexité de 48^N à 48!/(48-N)!
Ensuite, on peut remarquer aussi que l'ordre dans lequel on appuie sur les cases ne compte pas pour le résultat ... Ca réduit considérablement encore la complexité.
Enfin, si le problème est de remplir toutes les cases, on peut remarquer que tout dépend du remplissage de la première ligne / colonne, car une fois celle-ci remplie, un algorithme simple donne le remplissage de la ligne / colonne immédiatement à côté (il faut combler les trous de la dite ligne / colonne ; on ne pourra le faire qu'à cet endroit, après on sera trop loin) ... C'est réussi si et seulement si en arrivant à la dernière ligne / colonne, le remplissage de l'avant-dernière la comble aussi complètement.
Il suffit donc de tester toutes les possibilités sur une seule ligne / colonne
On peut appliquer le même algorithme à n'importe quelle figure à atteindre