Savoir si un Taquin est solluble

Version imprimable

07/12/2008, 17h01
smyley
:salut:

Je me fait un petit taquin et j'ai du mal pour générer quelque chose qui contient une solution. Il s'agit d'un Taquin 4x4 et des fois je n'arrive pas à le résoudre (manuellement). Par exemple à partir de ceci (0 étant la case vide) :

Citation:

11 13 10 1
4 12 2 15
6 0 5 9
3 7 8 14

j'arrive à ceci :

Citation:

1 2 3 4
5 6 7 8
9 10 12 11
13 14 15 0

et là, je ne sais pas comment faire.

Pourtant, sur wikipedia j'ai vu qu'il faut trouver un nombre de permutations pour arriver à la grille valide de la même parité que le nombre d'opérations nécessaire pour bouger le 0 à sa place.
Pour partir de la grille de départ et arriver à une grille correcte, je trouve ces échanges à faire :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 11 <-> 0 9 <-> 0 13 <-> 1 7 <-> 1 15 <-> 1 14 <-> 1 8 <-> 1 6 <-> 1 2 <-> 1 10 <-> 1 5 <-> 1 12 <-> 1 3 <-> 1
C'est bien comme ça ou je dois faire des vrais permutations (de la forme 1 2 4 3 etc.., comme en math quoi).

Donc il y en a 13 et il faut 3 mouvements pour amener le 0 en bas à droite. Donc ça devrais être soluble non ? où est le problème ? (La configuration sur laquelle j'arrive, avec 11 et 12 inversée n'est pas soluble suivant cette règle, mais comment puis-je arriver à un truc insoluble à partir d'un truc soluble ?!)

Idem avec la partie

Citation:

8 10 1 2 14
3 12 0 6
9 7 4 5
13 15 11

Pourtant ça semble coller ...
07/12/2008, 18h45
cedriku

Salut,

ta configuration initiale :
(11, 13, 10, 1, 4, 12, 2, 15, 6, 0, 5, 9, 3, 7, 8, 14)

permutations pour arriver à la solution :

(11, 13, 10, 1, 4, 12, 2, 15, 6, 14, 5, 9, 3, 7, 8, 0) <-> placement du 0 en permutant avec 14
(11, 13, 10, 1, 4, 12, 2, 8, 6, 14, 5, 9, 3, 7, 15, 0) <-> placement du 15 en permutant avec 8
(11, 13, 10, 1, 4, 12, 2, 8, 6, 7, 5, 9, 3, 14, 15, 0) <-> placement du 14 en permutant avec 7
(11, 3, 10, 1, 4, 12, 2, 8, 6, 7, 5, 9, 13, 14, 15, 0) <-> placement du 13 en permutant avec 3
(11, 3, 10, 1, 4, 9, 2, 8, 6, 7, 5, 12, 13, 14, 15, 0)
(5, 3, 10, 1, 4, 9, 2, 8, 6, 7, 11, 12, 13, 14, 15, 0)
(5, 3, 7, 1, 4, 9, 2, 8, 6, 10, 11, 12, 13, 14, 15, 0)
(5, 3, 7, 1, 4, 6, 2, 8, 9, 10, 11, 12, 13, 14, 15, 0)
(5, 3, 2, 1, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0)
(4, 3, 2, 1, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0)
(1, 3, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0)
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0)

Soit 12 permutations et comme tu l'as dit, il faut 3 deplacement pour mettre le 0 ou il faut à partir de la configuration initiale. Donc c'est pas soluble.

As-tu compris pour les permutations ?

PS : J'ai decouvert cette technique à l'instant en lisant l'article sur Wikipedia, si j'ai mal compris merci de l'indiquer :) mais regarde bien l'exemple 3 sur wikipedia, je pense que c'est ca!

Citation:

Envoyé par cedriku

Soit 12 permutations

Pourquoi tu trouves 12 et moi 13 ?!

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
            int _i = 0;
            int _j = 0;
            for (int i = 0; i < 16; i++)
            {
                _i = i / 4;
                _j = i % 4;
 
                while (gameWork[_i, _j].Value != i)
                {
                    Debug.WriteLine(String.Format("{0} <-> {1}", gameWork[_i, _j], i));
                    ExchangeValues(_i, _j, gameWork[_i, _j].Value / 4, gameWork[_i, _j].Value % 4, gameWork);
                    permutationCount++;
                }
            }

Avec ça on devrais avoir les permutations correctes non ?
(ExchangeValues(i,j,k,l,...) échange les cases à la position (i,j) et (k,l))

J'ai essayé de modifier mon code :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
int _i = 0;
            int _j = 0;
            int _k = 0;
 
            for (int i = 1; i < 16; i++)
            {
                /* le 0 sera bien placé à la fin */
                _i = i / 4;
                _j = i % 4;
 
                while (gameWork[_i, _j].Value != 0 && gameWork[_i, _j].Value != (i + 1))
                {
                    _k = gameWork[_i, _j].Value;
 
                    Debug.WriteLine(String.Format("{0} <-> {1}", _k, i + 1));
 
                    ExchangeValues(_i, _j, (_k - 1) / 4, (_k - 1) % 4, gameWork);
                    permutationCount++;
                }
            }

mais j'obtiens :

Citation:

Game :9 3 11 8 6 5 12 10 14 7 15 4 1 13 0 2 .
3 <-> 2
11 <-> 2
15 <-> 2
8 <-> 4
10 <-> 4
7 <-> 4
12 <-> 4
6 <-> 5
14 <-> 9
13 <-> 9
1 <-> 9
2 <-> 16
Permutations : 12
Case vide : 14

mais pourtant le jeu me mène encore vers une solution quasi complète mais avec le 12 et le 11 inversés (donc impossible).

14/12/2008, 15h29
smyley

Bon finalement je me suis débrouillé autrement.
Plutôt que de générer un taquin et ensuite vérifier s'il a une solution, je génère directement un taquin qui en a une.

Si vous voulez essayer (Windows XP+) :
http://www.developpez.net/forums/d65...csharp-taquin/
22/12/2008, 12h51
acx01b

salut

pour vérifier si c'est un taquin soluble (cf wikipedia) :
- tu tries une copie du tableau (16 cases) par exemple avec un tri à bulle, et tu comptes le nombre d'échanges que tu as fait pour le trier
- puis tu ajoutes au nombre d'échange, la distance entre le "blanc" et sa destination (bas droite)

si le taquin n'est pas soluble tu échanges 2 cases différentes de "blanc" pour le rendre soluble
22/12/2008, 14h15
smyley

Dès le départ j'avais essayé Wikipedia, et dès le départ je n'arrivais pas à faire marcher cette technique, mais maintenant vu que ça fonctionne autrement c'est plus un problème.