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'
Partager