Niveau algorithmique

Algorithme résolution de puzzle

Posté par
Fuyuhiko 13-02-11 à 16:33

Bonjour,

mes années de math remontent déjà, et je sèche pas mal sur la manière de mettre en place un algo. Je vous expose les faits en espérant un peu d'aide Je précise que je fais ça dans un cadre personnel.

-------------------------------
Imaginons 3 disques imbriqués.

Le disque intérieur est divisé en 8 (de la même façon que les rayons d'une roue de vélo).
Le disque du milieu est divisé en 12.
Le disque extérieur est divisé en 16.

Le but étant de manœuvrer ces disque en les tournant dans un sens ou l'autre pour que le premier rayon de chaque cercle soit aligné avec le premier rayon des autres. Facile. Sauf que seuls 6 déplacements sont autorisés :

Comprendre qu'un déplacement de 1 déplace un rayon sur le rayon suivant, et -1 sur le rayon précédent.

déplacement	disque intérieur	disque milieu	disque extérieur
D1	1	-2	-3
D2	-3	1	-2
D3	-2	-3	1
D4	-1	2	3
D5	3	-1	2
D6	2	3	-1

_{Désolé pour la taille de la table, je n'ai pas trouvé comment la réduire.}

Donc lorsque l'on souhaite tourner le disque intérieur dans le sens horaire avec D1, le disque du milieu tourne de 2 dans le sens anti-horaire, et le cercle extérieur de 3 dans le sens anti-horaire. Et comme c'est un puzzle, l'initialisation est aléatoire.

A défaut de trouver un algo de résolution, je suis passé par la méthode de "brute force" ^^. J'ai calculé toute les combinaisons possibles, en montant jusqu'à un enchaînement de 10 boutons (le PC a mouliné pendant plusieurs heures

). Malheureusement, je n'obtiens au final que 384 combinaisons uniques pour résoudre ce puzzle, en tenant bien-sûr compte de tous les doublons dues à plusieurs rotations de cercle ou à une rotation inverse équivalente d'un des disques. Peut-être ai-je déjà le nombre total de combinaisons possibles avec ces déplacements, mais j'en doute.

Je n'ai peut-être aussi pas eu les bon termes pour décrire cette recherche dans notre moteur de recherche favori

Si certains sont fan de rubik's cube, je pense qu'ils pourront m'aider

Pour ceux qui souhaitent s'y pencher mais pour qui l'imbrication des disques n'est pas claire, envoyez moi un message privé, je vous donnerai le lien de mon truc actuel.

Merci d'avance

Posté par re : Algorithme résolution de puzzle 13-02-11 à 17:04

Je viens de voir qu'il n'est pas possible d'éditer mon message, ni de communiquer par message privé, alors voici l'exemple que j'ai fais : . Les rayons à aligner se trouvent entre les flammes, et doivent revenir en position initiale 1 1 1.

Exemple de données : intérieur 7, milieu 8, extérieur 8

Désolé s'il persiste quelques bugs dans le maniement des disques, c'est en cours de dev, et utilisez autre chose que Internet Explorer si vous voulez des animations fluides IE accepte le SVG mais n'est pas très sympa dès qu'il s'agit d'animations.

Posté par re : Algorithme résolution de puzzle 14-02-11 à 00:36

Bonjour,

Je ne sais pas comment tu as procédé mais à première vue, je ferais comme ceci :

Je note $(u_0,v_0,w_0)$ les positions initiales des disques intérieur,milieu et extérieur.
Je note $D_k(i)$ la permutation liée au disque i (avec intérieur = 1, milieu =2, extérieur=3)
Par exemple $D_3(2)=-3$

Voilà comme j'écrirai ça : au bout de $\Bigsum_{k=1}^6 a_k$ séquences de mouvements, les disques sont en positions :

$(u_0+\Bigsum_{k=1}^6 a_kD_k(1),v_0+\Bigsum_{k=1}^6 a_kD_k(2),w_0+\Bigsum_{k=1}^6 a_kD_k(3))$

On cherche alors à résoudre :

$(u_0+\Bigsum_{k=1}^6 a_kD_k(1),v_0+\Bigsum_{k=1}^6 a_kD_k(2),w_0+\Bigsum_{k=1}^6 a_kD_k(3))=(1,1,1)$

En renommant les $a_k$ par les lettres de l'alphabet (a1=a,a2=b...a6=f) le système est équivalent à :

$2c+6d+6e-3f=1+v_0-u_0-w_0$
$8b+5c+7e-2f=w_0-1-3(1-u_0)$
$a-3b-2c-d-3e+f=1-u_0}$

Normalement ça ne sert à rien d'effectuer plus de 48 fois la même séquence car cela revient à ne rien faire.

On peut donc chercher à résoudre la première ligne on faisant varier chaque inconnues de 0 à 48, puis chaque solution trouvée donne la valeur de b grâce à la deuxième ligne, puis la valeur de a grâce à la troisième ligne (sous les conditions a>=0 et b>=0 évidemment).

Ceci nécessite donc en gros pour la première ligne $48^4$ opérations donc environ $10^7$ .

Cette technique devrait sortir toutes les solutions au problème pour une configuration initiale donnée, mais j'avoue que pour un tel nombre d'opérations je ne sais pas si ça met du temps.

Ca reste de la force brute, mais cette fois ci toutes les solutions sont sorties, (et pas seulement celles en moins de 10 séquences) et la solution est donnée.

Je ne sais pas si j'ai été très clair, dis moi si ça te convient ou pas
(Et c'est quand même bien moins complexe que le Rubik's cube )

Remarque : J'ai peut être fait une erreur dans le système équivalent, mais l'idée est là

Posté par re : Algorithme résolution de puzzle 14-02-11 à 01:29

Salut Plouf,

merci pour ta réponse Tu as été très claire (le temps pour moi de me remettre les notations mathématiques en tête ^^). En fin d'après midi j'ai croisé un ami à qui j'ai parlé de mon problème, et il m'a parlé de mettre ça sous forme de matrice, puis d'éliminer les inconnues. Il m'a prévenu d'avance que pour 6 inconnues il faudrait 6 équations pour bien faire ^^. J'ai alors gratté cette approche, un peu de la même manière que toi, et je me suis rendu compte d'un truc "bête" (j'ai peiné quelques heures avant) :
Pour effectuer un déplacement, on ne se sert que de la moitié des boutons au maximum. Je m'explique : si j'utilise des mouvements D1, en restant logique, je ne vais jamais utiliser un mouvement D4 qui annule un mouvement D1 et me ferait faire 2 coups pour rien, sachant qu'à la fin tous les déplacements s'additionnent. On a donc D1 = -D4, D2 = -D5, D3 = -D6.

Ma solution recoupe la tienne, mais j'ai beaucoup moins de valeurs à tester maintenant
J'ai fini par résoudre mon problème en utilisant Gauss Jordan et la matrice suivante :

{ 1, -3,-2, i}
{ -2, 1, -3, j}
{ -3, -2, 1, k}

où i, j et k représentent le nombre de mouvements D à effectuer. Au final, si pour "i" j'obtiens "-2", c'est que "i" représente D4 et non D1 Pour trouver un déplacement correct, on doit faire toutes les combinaisons de (i,j,k) [horaire/anti-horaire, soit 8 combinaisons max] jusqu'à obtenir des valeurs entières en résultat (rapide avec un algo).

Je pense que ça peut faire un bon exo pour un cours

Merci d'avoir pris le temps de me répondre, et bonne soirée !

Ps: Rha ces disques et ces rotations ... ils m'en ont fait baver ce weekend ^^

Posté par re : Algorithme résolution de puzzle 14-02-11 à 13:22

Effectivement en cherchant quelque chose de plus rapide je me suis rendu compte que D1=-D4 etc...
Là où par contre je ne suis pas d'accord avec ton ami, c'est dès qu'il dit que pour trouver n inconnues, il faut n équations. Ceci n'est pas obligatoire car on cherche les solutions dans $\mathbb{N}$ . J'ai une solution qui est donc assez rapide et peut presque se faire "à la main", je te la propose au cas où

Sous forme de matrice on cherche effectivement à résoudre le système :

$\text{+1 -3 -2}\\\text{-2 +1 -3}\\\text{-3 -2 +1}\)$i\\j\\k$=\(x\\y\\z$

avec $(x,y,z)=(1-u_0,1-v_0,1-w_0)$ et $(i,j,k)\in [|0,48|]$

Il ne sert à rien de chercher des valeurs négatives de i,j ou k, car par exemple 46i = -2i

Les formules de Cramer permettent d'exprimer les solutions de ce système et donnent donc :

$\{-52i=-5x+7y+11z\\-52j=11x-5y+7z\\-52k=7x+11y-5z$

Les deux premières lignes donnent : $-5i-7j=x+2z$

Or on sait entièrement résoudre cette équation ! (c'est une équation diophantienne)
Pr exemple si $u_0=2$ et $w_0=1$ , l'équation a pour solutions : $\{7p+3,-5p-2),p\in\mathbb{N}\}$

La condition $x\ge 0$ montre qu'aucun p ne convient donc il n'y a pas de solution, quelque soit la position initiale du disque du milieu ! (Sauf erreur )

Tu comprends le principe ? La résolution se fait sans problème à la main jusque là.
Si on avait trouvé des solutions qui conviennent, on aurait réinjecter ces solutions dans le système initial (moins une des deux premières lignes inutile), et on en tirait la valeur de k, en vérifiant qu'il est entier.

L'algorithme de résolution est ici très rapide !

Posté par re : Algorithme résolution de puzzle 14-02-11 à 20:35

Petite correction à ce que j'ai dit :

Ne mettons pas de conditions sur (i,j,k).
Les solutions de l'équation diophantienne précédente sont en fait (i,j)=(7p+2,-5p+3)
Ce qui nous donne en reportant : y=-52p+2 et k=11p-1.

La position initiale étant la même modulo 12, on cherche les valeurs possibles de y mod 12.
Les seules valeurs possibles sont 2, 6 et 10 respectivement atteinte pour p=0,1 et 2.

Avec comme position initiale u0=5 et w0=13 les seuls cas solubles sont donc :

v0=3   et la solution est alors $D_1^2D_2^3D_6$ car -D3=D6
v0=7   et la solution est alors $D_1^{16}D_5^7D_3^{20}$
v0=11  et la solution est alors $D_1^{9}D_5^2D_3^{10}$

Et les expressions devraient se simplifier

Voilà, tout se résout à la main finalement