Bonjour
Comment tester si une certaine disposition du jeu Taquin est soluble ou insoluble ?
Pour un jeu d'une grille de NC colonnes et NL lignes, il existe (NC*NL)! situations dont exactement une sur deux est soluble.
Par exemple, pour la dimension la plus courante 4x4, il existe 10'461'394'944'000 dispositions initiales solubles et autant d'insolubles.
Les mots
soluble, insoluble sont utilisés ici avec un sens "mathématique" et non "chimique".
On pourrait aussi utiliser les mots
faisable, infaisable ou
possible, impossible.
Soluble veut dire qu'avec les règles du jeu Taquin, on peut arriver à une
disposition finale qui correspond le plus souvent à {1,2,3,...,NC*NL-1,0}, c'est-à-dire pour le jeu 4x4, à {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0} ou
| 1 2 3 4|
| 5 6 7 8|
| 9 10 11 12|
|13 14 15 0| (0: la case vide).
Les codes présentés ici sont personnels et font suite à l'article CodeS-SourceS
Jeu: Taquin NxN.
Essayons d'abord de programmer la méthode proposée par Wikipédia
Taquin pour déterminer la solubilité d'une disposition nCxnL "contenue" dans le tableau
jeu:
/* Exemple: nC=4, nL=4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 n<->j jeu[n]<->jeu[j] np
{13, 2, 3,12, 9,11, 1,10, 0, 6, 4, 8,15,14, 7, 5} 15 8 5 0 1
{13, 2, 3,12, 9,11, 1,10, 5, 6, 4, 8,15,14, 7, 0} 14 12 7 15 2
{13, 2, 3,12, 9,11, 1,10, 5, 6, 4, 8, 7,14,15, 0} 13 13
{13, 2, 3,12, 9,11, 1,10, 5, 6, 4, 8, 7,14,15, 0} 12 0 7 13 3
{ 7, 2, 3,12, 9,11, 1,10, 5, 6, 4, 8,13,14,15, 0} 11 3 8 12 4
{ 7, 2, 3, 8, 9,11, 1,10, 5, 6, 4,12,13,14,15, 0} 10 5 4 11 5
{ 7, 2, 3, 8, 9, 4, 1,10, 5, 6,11,12,13,14,15, 0} 9 7 6 10 6
{ 7, 2, 3, 8, 9, 4, 1, 6, 5,10,11,12,13,14,15, 0} 8 4 5 9 7
{ 7, 2, 3, 8, 5, 4, 1, 6, 9,10,11,12,13,14,15, 0} 7 3 6 8 8
{ 7, 2, 3, 6, 5, 4, 1, 8, 9,10,11,12,13,14,15, 0} 6 0 1 7 9
{ 1, 2, 3, 6, 5, 4, 7, 8, 9,10,11,12,13,14,15, 0} 5 3 4 6 10
{ 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15, 0} 4 4
{ 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15, 0} 3 3
{ 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15, 0} 2 2
{ 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15, 0} 1 1
*/
bool Insoluble_1(int nC, int nL, int *jeu) {
int e, j = 0, n = nC*nL - 1, np;
while (jeu[j]) j++; // j = case vide
np = (n-j)%nC + (n-j)/nC; // dépl. de la case vide jusqu'à sa position finale
for ( ; n > 0; --n) {
if (n != j) {e = jeu[j]; jeu[j] = jeu[n]; jeu[n] = e; j=n; ++np;} // échange
while (jeu[j] != n) --j; // j = prochaine case à (dé)placer
}
return 1&np;
} // Attention: le contenu de l'array 'int *jeu' est modifié
Le premier groupe de 14 tests (dont le 13ème correspond à l'exemple proposé par Wikipédia) permet d'en faire une "vérification".
Peut-on encore "réduire" ce code pourtant déjà bien simple ?
La valeur mise à la place n (jeu[n] = n+1) n'est plus utilisée, on peut donc éviter cette affectation (qui utilise la variable
e):
bool Insoluble_2(int nC, int nL, int *jeu) {
int j = 0, n = nC*nL - 1, np;
while (jeu[j]) j++; // j = case vide
for (np = (n-j)%nC + (n-j)/nC; n > 0; --n) {
if (n != j) {jeu[j] = jeu[n]; j = n; ++np;} // "permutation"
while (jeu[--j] != n) ; // j = prochaine case à (dé)placer
}
return 1&np;
} // Attention: le contenu de l'array 'int *jeu' est modifié
Pour ne pas modifier la situation donnée
jeu, travaillons avec une copie:
const int MaxDim = 6; // ou autre
...
bool Insoluble_3(int nC, int nL, int *jeu) {
int i, j, n = nC*nL - 1, np, copie[MaxDim*MaxDim];
for (i = 0; i <= n; ++i)
if ((copie[i] = jeu[i]) == 0) j = i; // copie et j = case vide
for (np = (n-j)%nC + (n-j)/nC; n > 0; --n) {
if (n != j) {copie[j] = copie[n]; j = n; ++np;} // permutation
while (copie[--j] != n) ; // j = prochaine case à (dé)placer
}
return 1&np;
} // Le contenu de l'array 'int *jeu' n'est pas modifié
On peut regretter cette nécessité de dédoubler le jeu et également le fait que la méthode utilisée ne soit que de performance quadratique par rapport au nombre de cases:
O((nC*nL)²
).
Mais pour des jeux de taille "raisonnables" (par exemple 16*16), le temps de calcul reste tout à fait "négligeable".
Remarque: Dans tous les codes, l'argument
jeu doit impérativement contenir une permutation des nombres 0 à (nC*nL-1).
Dans l'incertitude, il faudra le tester préalablement.
Je propose encore 100 tests avec dimensions et initialisation aléatoires en utilisant la fonction
RandPermutInit(...) de l'article CodeS-SourceS
Permutations aléatoires.
Voici le programme de test complet contenu dans un seul fichier:
#include <stdio.h>
#include <stdlib.h>
const int MaxDim = 6;
bool Insoluble_1(int nC, int nL, int *jeu) {
int e, j = 0, n = nC*nL - 1, np;
while (jeu[j]) j++; // j = case vide
np = (n-j)%nC + (n-j)/nC; // dépl. de la case vide jusqu'à sa position finale
for ( ; n > 0; --n) {
if (n != j) {e = jeu[j]; jeu[j] = jeu[n]; jeu[n] = e; j=n; ++np;} // échange
while (jeu[j] != n) --j; // j = prochaine case à (dé)placer
}
return 1&np;
} // Attention: le contenu de l'array 'int *jeu' est modifié
bool Insoluble_2(int nC, int nL, int *jeu) {
int j = 0, n = nC*nL - 1, np;
while (jeu[j]) j++; // j = case vide
for (np = (n-j)%nC + (n-j)/nC; n > 0; --n) {
if (n != j) {jeu[j] = jeu[n]; j = n; ++np;} // "permutation"
while (jeu[--j] != n) ; // j = prochaine case à (dé)placer
}
return 1&np;
} // Attention: le contenu de l'array 'int *jeu' est modifié
bool Insoluble_3(int nC, int nL, int *jeu) {
int i, j, n = nC*nL - 1, np, copie[MaxDim*MaxDim];
for (i = 0; i <= n; ++i)
if ((copie[i] = jeu[i]) == 0) j = i; // copie et j = case vide
for (np = (n-j)%nC + (n-j)/nC; n > 0; --n) {
if (n != j) {copie[j] = copie[n]; j = n; ++np;} // permutation
while (copie[--j] != n) ; // j = prochaine case à (dé)placer
}
return 1&np;
} // Le contenu de l'array 'int *jeu' n'est pas modifié
void RandPermutInit(int *ent, int n) { // ent[]: assez grand non initialisé
for (int r, i = 0; i < n; ++i) {ent[i] = ent[r = rand()%(i+1)]; ent[r] = i;}
} // Tiré de l'article CodeS-SourceS: Permutations aléatoires
void PrintJeu(int nC, int nL, int *jeu) {
printf("nTaquin %ix%i:", nC, nL);
for (int l = 0; l < nL; ++l) {
printf("n ");
for (int c=0; c<nC; ++c) printf(" %2i", jeu[l*nC + c]);
}
// Test de la fonction Insoluble_X(...) (Coisissez X = 1, 2 ou 3):
printf(" %sn", Insoluble_3(nC,nL,jeu) ? "insoluble" : "soluble");
}
int main() {
int jeu[MaxDim*MaxDim];
int Jeu_22A[] = { 1, 2, 3, 0};
int Jeu_22B[] = { 1, 3, 2, 0};
int Jeu_22C[] = { 2, 0, 1, 3};
int Jeu_22D[] = { 2, 0, 3, 1};
int Jeu_33A[] = { 1, 2, 3, 4, 5, 6, 7, 8, 0};
int Jeu_33B[] = { 1, 2, 3, 4, 5, 6, 8, 7, 0};
int Jeu_33C[] = { 7, 0, 3, 6, 2, 8, 4, 5, 1};
int Jeu_33D[] = { 7, 0, 3, 4, 2, 8, 6, 5, 1};
int Jeu_44A[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15, 0};
int Jeu_44B[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,15,14, 0};
int Jeu_44C[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15};
int Jeu_44D[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,15,14};
int Jeu_44E[] = {13, 2, 3,12, 9,11, 1,10, 0, 6, 4,14,15, 8, 7, 5}; // Wiki
int Jeu_44F[] = {13, 2, 3,12, 9,11, 1,10, 0, 6, 4, 8,15,14, 7, 5};
PrintJeu(2,2,Jeu_22A);
PrintJeu(2,2,Jeu_22B);
PrintJeu(2,2,Jeu_22C);
PrintJeu(2,2,Jeu_22D);
PrintJeu(3,3,Jeu_33A);
PrintJeu(3,3,Jeu_33B);
PrintJeu(3,3,Jeu_33C);
PrintJeu(3,3,Jeu_33D);
PrintJeu(4,4,Jeu_44A);
PrintJeu(4,4,Jeu_44B);
PrintJeu(4,4,Jeu_44C);
PrintJeu(4,4,Jeu_44D);
PrintJeu(4,4,Jeu_44E);
PrintJeu(4,4,Jeu_44F);
printf("nn100 tests avec dimensions et initialisation aléatoires:n");
printf("======================================================n");
for (int k = 0; k < 100; ++k) {
int nC = 2 + rand() % (MaxDim-1), nL = 2 + rand() % (MaxDim-1);
RandPermutInit(jeu, nC*nL); // voir Codes-SourceS: Permutations aléatoires
PrintJeu(nC,nL,jeu);
}
getchar();
}
Et qui donne l'
Output:
Taquin 2x2:
1 2
3 0 soluble
Taquin 2x2:
1 3
2 0 insoluble
Taquin 2x2:
2 0
1 3 soluble
Taquin 2x2:
2 0
3 1 insoluble
Taquin 3x3:
1 2 3
4 5 6
7 8 0 soluble
Taquin 3x3:
1 2 3
4 5 6
8 7 0 insoluble
Taquin 3x3:
7 0 3
6 2 8
4 5 1 soluble
Taquin 3x3:
7 0 3
4 2 8
6 5 1 insoluble
Taquin 4x4:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0 soluble
Taquin 4x4:
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 0 insoluble
Taquin 4x4:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15 insoluble
Taquin 4x4:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 15 14 soluble
Taquin 4x4:
13 2 3 12
9 11 1 10
0 6 4 14
15 8 7 5 insoluble
Taquin 4x4:
13 2 3 12
9 11 1 10
0 6 4 8
15 14 7 5 soluble
100 tests avec dimensions et initialisation aléatoires:
======================================================
Taquin 3x4:
7 0 2
11 1 10
3 5 8
6 9 4 soluble
Taquin 3x3:
5 7 1
6 8 3
2 4 0 soluble
Taquin 4x3:
1 4 6 3
8 7 2 11
0 10 5 9 soluble
Taquin 6x5:
27 10 22 15 14 26
24 17 3 0 12 20
11 5 21 13 19 9
25 2 8 6 1 16
4 18 29 23 28 7 soluble
Taquin 2x2:
1 0
3 2 soluble
Taquin 3x5:
13 9 2
6 12 8
7 10 3
1 0 5
4 14 11 insoluble
Taquin 4x5:
18 3 11 4
0 12 8 10
5 19 17 14
6 16 7 2
9 1 13 15 insoluble
Taquin 4x5:
5 4 13 8
18 10 14 7
0 16 17 19
15 3 2 9
6 1 11 12 soluble
Taquin 4x4:
15 1 8 14
2 5 7 0
9 10 13 12
6 11 3 4 insoluble
Taquin 2x3:
0 2
1 3
4 5 insoluble
Taquin 5x5:
0 17 16 24 21
3 8 1 18 6
5 23 20 12 15
9 10 14 19 4
13 7 11 2 22 insoluble
Taquin 5x5:
2 6 8 23 19
10 5 21 11 16
24 14 9 13 17
4 7 20 1 22
15 18 3 0 12 insoluble
Taquin 5x5:
5 21 7 10 16
15 17 1 24 8
4 20 19 18 6
11 14 23 3 0
22 2 12 9 13 insoluble
Taquin 3x2:
2 0 5
1 4 3 insoluble
Taquin 2x5:
1 9
2 8
7 0
4 3
6 5 soluble
Taquin 5x4:
9 6 19 14 5
3 4 18 2 17
8 13 7 12 16
0 11 15 1 10 soluble
Taquin 2x4:
1 7
4 2
5 0
6 3 soluble
Taquin 6x3:
3 11 7 14 13 5
6 17 10 0 4 15
2 16 12 9 1 8 insoluble
Taquin 3x4:
0 10 3
1 8 2
9 5 11
4 7 6 insoluble
Taquin 4x2:
3 7 5 1
2 0 6 4 insoluble
Taquin 2x2:
3 0
2 1 soluble
Taquin 2x5:
6 5
4 1
7 2
0 3
8 9 insoluble
Taquin 3x2:
5 1 2
0 4 3 insoluble
Taquin 6x5:
1 3 7 25 16 8
18 11 21 24 15 27
23 6 19 20 10 26
29 2 13 9 28 12
4 0 17 14 22 5 insoluble
Taquin 4x5:
5 16 9 19
14 7 0 18
3 1 4 17
12 6 8 15
2 11 10 13 soluble
Taquin 4x2:
7 1 5 6
2 4 0 3 insoluble
Taquin 2x4:
4 5
3 2
0 6
1 7 insoluble
Taquin 2x3:
3 5
1 0
4 2 insoluble
Taquin 6x6:
23 9 24 8 3 30
22 18 10 5 19 20
0 12 13 1 16 11
14 34 6 7 32 15
27 2 4 26 25 31
28 33 29 35 17 21 insoluble
Taquin 4x6:
13 14 4 5
11 12 23 1
3 10 18 21
9 17 7 22
8 0 6 16
19 20 2 15 insoluble
Taquin 6x5:
24 27 3 6 25 20
22 17 28 1 16 10
4 12 13 21 9 19
26 0 11 15 18 8
5 29 7 23 2 14 insoluble
Taquin 2x3:
4 5
1 0
3 2 soluble
Taquin 2x3:
2 0
4 5
3 1 soluble
Taquin 3x6:
1 11 12
16 2 0
10 14 15
5 6 17
8 3 13
4 9 7 soluble
Taquin 4x6:
22 19 6 2
4 23 5 12
16 21 8 11
17 18 10 20
14 7 13 9
15 3 1 0 soluble
Taquin 2x3:
0 5
3 4
1 2 soluble
Taquin 3x5:
14 12 7
13 0 3
1 2 5
6 4 9
11 10 8 soluble
Taquin 4x4:
12 7 6 9
15 8 10 1
13 0 4 5
14 11 2 3 insoluble
Taquin 4x2:
4 1 6 2
5 7 0 3 soluble
Taquin 2x2:
3 0
1 2 insoluble
Taquin 6x5:
19 14 21 17 18 26
8 16 9 20 10 15
12 2 28 24 22 1
4 0 11 29 3 7
27 25 23 6 5 13 soluble
Taquin 4x6:
21 2 7 1
3 20 22 9
4 23 6 15
8 17 5 18
10 11 13 16
12 19 14 0 insoluble
Taquin 3x6:
13 3 17
15 11 0
16 12 14
1 10 2
9 4 6
5 7 8 insoluble
Taquin 3x5:
1 13 6
0 10 2
11 12 9
4 7 5
14 3 8 insoluble
Taquin 4x4:
7 3 12 14
11 9 6 13
5 8 10 0
1 2 4 15 insoluble
Taquin 4x6:
6 16 5 22
9 7 15 4
0 1 17 18
2 10 20 3
19 23 13 12
8 11 14 21 soluble
Taquin 5x5:
7 21 0 3 19
15 8 11 17 1
16 20 4 13 23
18 5 9 2 22
14 24 12 6 10 insoluble
Taquin 5x4:
1 3 0 9 14
2 4 13 6 5
17 16 8 12 11
18 7 15 19 10 insoluble
Taquin 4x2:
4 5 7 6
0 3 1 2 insoluble
Taquin 2x2:
2 3
1 0 soluble
Taquin 3x4:
7 11 5
4 9 3
1 2 10
8 6 0 soluble
Taquin 6x5:
26 23 3 29 15 25
9 16 18 17 0 8
2 22 12 21 4 28
5 7 13 14 11 27
1 20 19 6 10 24 insoluble
Taquin 2x3:
2 3
1 5
0 4 insoluble
Taquin 4x5:
13 5 3 8
16 7 14 18
15 11 2 9
1 10 12 19
6 4 0 17 soluble
Taquin 2x6:
4 11
10 2
5 9
7 1
0 6
3 8 insoluble
Taquin 2x6:
5 7
4 6
8 10
2 0
9 1
11 3 soluble
Taquin 5x5:
3 14 8 20 2
16 21 13 0 23
5 1 10 19 6
9 4 24 11 22
18 17 15 7 12 insoluble
Taquin 5x6:
0 28 19 2 5
25 6 14 21 23
10 20 24 9 3
13 1 12 29 7
8 22 11 18 16
17 4 26 15 27 soluble
Taquin 4x4:
9 2 1 8
15 4 12 3
11 5 14 10
6 7 0 13 insoluble
Taquin 5x3:
2 1 13 7 3
0 14 12 8 9
11 10 6 5 4 soluble
Taquin 6x5:
7 18 17 14 5 9
28 29 6 8 21 12
23 22 26 24 3 0
16 27 19 11 1 10
2 25 4 20 15 13 insoluble
Taquin 5x4:
9 18 17 13 8
14 19 12 15 6
2 10 5 11 7
4 0 3 1 16 insoluble
Taquin 6x3:
16 10 15 7 0 5
11 3 12 4 2 6
14 8 17 1 13 9 insoluble
Taquin 6x6:
7 27 31 26 19 21
22 10 30 32 23 34
35 29 3 4 13 28
25 11 20 0 2 16
12 18 33 14 1 15
24 5 6 17 8 9 insoluble
Taquin 6x2:
0 4 10 5 2 9
3 8 6 7 11 1 soluble
Taquin 2x6:
5 9
3 1
11 7
4 2
0 10
8 6 insoluble
Taquin 5x3:
7 9 3 12 11
6 13 14 2 5
1 4 0 8 10 insoluble
Taquin 2x2:
1 2
3 0 soluble
Taquin 4x4:
11 7 9 0
13 6 5 1
15 10 12 4
14 8 3 2 insoluble
Taquin 2x5:
3 7
1 0
8 5
9 4
2 6 soluble
Taquin 2x4:
3 1
6 7
4 0
2 5 soluble
Taquin 4x3:
0 1 11 3
7 2 6 8
10 4 5 9 insoluble
Taquin 2x6:
2 1
6 3
11 5
10 4
7 0
9 8 insoluble
Taquin 4x3:
0 6 5 8
10 4 1 11
9 3 7 2 soluble
Taquin 5x3:
13 11 14 2 4
10 8 12 3 7
9 0 6 1 5 insoluble
Taquin 4x2:
6 3 2 0
1 7 5 4 soluble
Taquin 2x5:
0 2
6 8
4 5
7 1
9 3 insoluble
Taquin 3x4:
11 0 6
4 2 3
10 5 7
1 8 9 insoluble
Taquin 6x3:
0 10 14 8 1 4
15 16 9 11 13 12
6 17 2 7 5 3 insoluble
Taquin 2x2:
3 0
1 2 insoluble
Taquin 2x5:
6 5
9 1
2 4
3 7
0 8 soluble
Taquin 4x5:
7 1 16 4
8 11 6 5
19 15 14 0
12 13 18 2
3 10 9 17 insoluble
Taquin 5x3:
11 1 2 0 4
13 10 7 9 3
5 6 12 8 14 insoluble
Taquin 2x5:
7 4
0 1
2 9
8 6
5 3 soluble
Taquin 6x2:
11 6 5 9 4 3
1 8 10 7 0 2 insoluble
Taquin 4x3:
11 6 8 1
9 2 0 7
10 4 3 5 soluble
Taquin 5x4:
17 1 8 14 15
18 6 12 16 9
4 3 10 13 19
11 7 5 0 2 soluble
Taquin 5x4:
14 15 10 1 11
8 7 12 18 4
13 6 16 17 5
0 9 2 19 3 soluble
Taquin 2x3:
1 5
3 4
0 2 insoluble
Taquin 5x4:
16 18 5 1 9
2 3 6 14 15
12 19 13 4 7
11 17 10 8 0 soluble
Taquin 5x4:
19 11 0 17 9
7 16 5 3 1
18 6 13 10 2
14 12 15 4 8 insoluble
Taquin 4x3:
4 6 3 2
7 11 1 0
5 8 9 10 soluble
Taquin 3x5:
10 2 14
5 0 3
4 12 7
11 13 1
8 9 6 soluble
Taquin 4x4:
8 13 3 7
0 2 4 10
12 9 11 1
6 14 15 5 insoluble
Taquin 3x6:
5 0 17
13 7 4
12 15 1
10 6 11
14 8 2
9 3 16 insoluble
Taquin 4x3:
8 1 11 3
9 10 6 7
0 5 2 4 soluble
Taquin 6x5:
8 12 18 13 21 29
24 17 9 22 0 15
6 4 11 2 10 23
5 14 19 16 27 25
1 28 26 7 3 20 insoluble
Taquin 4x6:
18 3 16 13
6 7 19 10
11 4 17 8
12 15 0 22
21 23 20 5
2 9 14 1 insoluble
Taquin 2x6:
3 6
11 8
9 10
2 7
1 5
4 0 soluble
Taquin 5x4:
1 11 6 15 3
5 18 19 4 2
13 14 7 9 8
10 17 12 16 0 insoluble
J'aurais aimé trouver "ailleurs" une fonction "testée" pour me permettre de mieux vérifier les résultats obtenus.
Merci d'avance pour vos propositions.
Bonne lecture ...
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.