Voici un programme qui calcule la solution du solitaire.
Exécuté sur un Pentium M cadencé à 1,4 GHz, il a tourné 1h30 et effectué 3 milliards de parties (2 943 463 868 pour être précis) avant de trouver la solution que voici :
Le programme commence avec la grille ci-dessous. La symétrie fait que le premier coup est forcement celui-là. Dans le programme, les directions de la figure de droite sont utilisées : 0 pour le Sud, 1 pour l'Ouest, 2 pour le Nord et 3 pour l'Est.
Le programme recherche systématiquement toutes les solutions. Il commence par jouer le premier coup qu'il trouve, puis si ce coup n'amène pas à la solution, il joue le suivant, et ainsi de suite...
Voici le programme :
#include <stdio.h>
struct coup // un coup est une case, une direction, et un plateau résultant
{
int ligne;
int colonne;
int direction;
int plateau[7][7];
};
// variables globales
long long int nb_parties=0;
int coup_courant, meilleure=1, coup_trouve[3], retour;
struct coup partie[32];
void coup_suivant (int retour) //renvoie le coup à jouer ou 255 si impossible
{
int i, j, trouve=0;
coup_trouve[0]=255;
if (retour) // on revient en arrière : il faut choisir le coup suivant par rapport au coup précédent
{
i=partie[coup_courant+1].ligne;
j=partie[coup_courant+1].colonne; // on regarde si le pion peut bouger ailleurs
if (j>1 && partie[coup_courant].plateau[i][j-1]==1 && partie[coup_courant].plateau[i][j-2]==0 && partie[coup_courant+1].direction<1 )
{
coup_trouve[0]=i; coup_trouve[1]=j; coup_trouve[2]=1; trouve=1;
}
else if (i>1 && partie[coup_courant].plateau[i-1][j]==1 && partie[coup_courant].plateau[i-2][j]==0 && partie[coup_courant+1].direction<2 )
{
coup_trouve[0]=i; coup_trouve[1]=j; coup_trouve[2]=2; trouve=1;
}
else if (j<5 && partie[coup_courant].plateau[i][j+1]==1 && partie[coup_courant].plateau[i][j+2]==0 && partie[coup_courant+1].direction<3 )
{
coup_trouve[0]=i; coup_trouve[1]=j; coup_trouve[2]=3; trouve=1;
}
if (!trouve && partie[coup_courant+1].colonne < 6) // on part du dernier pion jouer et on avance
{
for (i=partie[coup_courant+1].ligne; i<7 ; i++)
{
for (j=0; j<7; j++)
{
if (i==partie[coup_courant+1].ligne && j==0 ) j=partie[coup_courant+1].colonne+1;
if (partie[coup_courant].plateau[i][j] == 1)
{
if (i<5 && partie[coup_courant].plateau[i+1][j]==1 && partie[coup_courant].plateau[i+2][j]==0 )
{
coup_trouve[0]=i; coup_trouve[1]=j; coup_trouve[2]=0; trouve=1; break;
}
else if (j>1 && partie[coup_courant].plateau[i][j-1]==1 && partie[coup_courant].plateau[i][j-2]==0)
{
coup_trouve[0]=i; coup_trouve[1]=j; coup_trouve[2]=1; trouve=1; break;
}
else if (i>1 && partie[coup_courant].plateau[i-1][j]==1 && partie[coup_courant].plateau[i-2][j]==0 )
{
coup_trouve[0]=i; coup_trouve[1]=j; coup_trouve[2]=2; trouve=1; break;
}
else if (j<5 && partie[coup_courant].plateau[i][j+1]==1 && partie[coup_courant].plateau[i][j+2]==0 )
{
coup_trouve[0]=i; coup_trouve[1]=j; coup_trouve[2]=3; trouve=1; break;
}
}
}
if (trouve==1) break;
}
}
}
else // on joue le coup suivant, donc on reprend la première solution à partir de (0,0)
{
for (i=0; i<7 ; i++)
{
for (j=0; j<7; j++)
if (partie[coup_courant].plateau[i][j] == 1)
{
if (i<5 && partie[coup_courant].plateau[i+1][j]==1 && partie[coup_courant].plateau[i+2][j]==0 )
{
coup_trouve[0]=i; coup_trouve[1]=j; coup_trouve[2]=0; trouve=1; break;
}
else if (j>1 && partie[coup_courant].plateau[i][j-1]==1 && partie[coup_courant].plateau[i][j-2]==0)
{
coup_trouve[0]=i; coup_trouve[1]=j; coup_trouve[2]=1; trouve=1; break;
}
else if (i>1 && partie[coup_courant].plateau[i-1][j]==1 && partie[coup_courant].plateau[i-2][j]==0 )
{
coup_trouve[0]=i; coup_trouve[1]=j; coup_trouve[2]=2; trouve=1; break;
}
else if (j<5 && partie[coup_courant].plateau[i][j+1]==1 && partie[coup_courant].plateau[i][j+2]==0 )
{
coup_trouve[0]=i; coup_trouve[1]=j; coup_trouve[2]=3; trouve=1; break;
}
}
if (trouve==1) break;
}
}
//partie[coup_courant].ligne=coup_trouve[0];
//partie[coup_courant].colonne=coup_trouve[1];
//partie[coup_courant].direction=coup_trouve[2];
}
void affiche_plateau(int tableau[7][7])
{
int i,j;
for (i=0; i<7; i++)
{
for (j=0; j<7; j++)
printf ("%d", tableau[i][j]);
printf("\n");
}
printf("\n");
}
int jouer(int retour)
{
int i, j;
coup_suivant (retour);
if (coup_trouve[0]==255)
{
//goto(1,1);
coup_courant--;
if (meilleure < coup_courant)
{
meilleure = coup_courant;
for(i=0; i<30; i++)
{
//affiche_plateau(partie[i].plateau);
printf("ligne : %d ; colonne : %d ; direction : %d\n", partie[i].ligne, partie[i].colonne, partie[i].direction);
}
printf("parties jouées : %lli\n\nMeileure partie : %d\n\n", nb_parties, meilleure);
system("date");
}
nb_parties++;
if ((nb_parties%500000000) == 0) { printf("\nNb parties : %d\n", nb_parties); system("date"); }
return 1;
}
else
{
coup_courant++;
partie[coup_courant].ligne=coup_trouve[0];
partie[coup_courant].colonne=coup_trouve[1];
partie[coup_courant].direction=coup_trouve[2];
for (i=0; i<7; i++) // on recopie le plateau
for (j=0; j<7; j++)
partie[coup_courant].plateau[i][j]=partie[coup_courant-1].plateau[i][j];
partie[coup_courant].plateau[coup_trouve[0]][coup_trouve[1]]=0;
switch (coup_trouve[2])
{
case 0 : partie[coup_courant].plateau[coup_trouve[0]+1][coup_trouve[1]]=0;
partie[coup_courant].plateau[coup_trouve[0]+2][coup_trouve[1]]=1;
break;
case 1 : partie[coup_courant].plateau[coup_trouve[0]][coup_trouve[1]-1]=0;
partie[coup_courant].plateau[coup_trouve[0]][coup_trouve[1]-2]=1;
break;
case 2 : partie[coup_courant].plateau[coup_trouve[0]-1][coup_trouve[1]]=0;
partie[coup_courant].plateau[coup_trouve[0]-2][coup_trouve[1]]=1;
break;
int main(void)
{
// variables
int i, j, k, retour=0;
//initialisation des plateaux des différents coups
// 2 pour une case injouable, 1 pour un pion, et 0 pour un trou
for (i=0; i<33; i++)
for (j=0; j<7; j++)
for (k=0; k<7; k++)
if ((j<2 || j>4) && (k<2 || k>4))
{
partie[i].plateau[j][k]=2;
}
else
partie[i].plateau[j][k]=1;
// on joue le premier coup car la symétrie fait que l'on a pas le choix
partie[0].plateau[3][1]=0; partie[0].plateau[3][2]=0;
coup_courant=0;
// on initialise le premier coup jouer comme étant la première case
partie[0].ligne= 0;
partie[0].colonne= 0;
partie[0].direction= 0;
// et on commence à jouer
while (coup_courant!=30)
{
if (retour) // on revient en arrière
{
retour=jouer(1);
}
else // on avance d'un coup
retour=jouer(0);
}
for(i=0; i<30; i++)
{
printf("ligne : %d ; colonne : %d ; direction : %d\n", partie[i].ligne, partie[i].colonne, partie[i].direction);
}
printf("parties jouées : %lli\n\nMeileure partie : %d\n\n", nb_parties, meilleure);
system("date");
return 0;
}
Et voici le résultat de l'exécution (le programme donne les solutions intermédiaires) :
desgeorge@linux:~/Langage_C> ./solitaire
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 1 ; colonne : 2 ; direction : 0
ligne : 1 ; colonne : 4 ; direction : 1
ligne : 0 ; colonne : 2 ; direction : 0
ligne : 0 ; colonne : 4 ; direction : 1
ligne : 3 ; colonne : 2 ; direction : 2
ligne : 0 ; colonne : 2 ; direction : 0
ligne : 3 ; colonne : 3 ; direction : 2
ligne : 2 ; colonne : 1 ; direction : 3
ligne : 1 ; colonne : 3 ; direction : 0
ligne : 2 ; colonne : 5 ; direction : 1
ligne : 3 ; colonne : 3 ; direction : 2
ligne : 3 ; colonne : 5 ; direction : 1
ligne : 4 ; colonne : 3 ; direction : 2
ligne : 1 ; colonne : 3 ; direction : 0
ligne : 4 ; colonne : 1 ; direction : 3
ligne : 4 ; colonne : 3 ; direction : 2
ligne : 4 ; colonne : 5 ; direction : 1
ligne : 5 ; colonne : 3 ; direction : 2
ligne : 2 ; colonne : 3 ; direction : 0
ligne : 6 ; colonne : 2 ; direction : 2
ligne : 4 ; colonne : 2 ; direction : 3
ligne : 5 ; colonne : 4 ; direction : 2
ligne : 6 ; colonne : 4 ; direction : 1
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
parties jouées : 0
Meileure partie : 22
lun mar 15 17:14:33 CET 2004
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 1 ; colonne : 2 ; direction : 0
ligne : 1 ; colonne : 4 ; direction : 1
ligne : 0 ; colonne : 2 ; direction : 0
ligne : 0 ; colonne : 4 ; direction : 1
ligne : 3 ; colonne : 2 ; direction : 2
ligne : 0 ; colonne : 2 ; direction : 0
ligne : 3 ; colonne : 3 ; direction : 2
ligne : 2 ; colonne : 1 ; direction : 3
ligne : 1 ; colonne : 3 ; direction : 0
ligne : 2 ; colonne : 5 ; direction : 1
ligne : 3 ; colonne : 3 ; direction : 2
ligne : 3 ; colonne : 5 ; direction : 1
ligne : 4 ; colonne : 3 ; direction : 2
ligne : 1 ; colonne : 3 ; direction : 0
ligne : 4 ; colonne : 1 ; direction : 3
ligne : 4 ; colonne : 3 ; direction : 2
ligne : 4 ; colonne : 5 ; direction : 1
ligne : 5 ; colonne : 3 ; direction : 2
ligne : 2 ; colonne : 3 ; direction : 0
ligne : 6 ; colonne : 2 ; direction : 2
ligne : 4 ; colonne : 3 ; direction : 1
ligne : 4 ; colonne : 0 ; direction : 3
ligne : 2 ; colonne : 0 ; direction : 0
ligne : 6 ; colonne : 4 ; direction : 1
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
parties jouées : 6
Meileure partie : 23
lun mar 15 17:14:33 CET 2004
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 1 ; colonne : 2 ; direction : 0
ligne : 1 ; colonne : 4 ; direction : 1
ligne : 0 ; colonne : 2 ; direction : 0
ligne : 0 ; colonne : 4 ; direction : 1
ligne : 3 ; colonne : 2 ; direction : 2
ligne : 0 ; colonne : 2 ; direction : 0
ligne : 3 ; colonne : 3 ; direction : 2
ligne : 2 ; colonne : 1 ; direction : 3
ligne : 1 ; colonne : 3 ; direction : 0
ligne : 2 ; colonne : 5 ; direction : 1
ligne : 3 ; colonne : 3 ; direction : 2
ligne : 3 ; colonne : 5 ; direction : 1
ligne : 4 ; colonne : 3 ; direction : 2
ligne : 1 ; colonne : 3 ; direction : 0
ligne : 4 ; colonne : 1 ; direction : 3
ligne : 4 ; colonne : 3 ; direction : 2
ligne : 4 ; colonne : 5 ; direction : 1
ligne : 6 ; colonne : 2 ; direction : 2
ligne : 4 ; colonne : 3 ; direction : 1
ligne : 4 ; colonne : 0 ; direction : 3
ligne : 2 ; colonne : 0 ; direction : 0
ligne : 6 ; colonne : 3 ; direction : 2
ligne : 4 ; colonne : 3 ; direction : 1
ligne : 4 ; colonne : 0 ; direction : 3
ligne : 6 ; colonne : 4 ; direction : 2
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
parties jouées : 205
Meileure partie : 24
lun mar 15 17:14:33 CET 2004
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 1 ; colonne : 2 ; direction : 0
ligne : 1 ; colonne : 4 ; direction : 1
ligne : 0 ; colonne : 2 ; direction : 0
ligne : 0 ; colonne : 4 ; direction : 1
ligne : 3 ; colonne : 2 ; direction : 2
ligne : 0 ; colonne : 2 ; direction : 0
ligne : 3 ; colonne : 3 ; direction : 2
ligne : 2 ; colonne : 1 ; direction : 3
ligne : 1 ; colonne : 3 ; direction : 0
ligne : 2 ; colonne : 5 ; direction : 1
ligne : 3 ; colonne : 3 ; direction : 2
ligne : 3 ; colonne : 5 ; direction : 1
ligne : 4 ; colonne : 3 ; direction : 2
ligne : 1 ; colonne : 3 ; direction : 0
ligne : 4 ; colonne : 1 ; direction : 3
ligne : 4 ; colonne : 3 ; direction : 2
ligne : 4 ; colonne : 5 ; direction : 1
ligne : 6 ; colonne : 2 ; direction : 2
ligne : 4 ; colonne : 3 ; direction : 1
ligne : 4 ; colonne : 0 ; direction : 3
ligne : 2 ; colonne : 0 ; direction : 0
ligne : 6 ; colonne : 3 ; direction : 2
ligne : 6 ; colonne : 4 ; direction : 2
ligne : 4 ; colonne : 3 ; direction : 3
ligne : 4 ; colonne : 6 ; direction : 1
ligne : 2 ; colonne : 6 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
parties jouées : 212
Meileure partie : 25
lun mar 15 17:14:33 CET 2004
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 1 ; colonne : 2 ; direction : 0
ligne : 1 ; colonne : 4 ; direction : 1
ligne : 0 ; colonne : 2 ; direction : 0
ligne : 0 ; colonne : 4 ; direction : 1
ligne : 3 ; colonne : 2 ; direction : 2
ligne : 0 ; colonne : 2 ; direction : 0
ligne : 3 ; colonne : 3 ; direction : 2
ligne : 2 ; colonne : 1 ; direction : 3
ligne : 1 ; colonne : 3 ; direction : 0
ligne : 2 ; colonne : 5 ; direction : 1
ligne : 3 ; colonne : 3 ; direction : 2
ligne : 3 ; colonne : 5 ; direction : 1
ligne : 4 ; colonne : 3 ; direction : 2
ligne : 1 ; colonne : 3 ; direction : 0
ligne : 4 ; colonne : 1 ; direction : 3
ligne : 4 ; colonne : 4 ; direction : 1
ligne : 4 ; colonne : 6 ; direction : 1
ligne : 2 ; colonne : 6 ; direction : 0
ligne : 5 ; colonne : 4 ; direction : 2
ligne : 3 ; colonne : 4 ; direction : 1
ligne : 6 ; colonne : 3 ; direction : 2
ligne : 4 ; colonne : 3 ; direction : 1
ligne : 6 ; colonne : 2 ; direction : 2
ligne : 3 ; colonne : 2 ; direction : 0
ligne : 4 ; colonne : 0 ; direction : 3
ligne : 2 ; colonne : 0 ; direction : 0
ligne : 4 ; colonne : 2 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 0 ; colonne : 0 ; direction : 0
parties jouées : 4249
Meileure partie : 26
lun mar 15 17:14:33 CET 2004
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 1 ; colonne : 2 ; direction : 0
ligne : 1 ; colonne : 4 ; direction : 1
ligne : 0 ; colonne : 2 ; direction : 0
ligne : 0 ; colonne : 4 ; direction : 1
ligne : 3 ; colonne : 2 ; direction : 2
ligne : 0 ; colonne : 2 ; direction : 0
ligne : 3 ; colonne : 3 ; direction : 2
ligne : 2 ; colonne : 1 ; direction : 3
ligne : 1 ; colonne : 3 ; direction : 0
ligne : 2 ; colonne : 5 ; direction : 1
ligne : 3 ; colonne : 3 ; direction : 2
ligne : 3 ; colonne : 5 ; direction : 1
ligne : 4 ; colonne : 3 ; direction : 2
ligne : 1 ; colonne : 3 ; direction : 0
ligne : 4 ; colonne : 1 ; direction : 3
ligne : 5 ; colonne : 4 ; direction : 2
ligne : 3 ; colonne : 3 ; direction : 3
ligne : 3 ; colonne : 6 ; direction : 1
ligne : 4 ; colonne : 6 ; direction : 1
ligne : 3 ; colonne : 4 ; direction : 0
ligne : 6 ; colonne : 2 ; direction : 2
ligne : 4 ; colonne : 3 ; direction : 1
ligne : 4 ; colonne : 0 ; direction : 3
ligne : 2 ; colonne : 0 ; direction : 0
ligne : 6 ; colonne : 3 ; direction : 2
ligne : 4 ; colonne : 3 ; direction : 1
ligne : 4 ; colonne : 0 ; direction : 3
ligne : 6 ; colonne : 4 ; direction : 2
ligne : 0 ; colonne : 0 ; direction : 0
parties jouées : 5120
Meileure partie : 27
lun mar 15 17:14:33 CET 2004
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 1 ; colonne : 2 ; direction : 0
ligne : 1 ; colonne : 4 ; direction : 1
ligne : 0 ; colonne : 2 ; direction : 0
ligne : 0 ; colonne : 4 ; direction : 1
ligne : 3 ; colonne : 2 ; direction : 2
ligne : 0 ; colonne : 2 ; direction : 0
ligne : 3 ; colonne : 3 ; direction : 2
ligne : 2 ; colonne : 1 ; direction : 3
ligne : 1 ; colonne : 3 ; direction : 0
ligne : 2 ; colonne : 5 ; direction : 1
ligne : 3 ; colonne : 3 ; direction : 2
ligne : 5 ; colonne : 2 ; direction : 2
ligne : 4 ; colonne : 0 ; direction : 3
ligne : 2 ; colonne : 0 ; direction : 0
ligne : 3 ; colonne : 2 ; direction : 0
ligne : 6 ; colonne : 2 ; direction : 2
ligne : 4 ; colonne : 3 ; direction : 1
ligne : 4 ; colonne : 0 ; direction : 3
ligne : 4 ; colonne : 5 ; direction : 1
ligne : 6 ; colonne : 4 ; direction : 2
ligne : 4 ; colonne : 3 ; direction : 3
ligne : 4 ; colonne : 6 ; direction : 1
ligne : 2 ; colonne : 6 ; direction : 0
ligne : 3 ; colonne : 4 ; direction : 0
ligne : 6 ; colonne : 3 ; direction : 2
ligne : 4 ; colonne : 2 ; direction : 3
ligne : 5 ; colonne : 4 ; direction : 2
ligne : 3 ; colonne : 4 ; direction : 3
ligne : 4 ; colonne : 6 ; direction : 2
parties jouées : 93288660
Meileure partie : 28
lun mar 15 17:17:28 CET 2004
Nb parties : 500000000
lun mar 15 17:30:04 CET 2004
Nb parties : 1000000000
lun mar 15 17:45:29 CET 2004
Nb parties : 1500000000
lun mar 15 18:00:51 CET 2004
Nb parties : 2000000000
lun mar 15 18:16:14 CET 2004
Nb parties : -1794967296
lun mar 15 18:31:42 CET 2004
ligne : 0 ; colonne : 0 ; direction : 0
ligne : 1 ; colonne : 2 ; direction : 0
ligne : 1 ; colonne : 4 ; direction : 1
ligne : 0 ; colonne : 2 ; direction : 0
ligne : 0 ; colonne : 4 ; direction : 1
ligne : 3 ; colonne : 2 ; direction : 2
ligne : 0 ; colonne : 2 ; direction : 0
ligne : 3 ; colonne : 3 ; direction : 2
ligne : 2 ; colonne : 1 ; direction : 3
ligne : 1 ; colonne : 3 ; direction : 0
ligne : 2 ; colonne : 5 ; direction : 1
ligne : 5 ; colonne : 2 ; direction : 2
ligne : 4 ; colonne : 0 ; direction : 3
ligne : 2 ; colonne : 0 ; direction : 0
ligne : 3 ; colonne : 2 ; direction : 0
ligne : 6 ; colonne : 2 ; direction : 2
ligne : 4 ; colonne : 3 ; direction : 1
ligne : 4 ; colonne : 0 ; direction : 3
ligne : 4 ; colonne : 5 ; direction : 1
ligne : 6 ; colonne : 4 ; direction : 2
ligne : 4 ; colonne : 3 ; direction : 3
ligne : 2 ; colonne : 3 ; direction : 0
ligne : 4 ; colonne : 6 ; direction : 1
ligne : 2 ; colonne : 6 ; direction : 0
ligne : 3 ; colonne : 4 ; direction : 0
ligne : 4 ; colonne : 2 ; direction : 3
ligne : 6 ; colonne : 3 ; direction : 2
ligne : 4 ; colonne : 3 ; direction : 3
ligne : 4 ; colonne : 6 ; direction : 1
ligne : 5 ; colonne : 4 ; direction : 2
parties jouées : 2943463868
Meileure partie : 28
lun mar 15 18:45:24 CET 2004
desgeorge@linux:~/Langage_C>
