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) :
j'arrive à ceci :11 13 10 1
4 12 2 15
6 0 5 9
3 7 8 14
et là, je ne sais pas comment faire.1 2 3 4
5 6 7 8
9 10 12 11
13 14 15 0
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 :
C'est bien comme ça ou je dois faire des vrais permutations (de la forme 1 2 4 3 etc.., comme en math quoi).
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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
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
Pourtant ça semble coller ...8 10 1 2 14
3 12 0 6
9 7 4 5
13 15 11
Partager