Commentaire de
Taquineries

En bref.

Diverses variantes du classique jeu de taquin.

Mais encore...

Le taquin est un casse-tête bien connu qui date de la fin du XIX^e siècle. Dans sa version originale il consiste en 15 carrés numérotés que l'on peut déplacer parmi 16 emplacements (il en existe de très nombreuses variantes). Le but du jeu est, en partant d'une situation où les 15 pièces sont mélangées, de les remettre dans l'ordre des numéros. Pour cela on ne peut déplacer qu'une pièce à la fois, en faisant glisser dans l'emplacement libre la pièce située immédiatement au-dessus, au-dessous, à droite ou à gauche de celui-ci.

La page Taquineries permet de simuler le fonctionnement d'un taquin, et propose trois problèmes à résoudre avec des niveaux de difficulté croissants.

Le simulateur de taquin est écrit en JavaScript. Si l'exécution de JavaScript est désactivée sur votre navigateur vous ne pourrez pas l'utiliser.

1. Alphabétisation

Ce premier problème est tout à fait classique : les 15 lettres (qui remplacent les chiffres) sont mélangées et il s'agit de les mettre dans l'ordre alphabétique.

Le mélange change aléatoirement à chaque fois que l'on réaffiche cette page, mais il n'est pas fait tout à fait au hasard. En effet, en mélangeant les pièces au hasard il y aurait une chance sur deux que le problème soit impossible à résoudre. Depuis une configuration donnée des pièces, en n'effectuant que des déplacements conformes aux règles du taquin on ne peut atteindre que la moitié des configurations théoriquement possibles. Ici, le mélange est fait de telle sorte que le problème ait toujours une solution.

Comment savoir s'il existe une solution ?

Étant donné deux configurations des pièces du taquin, on peut savoir s'il est possible de passer de l'une à l'autre par des déplacements autorisés, de la façon suivante.

1. Supposer que l'on ait le droit de prendre deux pièces quelconques du jeu (même si elles ne sont pas voisines) et de les échanger de place. Chercher combien il faudrait faire de tels échanges pour passer de la configuration de départ à celle d'arrivée. Il y a beaucoup de façons de procéder : en choisir une quelconque, et noter le nombre E d'échanges qu'elle nécessite. Pour ce calcul, la case vide est considérée comme une pièce à part entière qui doit être amenée à sa place par des échanges, comme les autres pièces.
2. Supposer que l'on cherche uniquement à déplacer la case vide de sa position de départ à celle d'arrivée, sans s'occuper des autres pièces. Elle peut se déplacer d'une case à la fois, horizontalement ou verticalement. Compter le nombre de déplacements D qu'il lui faudra effectuer (choisissez n'importe quel chemin).
3. Si les nombres E et D sont tous les deux pairs, ou tous les deux impairs, alors le problème a une solution, il est possible de passer de la configuration de départ à celle d'arrivée en respectant les règles du taquin. Si l'un des nombres est pair et l'autre impair, il n'y a pas de solution.

1. Pour mettre les pièces à leur place par échanges successifs, on peut par exemple échanger le M et la case vide, puis le N et la case vide, puis le N et le O, soit 3 échanges (il y a bien d'autres possibilités). Donc E = 3.
2. Pour amener la case vide de sa position de départ à sa position d'arrivée il faut 3 déplacements, donc D = 3.
3. E et D sont tous les deux impairs, donc le problème a une solution.

1. Pour mettre les pièces à leur place par échanges successifs, on peut par exemple échanger M et A, N et B, O et C, la case vide et D, et finalement C et D, soit 5 échanges, donc E = 5.
2. Pour amener la case vide de sa position de départ à sa position d'arrivée il faut 4 déplacements, donc D = 4.
3. E est impair et D pair, donc il est impossible de passer d'une configuration à l'autre en suivant les règles du taquin.

2. Rien que des animaux

À première vue, il s'agit dans ce problème d'échanger le A et le R, sans rien changer d'autre. Tous les amateurs de taquin savent que c'est impossible, et on peut facilement s'en assurer comme expliqué dans la section précédente : E = 1 (un seul échange) est impair et D = 0 (la case vide ne bouge pas) est pair.

Cependant, on peut observer que la dernière ligne comprend deux I qui sont indiscernables. La description des configurations initiale et finale ne permet pas de savoir si ces I ont changé de place ou pas. Si on décide d'échanger ces deux I en même temps que l'on échange le A et le R, le problème devient alors soluble (E = 2 et D = 0 sont tous deux pairs).

La solution la plus courte nécessite 36 déplacements. Voici les lettres qu'il faut successivement déplacer dans la case vide : x u i w i é b i (de droite) w i i (du haut) w u n y b z l a r t y b a l z é i w b y t a y n x.

Voici un autre problème dont la solution repose sur une constatation similaire, mais en sens inverse :

Si l'on cherche à échanger la première et la dernière ligne, on constate que c'est impossible (E = 4 est pair, D = 3 est impair). Il faut réaliser que ces lignes contiennent chacune un A, qu'il est inutile de déplacer. En échangeant seulement B et H, S et U, la case vide et T, on trouve facilement une solution.

3. Retournement de situation

Cette fois encore, le problème est a priori insoluble. Le nombre E d'échanges directs nécessaire est pair (par exemple 6 avec H et U, E et P, S et I, la case vide et M, U et I, P et M) tandis que D = 1 est impair. Contrairement au problème précédent, les lettres sont toutes différentes.

L'astuce réside cette fois dans le graphisme des lettres. Elles sont dessinées de telle sorte qu'en retournant une lettre, soit elle reste inchangée (I, l, o, s, z), soit elle se change en une autre lettre également présente (a↔e, d↔p, h↔y, m↔w, n↔u). Ainsi, si on tenait réellement le taquin en main, il suffirait de le faire tourner d'un demi-tour pour transformer

h	e	s
u	p	I	m
d	o	w	n
l	a	z	y

en

h	z	e	l
u	m	o	p
w	I	d	n
	s	a	y

à partir d'où il est possible d'atteindre

I	m	u	p
h	e	s
d	o	w	n
l	a	z	y

.

Dans le simulateur de la page Taquineries il n'est pas possible de retourner l'ensemble du taquin. Par contre il suffit de cliquer sur la case vide pour faire tourner individuellement chacune des lettres, ce qui permet également de résoudre le problème.

Si l'on clique sur la case vide à partir de la configuration initiale, il faut ensuite au minimum 57 déplacements pour atteindre la configuration finale. La solution la plus courte s'obtient en déplaçant successivement les lettres suivantes : s I m o d a I m a n p d o a w u h z a w n p y I m s u n p y d o e a w h n p h e y h e y o d h e s u p n y w z y n.

Références.

Un taquin à faire vous-même

Cliquez sur une lettre de l'alphabet puis sur une case du taquin pour inscrire la lettre dans cette case. Vous pouvez même inscrire une lettre dans la case vide, cela ne l'empêchera pas de continuer à fonctionner comme case vide. À la fin de l'alphabet se trouvent quatre boutons spéciaux :

1. Le carré blanc sert à effacer une lettre du taquin pour remettre la case dans son état initial.
2. Le carré « vide » permet de donner à une case l'aspect d'une case vide (mais cela ne la rend pas réellement vide, elle continue à se comporter comme si elle contenait une lettre).
3. Le bouton à quatre flèches retourne toutes les cases du taquin. Certaines lettres restent inchangées quand on les retourne et certaines autres se transforment en d'autres lettres.
4. Le bouton à une flèche retourne le taquin en bloc.

Voici quelques exemples de problèmes qui ne peuvent être résolus qu'en retournant le taquin (cliquez dessus pour remplir directement la grille) :

• half down? up, my sex!_ → half up, my sex?_ down!
• fay,_ help us! I'm down. → I'm up now,_ fay's held.