Exemple du taquin

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.

Formalisation du problème :

• S est l'ensemble des configurations possibles du damier,

• est l'état initial suivant:

  

• F contient l'unique état final suivant:

  

• T est la fonction de transition définie par

     = { (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 .