Comment résoudre un taquin

Bonjour

Je bloque pour la résolution du jeu du taquin...
Pour ceux qui ne savent pas ce que c'est exactement, c'est le jeu où une image est composée en petites images placées dans le désordre et il faut les déplacer pour reconstituer l'image originale.

Bref, je vois comment faire en théorie. Par exemple, pour un taquin en 4*4, l'idée est de résoudre les deux premières lignes. Puis de résoudre les deux dernières en colonnes de gauche à droite.

Mais comment programmer ça? J'ai déjà visité pas mal de sites Internet qui donnent une explication trop théorique (comme celle que je viens de faire ci-dessus). Je voudrais un algorithme (analyse descentente) mais je n'arrive pas trop à gérer tout ça.

Il parait que certains algos comme le IDA* (tiré du A*) permettent de le faire (j'ai vu ça sur une page Internet de l'Ecole Plytechnique) mais comme j'ai pas (encore) vu ce genre d'algo en cours, c'est un peu compliqué...
Est-on obligé de passer par là? Je suppose que oui...

Je programme en C même si, niveau algo, ça ne change pas grand chose.
J'ai un tableau de structure contenant la variable X qui donne la position où doit être l'image au final et également une variable Y qui donne position courante de l'image.
A chaque déplacement, je modifie l'indice Y. Donc le but est de placer l'image en partant de la position Y pour aller à la position X.

Nas'

Bonjour,
je n'ai jamais programmé le taquin, mais j'imagine que le principe est le suivant :

Pour ce jeu, tu as au maximum 4 mouvements possibles (et moins si tu te trouves contre une paroi)
L'idée serait donc de construire un arbre des positions.
Un noeud représente une "position", et donc chaque noeud aurait au maximum 4 fils correspondant aux 4 mouvements possibles.
Pour résoudre le jeu du taquin, il faudrait donc parcourir cet arbre en largeur, et comparer la "position" courante avec la position gagnante.
Si on ne trouve pas la position gagnante, on construit le niveau inférieur de l'arbre (encore une position).

Ca, c'est l'algo de base, parce que j'imagine que tu pourras "couper" ton arbre, c'est à dire eviter les branches du style je bouge a droite, je bouge à gauche etc ... ce qui mene à une boucle et pas à la solution.
Ceci devrait bien améliorer l'algo, mais déjà, essaie peut-être sans.

Voilà, j'espère que je ne t'ai pas embrouillé. Sans t'apporter la solution, ça te donnera peut-être des pistes.
a+

Tu as effectivement le principe.
Pour le résoudre j'ai utilisé ce principe:
Les case sont numérotées 1 => l * c -1 (j'utilise un taquin de L lignes et c colonnes) -1 à cause de la cases vide.
Je mélange les cases (attention tous les mélanges ne sont pas corrects, ils ne donnent pas forcément à la fin un taquin bien ordonné ).
Je range les L-2 premières lignes : le principe (absolument pas optimisé)que j'ai utilisé est de positionner la case à ranger en un premier temps complètement à droite puis à l'amener par des déplacements à la bonne place (pour les deux dernières il faut les déplacer ensemble). Une case bien rangée est marquée pour qu'elle ne soit plus dérangée.
Pour les deux dernières lignes, effectivement il faut travailler par colonnes, même principe, je place les deux cases à ranger sur la dernière colonne à droite (la case qui est à la dernière ligne en haut et l'autre en bas, puis je déplace les deux cases en même temps. Pour les 3 dernières, si je me souviens bien, il faut simplement effectuer une rotation de 1 ou 2 coups.

Je n'ai pas utilisé d'arbre de positions, je me suis plutôt intéressé à la succession des cases parcourues par la case vide (en fait c'est elle la plus importante, c'est elle qui détermine le mouvement des autres cases.

Salut !

J'en avais proposé un à la rédac, mais je ne sais pas s'il a été publié dans
les codes sources (il faudrait peut-être que j'aille voir !).
Il permet de jouer en 4*4, 5*5 et 6*6.
Développé à l'aide de BCB, pour les facilités offertes (graphique et événementiel).

J'ai utilisé un tableau de pointeurs, ce qui permet de travailler avec n'importe quel
type d'objet pour la glisse mais aussi pour la réinitialisation du jeu.

C'est la cellule vide qui conditionne le décalage des objets aussi bien en x qu'en y.
On déduit assez facilement dans quel sens doit s'effectuer cette glisse.
Par ailleurs, le déplacement n'est possible que si et seulement si la case vide est
sur l'un des axes (x ou y).
Si le décalage est possible alors on sait calculer dans quel sens il va s'opérer (aval
ou amont) et on procède à ce décalage :
- en commençant par décaler vers la case vide l'objet adjacent
- on continue jusqu'a la case sélectionnée, qui devient alors la case vide.

L'algo fait en tout 22 lignes (je ne compte pas les délimiteurs de blocs...) !

Si tu veux, je peux t'envoyer le code !

A plus !

Mon Taquin est quelque part par là :

http://c.developpez.com/sources/bcb/

Il suffit d'y rechercher "Taquin"

A plus !

Bonjour,

J'avais programmé ca en DEUG avec une permutation circulaire. Il fallait verifier que la signature etait ou non egale a 1 pour voir si le taquin possedait des solutions. Bref, un truc de transpositions avec heuristiques pour construire l'arbre.

Ludo