Résolution systématique du carré glissant.

[invitedf667161]

Nous avons tous joué dans notre jeunesse à ce petit jeu qui consiste à recomposer une image dessinée sur un carré découpé en plusieurs blocs, souvent neuf blocs, qui peuvent bouger grace à un bloc vide.

Notons de manière évidente les cases du carré de 1 à 9 en considérant que la neuvième est la case vide en position initiale.

1-2-3
4-5-6
7-8-9

Il s'agit donc à partir d'une certaine position de revenir à cette position initiale.

Mais attention pas n'importe comment, physiquement seuls sont autorisées les transpositions suivantes :
(12) , (23) , (14) , (25) , (36) , (45) , (56) , (47) , (58) , (69) , (78) , (89).

De plus on ne peut, physiquement toujours, pas les composer dans n'importe quel ordre : la composition (98)°(12) à partir de la position initiale est par exemple proscrite!

On peut donner un exemple:
On me donne le carré "mélangé", par exemple comme cela :

9-5-4
7-6-2
1-3-8

Il s'agit pour moi d'exprimer l'inverse de la permutation (198347)°(256) seulement à l'aide des transpositions sus-citées bien agencées.
Je ne sais pas si cela est possible vu que j'ai pris cet exemple au hasard!

En effet une des premières observationsà faire est de dire que toutes les positions ne peuvent être atteintes avec ces seules transpositions. Pour s'en convaincre, prendre un carré 2*2.
Si la position initiale est

1-2
3-4

avec le vide en 4, il n'est pas possible d'atteinre la position

1-3
2-4

De là à penser qu'il n'y a que deux classes d'équivalence de positions "atteignables", il n'y a qu'un pas.
Je n'ai pas réussi à montrer cela, mais je crois que c'est faisable.


Bref, le but de ce sujet est de vous exposer le problème et de vous permettre de vous exprimer si vous aviez une idée concernant la résolution de ce petit jeu.
-----

[moijdikssékool]

(0 est la case vide)

1-2
3-0

avec le vide en 4, il n'est pas possible d'atteinre la position

1-3
2-0

ah si c'est possible:

1-2-4
3-0-5
6-7-8

(je ne sais si cette position est possible, j'insères ton carré dans un carré 3*3)

1-2-4
3-5-0
6-7-8

1-2-0
3-5-4
6-7-8

1-0-2
3-5-4
6-7-8

1-5-2
3-0-4
6-7-8

1-5-2
0-3-4
6-7-8

1-5-2
0-3-4
6-7-8

1-5-2
6-3-4
0-7-8

1-5-2
6-3-4
7-0-8

1-5-2
6-3-4
7-8-0

1-5-2
6-3-0
7-8-4

1-5-0
6-3-2
7-8-4

1-0-5
6-3-2
7-8-4

1-3-5
6-0-2
7-8-4

1-3-5
6-2-0
7-8-4

1-3-5
6-2-4
7-8-0

1-3-5
6-2-4
7-0-8

1-3-5
6-2-4
0-7-8

1-3-5
0-2-4
6-7-8

1-3-5
2-0-4
6-7-8

d'où

1-3
2-0

[invitec314d025]

En faisant des rechrches sur "Sam Loyd" sur internet, tu devrais trouver les réponses à tes questions.

[fragman]

moijdikssékool, tu as du mal comprendre :
GuYem parlait d'un carré 2x2 et tu as donné ta solution dans un carré 3x3.

C'est comme si tu devais résoudre x²=-1 dans R et que tu donnes comme solutions x=i et x=-i

[A voir en vidéo sur Futura]

[inviteea0d596d]

le jeu que tu viens d'exposer s'appelle le Taquin

[invitedf667161]

Merci moijdiksekool de t'être penché sur mon problème!
En effet, je voulais juste donner un contre exemple sur un carré 2*2 du fait que toutes les positions ne sont pas atteignables.
Evidemment si tu plonges mon carré 2*2 dans un 3*3, ça pourra marcher mais ce n'est pas le problème.

Matthias : je chercherai ce qu'a fait ce brave monsieur.
Cependant mon but n'est pas de regarder ce que les autres ont fait; je me doute bien qu'il y en a qui ont déjà réussi à résoudre ce jeu.
Je voudrais voir par moi-même, et avec votre aide, ce qu'il est possible que nous trouvions

[invitedf667161]

Alors quelqu'un aurait une idée pour faire avancer le schmilblick?

[invite4e79ea66]

Salut

C'est comme si tu devais résoudre x²=-1 dans R et que tu donnes comme solutions x=i et x=-i

il est impossible à ma connaissance de dire que l'on veut résoudre dans R x²=-1 ce n'est que dans C.Mais je me trompe peut être ou plus simplement je n'ai pas compris ton message?
Amicalement chouket

[invitedf667161]

Salut

il est impossible à ma connaissance de dire que l'on veut résoudre dans R x²=-1 ce n'est que dans C.Mais je me trompe peut être ou plus simplement je n'ai pas compris ton message?
Amicalement chouket

On peut trés bien te demander X^2=-1 dans R, dans ce cas la réponse est qu'il n'y a pas de solution.
Le parallèle avec mon problème, c'est que tu ne peux pas passer de

1 2
3 0

à

1 3
2 0

sur un carré 2*2. Cependant si tu plonges ca carré 2*2 dans un 3*3, comme l'a fait moijdiksékool, alors c'est possible.
Tout comme quand tu plonges R dans C, alors l'équation X^=-1 a des solutions.