Reconstruction de puzzlesSujet proposé par Philippe ChassignetPhilippe.Chassignet[at]polytechnique.fr |
On se donne les pièces d'un puzzle et il s'agit de le reconstruire. Pour plus de clarté, dans l'exemple des figures 1 et 2, les pièces sont numérotées mais en réalité on n'aura pas cette information. Les pièces sont décrites par leurs contours et la reconstruction du puzzle va donc consister à apparier ces contours pour trouver les pièces adjacentes.
Si on le généralise à 8 directions, ce type de codage est appelé codage de Freeman et il permet de décrire toute courbe discrète. Un mot sur l'alphabet {+ , = , -} permet de décrire un côté “horizontal”, implicitement orienté de la gauche vers la droite, la figure 4 nous en donne quatre exemples.
Les 3 directions + = - nous suffisent. Une pièce du puzzle sera décrite par ses 4 côtés, enroulés dans le sens des aiguilles d'une montre. Ainsi la suite des 4 mots donnés figure 4, pris dans cet ordre, correspond à la pièce de la figure 5. On remarquera qu'une permutation circulaire des 4 mots décrirait la même pièce mais tournée d'un certain nombre de quarts de tours.
3 3 10 ========== =-+=+=+--= =-=+=+==-= ========== 0 ==+=---++= ========== =+=--===+= ==++-===-= 5 =-==+=+=-= =+===-=+-= ==--=-+++= ========== 3 =+++-=--== =+=-==-+== ========== ========== 6 =====+==-= ========== ========== =++---=+== 2 =+--=++=-= =-===-++== ==--+-=++= =-+=-===+= 4 ========== ========== =+==+-+--= =+===--=+= 8 =--+=+=+-= ========== =-==+===== =-=++=--+= 1 =--+-+==+= ========== ==+-==-=+= =++=-+--== 7On pourra utiliser le fait qu'il n'y a pas de côté plat à l'intérieur du puzzle.
This document was translated from LATEX by HEVEA.