L'Âne rouge

Le but du jeu est d'amener l'âne, représenté par le grand carré rouge, en bas du plateau par glissements successifs des éléments. La grille est constituée uniquement de petits carrés, de rectangles, et de l'âne.

La solution optimale compte 81 coups, il y a plusieurs façons de compter les coups, de 90 à 116. Le premier à publier cette solution a été Martin Gardner, en février 1964 dans le magazine Scientific American.

On peut voir ci-dessous les 10 principales étapes d'une solution en 115 coups.

• Principales étapes d'une solution en 115 coups
• 
  I
• 
  II
• 
  III
• 
  IV
• 
  V
• 
  VI
• 
  VII
• 
  VIII
• 
  IX
• 
  X

L'Âne Rouge est parfois présenté comme un jeu d'origine thaïlandaise, le nom du jeu en Thaïlande étant celui d'un prisonnier célèbre cherchant à s'évader : « Khun chang khun phaen ». Il est aussi probable que ce jeu soit d'une invention récente. À la suite du succès du taquin ou puzzle-15 (15 carrés 1x1 dans un grand carré 4x4) en 1880, le puzzle Dad's puzzler ou  Pennant puzzle  introduit les rectangles 1x2 en 1909 et 1912 (deux variantes enregistrées par copyright par L. W. Hardy aux États-Unis). Par la suite, J. H. Fleming dépose un copyright en 1934 pour ce jeu qui est connu un peu partout à cette époque sous différents noms : Klotski (bloc de bois) en polonais, Hua rong dao en chinois, Hakoiri musume (fille en boîte) en japonais[1], Forget-me-not ou Major Migraine Maker en anglais. Aujourd'hui, ce jeu se retrouve sous une grande quantité de noms, seul ou avec des variantes parfois très éloignées, sur différentes plateformes de jeu (iPhone, DS): Block puzzle, Path puzzle, Kwirk, Professor Layton, etc. Les variantes les plus connues et les plus proches de ce jeu sont Century, SuperCompo et Quzzle.

Il y a 65 880 placements différents des 10 pièces de ce jeu. Il y a 114 958 coups différents entre ces placements, ce qui correspond à une moyenne de 3,48 coups par placement approximativement. Ces placements se répartissent entre 898 composantes connexes différentes, dont deux principales contenant chacune 25 955 placements. Ces deux composantes sont symétriques l'une de l'autre par rapport à un axe horizontal ce qui explique qu'elles soient deux. Chacune possède par ailleurs un axe de symétrie vertical interne, ce qui fait qu'on peut passer d'un placement à son symétrique (par rapport à cet axe vertical) par un chemin (une suite de coups).

Placements records ayant même structure que l'âne rouge

Parmi les autres ensembles connexes, beaucoup plus petits en taille (entre 2 et 248 placements), 2 ont un axe horizontal et 18 autres ont un axe vertical. Le retournement d'un placement peut donc se faire selon un axe vertical pour près de 80 % des placements. Le chemin le plus long pour effectuer ce retournement mesure 120 coups. Le retournement d'un placement selon un axe horizontal est beaucoup plus rare et mesure au maximum 7 coups. Du fait de l'absence de composante connexe ayant un centre de symétrie, tous les demi-tours (retournement autour d'un centre) sont impossibles pour cette structure.

Pour ce qui concerne les chemins les plus longs possibles dans une composante connexe, le maximum est de 145 coups au sein d'une des composantes principales et varie entre 1 et 56 coups pour les autres composantes connexes. On peut amener le grand carré au milieu du côté du bas en un maximum de 93 coups, dans un coin du bas en 85 coups, sur le bas du côté en 73 coups et sur le bas du centre en 69 coups. Le jeu de « l'âne rouge » correspond à un placement inclus dans une des deux composantes connexes principales. Il ne peut donc pas être retourné selon un axe horizontal ou par un demi-tour, et le retournement selon un axe vertical n'a pas de sens (nombre de coup nul) puisque ce placement possède lui-même un axe de symétrie vertical. Le plus long chemin à partir de ce placement mesure 124 coups. On peut amener le grand carré au milieu du côté du bas en 81 coups, dans un coin du bas en 58 coups, sur le bas du côté en 52 coups et sur le bas du centre en 48 coups. À titre de comparaison, les configurations voisines appelées Century et SuperCompo dépassent celle de l'Âne Rouge sur tous les points (138 et 135 coups pour amener le grand carré au milieu du bas, 230 et 268 pour obtenir un retournement du placement selon un centre, etc.)

Ces données techniques[2] ont été obtenues à l'aide d'un programme[3] qui permet d'étudier aussi de nombreuses autres configurations incluant les configurations connues : Dad's Puzzler et Quzzle pour les configurations à 9 pièces, Century et SuperCompo pour celles à 10 pièces).

Solution animée en 81 coups

• Une version en ligne du jeu (en Java)
• Variantes diverses
• Algorithmes pour résoudre le problème (en C/C++)