Taquin résolu

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 applied 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 15 carreaux à partir d'une configuration initiale quelconque.

Le principe a été étendu à toutes sortes d'autres jeux. La plupart sont à base de blocs rectangulaires plutôt que carrés, mais le but est toujours de disposer les blocs d'une façon déterminée par un nombre minimal de mouvements. Le Rubik's Cube est aujourd'hui considéré comme l'un des « descendants » du taquin.

Méthode générale de résolution

Dans l'hypothèse où la case vide se trouve en bas à droite :

remettre le jeu dans l'ordre ligne par ligne en commençant par la ligne du haut ;

quand il ne reste plus que deux lignes mélangées, les réordonner colonne par colonne en commençant par celle de gauche.

Cette méthode ne garantit pas qu'un nombre minimal de mouvements sera effectué, mais est simple à mémoriser et aboutit dans tous les cas où une solution est possible.

Anecdote

Position initiale du taquin de Sam Loyd

Loyd affirma qu'il avait « rendu le monde entier fou » avec un taquin modifié. Dans la configuration proposée, les carreaux 14 et 15 étaient inversés, l'espace vide étant placé en bas à droite. Loyd prétendait avoir promis 1 000 USD à celui qui remettrait les carreaux dans l'ordre, mais la récompense n'aurait jamais été réclamée.

La résolution de ce problème est impossible. D'une part, il faut en effet échanger les places des carreaux 14 et 15, et l'on peut montrer que cette opération nécessite un nombre impair de glissements. D'autre part, il faut que la case vide retrouve sa place initiale, opération qui, quant à elle, nécessite un nombre pair de glissements. Il est toutefois possible d'ordonner les chiffres de 1 à 15 si la case vide est initialement en haut à gauche.

Configurations solubles et insolubles

The Great Presidential Puzzle : illustration montrant le sénateur Roscoe Conkling, à la tête des Stalwarts du parti républicain, jouant avec un puzzle. Tous les blocs de ce puzzle sont les têtes des candidats républicains aux présidentielles potentiels, parmi eux Grant, Sherman, Tilden et Blaine. (chromolithographie publiée en 1880 aux États-Unis).

Parmi toutes les dispositions initiales, il existe 10 461 394 944 000 dispositions dont la résolution est possible (à savoir la moitié de la factorielle de 16), et autant d'impossibles, dont celle proposée par Loyd.

Il est possible de dire à l'avance si le problème posé est soluble ou non. En effet, la configuration initiale d'un taquin est une permutation de sa configuration finale. Cette permutation est dite paire si elle peut être obtenue par un nombre pair d'échanges successifs de deux cases, adjacentes ou non, vide ou non, appelés également transpositions. On montre que cette notion ne dépend pas du choix de la suite des échanges. Elle est impaire sinon. On associe également à la case vide une parité : la case vide est paire si l'on peut se rendre de la position initiale de la case vide à la position finale en un nombre pair de déplacements, impair sinon.

Le problème sera soluble si la parité de la permutation est identique à la parité de la case vide.

Exemple 1

Le problème de Sam Loyd est impossible. La case vide occupant la même place dans la configuration initiale et dans la configuration finale souhaitée, elle est paire (il faut 0 déplacement pour aller d'une position à l'autre). Mais puisque la configuration initiale s'obtient à partir de la configuration finale par la seule transposition des cases 14 et 15, la permutation est impaire. La case vide étant paire et la permutation impaire, le problème est insoluble.

Exemple 2

Variante soluble du taquin de Loyd

Supposons que la configuration initiale soit telle que la case vide est en haut à gauche, suivie des carreaux dans l'ordre 1, 2, 3, ..., 13, 15, 14, ce que nous noterons (V, 1, 2, ..., 13, 15, 14). La configuration finale attendue est (1, 2, ..., 13, 14, 15, V). La case vide est paire, car on peut se rendre de sa position initiale (en haut à gauche) à sa position finale (en bas à droite) en faisant trois déplacements vers la droite puis trois déplacements vers le bas. La permutation est également paire, car on peut passer de (V, 1, 2, ..., 13, 15, 14) à (1, 2, ..., 13, 14, 15, V) en échangeant 14 et 15, puis en échangeant successivement V avec les 15 nombres qui suivent, (soit 16 transpositions en tout). La parité de la case vide étant identique à la parité de la permutation, la résolution est possible.

Exemple 3

Taquin mélangé

Dans le taquin mélangé ci-contre, la case vide occupe une position paire. Par ailleurs, la position donnée est (13, 2, 3, 12, 9, 11, 1, 10, V, 6, 4, 14, 15, 8, 7, 5). Les transpositions permettant de passer de cette position à la position finale sont au nombre de 11, par exemple :

(13, 2, 3, 12, 9, 11, 1, 10, 5, 6, 4, 14, 15, 8, 7, V)
(13, 2, 3, 12, 9, 11, 1, 10, 5, 6, 4, 14, 7, 8, 15, V)
(13, 2, 3, 12, 9, 11, 1, 10, 5, 6, 4, 8, 7, 14, 15, V)
(7, 2, 3, 12, 9, 11, 1, 10, 5, 6, 4, 8, 13, 14, 15, V)
(7, 2, 3, 8, 9, 11, 1, 10, 5, 6, 4, 12, 13, 14, 15, V)
(7, 2, 3, 8, 9, 4, 1, 10, 5, 6, 11, 12, 13, 14, 15, V)
(7, 2, 3, 8, 9, 4, 1, 6, 5, 10, 11, 12, 13, 14, 15, V)
(7, 2, 3, 8, 5, 4, 1, 6, 9, 10, 11, 12, 13, 14, 15, V)
(7, 2, 3, 6, 5, 4, 1, 8, 9, 10, 11, 12, 13, 14, 15, V)
(1, 2, 3, 6, 5, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, V)
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, V)

Il s'agit donc d'une permutation impaire. Etant impaire alors que la case vide est paire, la résolution est impossible.

L'algorithme proposé permet de déterminer si le problème posé est soluble ou non, mais ne donne pas la solution pour y parvenir. En particulier, il faut une certaine habileté pour l'effectuer concrètement en un moindre nombre de mouvements.

Exemples de jeu de Taquin

Divers jeux en ligne sont inspirés du mécanisme du jeu de taquin. Par exemple les jeux

Continuity

Rooms.

9数字推盘游戏解法

《总统推盘游戏》：彩色平版印刷的插图显示共和党参议员罗斯科·康克林在玩推盘游戏。盘中的方块包括格兰特、舍曼、蒂尔登和布莱恩等共和党总统候选人。推盘游戏模仿了著名的十五数字推盘游戏

数字推盘游戏（n-puzzle）是一种最早的滑块类游戏，常见的类型有十五数字推盘游戏和八数字推盘游戏等。也有以图画代替数字的推盘游戏。可能Noyes Palmer Chapman在1874年发明十五数字推盘，但Sam Loyd则在1891年也宣称为其发明。

八数字推盘（又名重排九宫）则同样是Noyes Palmer Chapman在1870年代发明，并且马丁·加德纳在科学人寻求更快的解答。也有人宣称重排九宫是传统中国游戏，来自洛书，并且为华容道的祖先。

十五数字推盘游戏。

构造

数字推盘游戏是由一块有凹槽的板和写有数字的方块所组成。 十五数字推盘游戏的板上会有十五个方块和一个大小相当于一个方块的空位（供方块移动之用）。而八数字推盘游戏，为九宫格布局，有八个方块和一个空位。

游戏规则

解法

放错的方块的数量，

所有放错的方块到各自目标位置的距离之和。