Taquin en désordre
Description
Bonjour
Voici un complément à mon article "Taquin insoluble ?" que j'ai déposé il y a quelques jours.
En utilisant la notion de "coefficient de désordre", on peut éviter de travailler sur une copie du jeu.
Le "coefficient de désordre" D, correspond au nombre de fois qu'un numéro plus petit est placé après lui-même:
Malheureusement, les exemples avec le coefficient de désordre que j'ai repérés ne concernent que des situations où la position vide est déjà à sa place finale.
Mais avec un peu de persévérance, j'ai réussi de trouver comment lier les dimensions du jeu, la position de la case vide et le coefficient de désordre pour déterminer si le jeu choisi est soluble ou non.
Il semble plus simple de calculer ce coefficient par rapport à la situation
{0,1,2,3,...,nC*nL-1} plutôt que {1,2,3,...,nC*nL-1,0}.
La seconde partie teste trois "façons" de déterminer si un jeu est insoluble:
a) Test correspondant à l'article "Taquin insoluble ?".
b) Test avec calcul explicite du coefficient de désordre D.
c) Test avec la fonction bool TaquinInsoluble(int nC, int nL, int *jeu).
Voici l'output du programme contenu dans le seul fichier TaquinDesordre.cpp:
Les codes présentés ici nous permettent d'éviter de faire une copie de travail des jeux analysés, mais la performance est toujours quadratique par rapport au nombre de cases: O((nC*nL)²).
Compléments d'information sur coefficient de désordre: Taquin (Uni P M Curie) et Jeu de Taquin (Nombres).
Bonne lecture ...
Voici un complément à mon article "Taquin insoluble ?" que j'ai déposé il y a quelques jours.
En utilisant la notion de "coefficient de désordre", on peut éviter de travailler sur une copie du jeu.
Le "coefficient de désordre" D, correspond au nombre de fois qu'un numéro plus petit est placé après lui-même:
int CoefDesordre(int nC, int nL, int *jeu) {
int D = 0, n = nC*nL - 1;
for (int i = 0; i < n; ++i)
for (int j = i+1; j <= n; ++j)
if (jeu[j] < jeu[i]) ++D;
return D;
} // Le contenu de l'array 'int *jeu' n'est pas modifié
Malheureusement, les exemples avec le coefficient de désordre que j'ai repérés ne concernent que des situations où la position vide est déjà à sa place finale.
Mais avec un peu de persévérance, j'ai réussi de trouver comment lier les dimensions du jeu, la position de la case vide et le coefficient de désordre pour déterminer si le jeu choisi est soluble ou non.
Il semble plus simple de calculer ce coefficient par rapport à la situation
{0,1,2,3,...,nC*nL-1} plutôt que {1,2,3,...,nC*nL-1,0}.
bool TaquinInsoluble(int nC, int nL, int *jeu) { // avec coefficient de désordre
int D = 0, n = nC*nL - 1, dV = 0, q;
for (int i = 0; i < n; ++i) {
if ((q = jeu[i])==0) dV = n-i; // déplacements de la case vide
for (int j = i+1; j <= n; ++j)
if (jeu[j] < q) ++D;
}
return 1&(n + dV%nC + dV/nC + D);
} // Le contenu de l'array 'int *jeu' n'est pas modifié
La première partie de l'output du fichier "Tests avec initialisation canonique {0,1,2,3,...,nC*nL-1}" montre qu'il faut n = nC*nL - 1 permutations pour obtenir la solution finale {1,2,3,...,NC*NL-1,0}.
La seconde partie teste trois "façons" de déterminer si un jeu est insoluble:
a) Test correspondant à l'article "Taquin insoluble ?".
b) Test avec calcul explicite du coefficient de désordre D.
c) Test avec la fonction bool TaquinInsoluble(int nC, int nL, int *jeu).
Voici l'output du programme contenu dans le seul fichier TaquinDesordre.cpp:
Tests avec initialisation canonique {0,1,2,3,...,nC*nL-1}:
=========================================================
Taquin 2x2:
0 1
2 3 nC*nL = 4, movVide = 2, nPerm = 3, insoluble
Taquin 2x3:
0 1
2 3
4 5 nC*nL = 6, movVide = 3, nPerm = 5, soluble
Taquin 2x4:
0 1
2 3
4 5
6 7 nC*nL = 8, movVide = 4, nPerm = 7, insoluble
Taquin 2x5:
0 1
2 3
4 5
6 7
8 9 nC*nL = 10, movVide = 5, nPerm = 9, soluble
Taquin 2x6:
0 1
2 3
4 5
6 7
8 9
10 11 nC*nL = 12, movVide = 6, nPerm = 11, insoluble
Taquin 3x2:
0 1 2
3 4 5 nC*nL = 6, movVide = 3, nPerm = 5, soluble
Taquin 3x3:
0 1 2
3 4 5
6 7 8 nC*nL = 9, movVide = 4, nPerm = 8, soluble
Taquin 3x4:
0 1 2
3 4 5
6 7 8
9 10 11 nC*nL = 12, movVide = 5, nPerm = 11, soluble
Taquin 3x5:
0 1 2
3 4 5
6 7 8
9 10 11
12 13 14 nC*nL = 15, movVide = 6, nPerm = 14, soluble
Taquin 3x6:
0 1 2
3 4 5
6 7 8
9 10 11
12 13 14
15 16 17 nC*nL = 18, movVide = 7, nPerm = 17, soluble
Taquin 4x2:
0 1 2 3
4 5 6 7 nC*nL = 8, movVide = 4, nPerm = 7, insoluble
Taquin 4x3:
0 1 2 3
4 5 6 7
8 9 10 11 nC*nL = 12, movVide = 5, nPerm = 11, soluble
Taquin 4x4:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15 nC*nL = 16, movVide = 6, nPerm = 15, insoluble
Taquin 4x5:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19 nC*nL = 20, movVide = 7, nPerm = 19, soluble
Taquin 4x6:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
20 21 22 23 nC*nL = 24, movVide = 8, nPerm = 23, insoluble
Taquin 5x2:
0 1 2 3 4
5 6 7 8 9 nC*nL = 10, movVide = 5, nPerm = 9, soluble
Taquin 5x3:
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14 nC*nL = 15, movVide = 6, nPerm = 14, soluble
Taquin 5x4:
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19 nC*nL = 20, movVide = 7, nPerm = 19, soluble
Taquin 5x5:
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24 nC*nL = 25, movVide = 8, nPerm = 24, soluble
Taquin 5x6:
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
25 26 27 28 29 nC*nL = 30, movVide = 9, nPerm = 29, soluble
Taquin 6x2:
0 1 2 3 4 5
6 7 8 9 10 11 nC*nL = 12, movVide = 6, nPerm = 11, insoluble
Taquin 6x3:
0 1 2 3 4 5
6 7 8 9 10 11
12 13 14 15 16 17 nC*nL = 18, movVide = 7, nPerm = 17, soluble
Taquin 6x4:
0 1 2 3 4 5
6 7 8 9 10 11
12 13 14 15 16 17
18 19 20 21 22 23 nC*nL = 24, movVide = 8, nPerm = 23, insoluble
Taquin 6x5:
0 1 2 3 4 5
6 7 8 9 10 11
12 13 14 15 16 17
18 19 20 21 22 23
24 25 26 27 28 29 nC*nL = 30, movVide = 9, nPerm = 29, soluble
Taquin 6x6:
0 1 2 3 4 5
6 7 8 9 10 11
12 13 14 15 16 17
18 19 20 21 22 23
24 25 26 27 28 29
30 31 32 33 34 35 nC*nL = 36, movVide = 10, nPerm = 35, insoluble
100 tests des 3 methodes avec dimensions et initialisation aleatoires:
=====================================================================
Compare taquin 3x4:
7 0 2
11 1 10
3 5 8
6 9 4 D = 27, sol, Sol, Soluble
Compare taquin 3x3:
5 7 1
6 8 3
2 4 0 D = 24, sol, Sol, Soluble
Compare taquin 4x3:
1 4 6 3
8 7 2 11
0 10 5 9 D = 24, sol, Sol, Soluble
Compare 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 D = 234, sol, Sol, Soluble
Compare taquin 2x2:
1 0
3 2 D = 2, sol, Sol, Soluble
Compare taquin 3x5:
13 9 2
6 12 8
7 10 3
1 0 5
4 14 11 D = 59, insol, Insol, Insoluble
Compare taquin 4x5:
18 3 11 4
0 12 8 10
5 19 17 14
6 16 7 2
9 1 13 15 D = 92, insol, Insol, Insoluble
Compare taquin 4x5:
5 4 13 8
18 10 14 7
0 16 17 19
15 3 2 9
6 1 11 12 D = 98, sol, Sol, Soluble
Compare taquin 4x4:
15 1 8 14
2 5 7 0
9 10 13 12
6 11 3 4 D = 62, insol, Insol, Insoluble
Compare taquin 2x3:
0 2
1 3
4 5 D = 1, insol, Insol, Insoluble
Compare 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 D = 155, insol, Insol, Insoluble
Compare 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 D = 156, insol, Insol, Insoluble
Compare 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 D = 158, insol, Insol, Insoluble
Compare taquin 3x2:
2 0 5
1 4 3 D = 6, insol, Insol, Insoluble
Compare taquin 2x5:
1 9
2 8
7 0
4 3
6 5 D = 23, sol, Sol, Soluble
Compare taquin 5x4:
9 6 19 14 5
3 4 18 2 17
8 13 7 12 16
0 11 15 1 10 D = 103, sol, Sol, Soluble
Compare taquin 2x4:
1 7
4 2
5 0
6 3 D = 14, sol, Sol, Soluble
Compare taquin 6x3:
3 11 7 14 13 5
6 17 10 0 4 15
2 16 12 9 1 8 D = 81, insol, Insol, Insoluble
Compare taquin 3x4:
0 10 3
1 8 2
9 5 11
4 7 6 D = 25, insol, Insol, Insoluble
Compare taquin 4x2:
3 7 5 1
2 0 6 4 D = 16, insol, Insol, Insoluble
Compare taquin 2x2:
3 0
2 1 D = 4, sol, Sol, Soluble
Compare taquin 2x5:
6 5
4 1
7 2
0 3
8 9 D = 20, insol, Insol, Insoluble
Compare taquin 3x2:
5 1 2
0 4 3 D = 8, insol, Insol, Insoluble
Compare 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 D = 212, insol, Insol, Insoluble
Compare taquin 4x5:
5 16 9 19
14 7 0 18
3 1 4 17
12 6 8 15
2 11 10 13 D = 97, sol, Sol, Soluble
Compare taquin 4x2:
7 1 5 6
2 4 0 3 D = 19, insol, Insol, Insoluble
Compare taquin 2x4:
4 5
3 2
0 6
1 7 D = 14, insol, Insol, Insoluble
Compare taquin 2x3:
3 5
1 0
4 2 D = 9, insol, Insol, Insoluble
Compare 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 D = 244, insol, Insol, Insoluble
Compare 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 D = 131, insol, Insol, Insoluble
Compare 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 D = 249, insol, Insol, Insoluble
Compare taquin 2x3:
4 5
1 0
3 2 D = 10, sol, Sol, Soluble
Compare taquin 2x3:
2 0
4 5
3 1 D = 7, sol, Sol, Soluble
Compare taquin 3x6:
1 11 12
16 2 0
10 14 15
5 6 17
8 3 13
4 9 7 D = 75, sol, Sol, Soluble
Compare 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 D = 169, sol, Sol, Soluble
Compare taquin 2x3:
0 5
3 4
1 2 D = 8, sol, Sol, Soluble
Compare taquin 3x5:
14 12 7
13 0 3
1 2 5
6 4 9
11 10 8 D = 52, sol, Sol, Soluble
Compare taquin 4x4:
12 7 6 9
15 8 10 1
13 0 4 5
14 11 2 3 D = 71, insol, Insol, Insoluble
Compare taquin 4x2:
4 1 6 2
5 7 0 3 D = 14, sol, Sol, Soluble
Compare taquin 2x2:
3 0
1 2 D = 3, insol, Insol, Insoluble
Compare 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 D = 242, sol, Sol, Soluble
Compare 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 D = 122, insol, Insol, Insoluble
Compare taquin 3x6:
13 3 17
15 11 0
16 12 14
1 10 2
9 4 6
5 7 8 D = 96, insol, Insol, Insoluble
Compare taquin 3x5:
1 13 6
0 10 2
11 12 9
4 7 5
14 3 8 D = 48, insol, Insol, Insoluble
Compare taquin 4x4:
7 3 12 14
11 9 6 13
5 8 10 0
1 2 4 15 D = 71, insol, Insol, Insoluble
Compare 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 D = 113, sol, Sol, Soluble
Compare 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 D = 137, insol, Insol, Insoluble
Compare taquin 5x4:
1 3 0 9 14
2 4 13 6 5
17 16 8 12 11
18 7 15 19 10 D = 51, insol, Insol, Insoluble
Compare taquin 4x2:
4 5 7 6
0 3 1 2 D = 19, insol, Insol, Insoluble
Compare taquin 2x2:
2 3
1 0 D = 5, sol, Sol, Soluble
Compare taquin 3x4:
7 11 5
4 9 3
1 2 10
8 6 0 D = 43, sol, Sol, Soluble
Compare 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 D = 238, insol, Insol, Insoluble
Compare taquin 2x3:
2 3
1 5
0 4 D = 7, insol, Insol, Insoluble
Compare taquin 4x5:
13 5 3 8
16 7 14 18
15 11 2 9
1 10 12 19
6 4 0 17 D = 100, sol, Sol, Soluble
Compare taquin 2x6:
4 11
10 2
5 9
7 1
0 6
3 8 D = 40, insol, Insol, Insoluble
Compare taquin 2x6:
5 7
4 6
8 10
2 0
9 1
11 3 D = 33, sol, Sol, Soluble
Compare 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 D = 133, insol, Insol, Insoluble
Compare 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 D = 192, sol, Sol, Soluble
Compare taquin 4x4:
9 2 1 8
15 4 12 3
11 5 14 10
6 7 0 13 D = 55, insol, Insol, Insoluble
Compare taquin 5x3:
2 1 13 7 3
0 14 12 8 9
11 10 6 5 4 D = 51, sol, Sol, Soluble
Compare 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 D = 230, insol, Insol, Insoluble
Compare taquin 5x4:
9 18 17 13 8
14 19 12 15 6
2 10 5 11 7
4 0 3 1 16 D = 137, insol, Insol, Insoluble
Compare taquin 6x3:
16 10 15 7 0 5
11 3 12 4 2 6
14 8 17 1 13 9 D = 79, insol, Insol, Insoluble
Compare 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 D = 398, insol, Insol, Insoluble
Compare taquin 6x2:
0 4 10 5 2 9
3 8 6 7 11 1 D = 27, sol, Sol, Soluble
Compare taquin 2x6:
5 9
3 1
11 7
4 2
0 10
8 6 D = 34, insol, Insol, Insoluble
Compare taquin 5x3:
7 9 3 12 11
6 13 14 2 5
1 4 0 8 10 D = 61, insol, Insol, Insoluble
Compare taquin 2x2:
1 2
3 0 D = 3, sol, Sol, Soluble
Compare taquin 4x4:
11 7 9 0
13 6 5 1
15 10 12 4
14 8 3 2 D = 67, insol, Insol, Insoluble
Compare taquin 2x5:
3 7
1 0
8 5
9 4
2 6 D = 20, sol, Sol, Soluble
Compare taquin 2x4:
3 1
6 7
4 0
2 5 D = 14, sol, Sol, Soluble
Compare taquin 4x3:
0 1 11 3
7 2 6 8
10 4 5 9 D = 21, insol, Insol, Insoluble
Compare taquin 2x6:
2 1
6 3
11 5
10 4
7 0
9 8 D = 25, insol, Insol, Insoluble
Compare taquin 4x3:
0 6 5 8
10 4 1 11
9 3 7 2 D = 32, sol, Sol, Soluble
Compare taquin 5x3:
13 11 14 2 4
10 8 12 3 7
9 0 6 1 5 D = 74, insol, Insol, Insoluble
Compare taquin 4x2:
6 3 2 0
1 7 5 4 D = 14, sol, Sol, Soluble
Compare taquin 2x5:
0 2
6 8
4 5
7 1
9 3 D = 17, insol, Insol, Insoluble
Compare taquin 3x4:
11 0 6
4 2 3
10 5 7
1 8 9 D = 28, insol, Insol, Insoluble
Compare taquin 6x3:
0 10 14 8 1 4
15 16 9 11 13 12
6 17 2 7 5 3 D = 79, insol, Insol, Insoluble
Compare taquin 2x2:
3 0
1 2 D = 3, insol, Insol, Insoluble
Compare taquin 2x5:
6 5
9 1
2 4
3 7
0 8 D = 24, sol, Sol, Soluble
Compare taquin 4x5:
7 1 16 4
8 11 6 5
19 15 14 0
12 13 18 2
3 10 9 17 D = 84, insol, Insol, Insoluble
Compare taquin 5x3:
11 1 2 0 4
13 10 7 9 3
5 6 12 8 14 D = 36, insol, Insol, Insoluble
Compare taquin 2x5:
7 4
0 1
2 9
8 6
5 3 D = 21, sol, Sol, Soluble
Compare taquin 6x2:
11 6 5 9 4 3
1 8 10 7 0 2 D = 45, insol, Insol, Insoluble
Compare taquin 4x3:
11 6 8 1
9 2 0 7
10 4 3 5 D = 39, sol, Sol, Soluble
Compare taquin 5x4:
17 1 8 14 15
18 6 12 16 9
4 3 10 13 19
11 7 5 0 2 D = 120, sol, Sol, Soluble
Compare taquin 5x4:
14 15 10 1 11
8 7 12 18 4
13 6 16 17 5
0 9 2 19 3 D = 107, sol, Sol, Soluble
Compare taquin 2x3:
1 5
3 4
0 2 D = 9, insol, Insol, Insoluble
Compare taquin 5x4:
16 18 5 1 9
2 3 6 14 15
12 19 13 4 7
11 17 10 8 0 D = 97, sol, Sol, Soluble
Compare taquin 5x4:
19 11 0 17 9
7 16 5 3 1
18 6 13 10 2
14 12 15 4 8 D = 103, insol, Insol, Insoluble
Compare taquin 4x3:
4 6 3 2
7 11 1 0
5 8 9 10 D = 24, sol, Sol, Soluble
Compare taquin 3x5:
10 2 14
5 0 3
4 12 7
11 13 1
8 9 6 D = 48, sol, Sol, Soluble
Compare taquin 4x4:
8 13 3 7
0 2 4 10
12 9 11 1
6 14 15 5 D = 49, insol, Insol, Insoluble
Compare taquin 3x6:
5 0 17
13 7 4
12 15 1
10 6 11
14 8 2
9 3 16 D = 74, insol, Insol, Insoluble
Compare taquin 4x3:
8 1 11 3
9 10 6 7
0 5 2 4 D = 42, sol, Sol, Soluble
Compare 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 D = 210, insol, Insol, Insoluble
Compare 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 D = 141, insol, Insol, Insoluble
Compare taquin 2x6:
3 6
11 8
9 10
2 7
1 5
4 0 D = 45, sol, Sol, Soluble
Compare taquin 5x4:
1 11 6 15 3
5 18 19 4 2
13 14 7 9 8
10 17 12 16 0 D = 82, insol, Insol, Insoluble
Les codes présentés ici nous permettent d'éviter de faire une copie de travail des jeux analysés, mais la performance est toujours quadratique par rapport au nombre de cases: O((nC*nL)²).
Compléments d'information sur coefficient de désordre: Taquin (Uni P M Curie) et Jeu de Taquin (Nombres).
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.