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) :
11 13 10 1
4 12 2 15
6 0 5 9
3 7 8 14
j'arrive à ceci :
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 : 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
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
8 10 1 2 14
3 12 0 6
9 7 4 5
13 15 11
Pourtant ça semble coller ...