Initialement, 8 carreaux numérotés et un carreau "vide" sont
disposés sur un damier dans une configuration
donnée. L'objectif du taquin est de modifier la position des
carreaux pour arriver à une configuration finale donnée. On
autorise les changements de position seulement par glissement d'un des
carreaux sur le carreau vide à partir d'une position adjacente
orthogonale. Le but du jeu est de trouver la séquence la plus courte
amenant à la configuration finale.
= { (monter(X),
) / X est le carreau sous le carreau vide, et
ou le carreau X est substitue au carreau vide }
{ (descendre(X),
) / X est le carreau sur le carreau vide, et
ou le carreau X est substitue au carreau vide }
{ (a_droite(X),
) / X est le carreau a gauche du carreau vide, et
ou le carreau X est substitue au carreau vide }
{ (a_gauche(X),
) / X est le carreau a droite du carreau vide, et
ou le carreau X est substitue au carreau vide }
Par exemple, une solution à ce problème est donnée par la séquence d'actions suivantes:
a_gauche(a), monter(b), a_gauche(e), monter(f)On peut généraliser le problème à N*N-1 carreaux sur un damier