Le taquin est un jeu solitaire en forme de damier créé vers 1870 aux États-Unis.
Sa théorie mathématique a été publiée par l’American Journal of mathematics pure and applied2 en 1879.
En 1891, son invention fut revendiquée par Sam Loyd, au moment où le jeu connaissait un engouement considérable, tant aux États-Unis qu’en Europe. Il est composé de 15 petits carreaux numérotés de 1 à 15 qui glissent dans un cadre prévu pour 16.
Il consiste à remettre dans l’ordre les carreaux à partir d’une configuration initiale quelconque
l'algorithme de recherche A* (qui se prononce A étoile, ou A star à l'anglaise) est un algorithme de recherche de chemin dans un graphe entre un nœud initial et un nœud final tous deux donnés.
En raison de sa simplicité il est souvent présenté comme exemple typique d'algorithme de planification, domaine de l'intelligence artificielle.
