Fifteen Puzzles

Avec RadarOric, Fifteen Puzzle est un des premiers jeux de l’année 2020. Rax et Iss nous ont concocté un magnifique jeu de réflexion. J’avoue n’avoir jamais été fan de ce type de jeu car ces puzzles type Rubik’s Puzzle et consorts ne m’ont jamais trop réussi. Cette sortie est donc l’occasion de découvrir le genre et surtout les méthodes qui me permettent enfin de finir ces casse-têtes.

Petit historique pour commencer …

Ces jeux de réflexion ou l’on pousse des pièces pour les remettre dans l’ordre est également appelé “taquin” (NDLR : Rax et Iss le sont ils ?).
Ce solitaire se présente sous la forme d’un damier et a été créé vers 1870 aux États-Unis. Comme toujours dans les domaines du jeu, le concept est associé à une théorie mathématique qui a été publiée par l’American Journal of mathematics pure and applied en 1879 (franchement, je préfère être publié dans le CEO-MAG). En 1891, alors que le jeu passionne, son invention est revendiquée par Sam Loyd. En fait, le premier jeu de taquin connu date de 1880 et il est de Noyes Chapman. Sam Loyd l’a popularisé. Sans internet, le jeu a tout de même mis quelques mois à se répandre dans les chaumières.
La version la plus classique est composée de 15 carreaux numérotés de 1 à 15 qui glissent dans un cadre prévu pour 16 (sur une matrice de 4×4). Il faut donc que le joueur remette 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.

Le Concept

Le jeu qu’il proposait était le 14-15. Il s’agissait de remettre les pions mobiles dans l’ordre séquentiel correct. Loyd promettait un prix à celui qui y arriverait. Il était, en fait, infaisable … car les pavés 14 et 15 étaient inversés.

Pour répondre au petit casse-tête de Sam Loyd, nous allons étudier comment les configurations du taquin changent par les mouvements autorisés. Il sera plus facile de travailler avec des nombres disposés à la queue-leu-leu plutôt que rangés dans un tableau. Voici comment nous rangeons les nombres : à une position du taquin, on associe la liste des numéros que l’on rencontre en parcourant les cases le long du chemin indiqué ci-dessous. On ne tient pas compte de la case vide. Le chemin vert ressemble à une file d’attente aux guichets d’une gare, entre des barrières qui zigzaguent, n’est-ce pas ?

On obtient ainsi un rangement des nombres de 1 à 15. Par exemple, le rangement associé à la configuration de départ du taquin est “4 – 3 – 2 – 1 – 5 – 6 – 7 – 8 – 12 – 11 – 10 – 9 – 13 – 14 – 15”.
Le rangement des nombres de 1 à 15 ne détermine pas complètement la configuration du taquin, car il ne donne pas d’information sur la position de la case vide. Mais comme on peut promener la case vide le long du chemin par les mouvements autorisés du taquin, peu importe : si l’on peut arriver à l’une des configurations donnant un certain rangement, on pourra aussi arriver à toutes les configurations donnant le même rangement.

Le critère le plus important pour qualifier le taquin est le dérangement. Le « dérangement » est le nombre de paires inversées pour obtenir une séquence croissante de 1 à 15. Dans le cas simple ci-dessus du Taquin de Loyd, seule la paire 14-15 est inversée (le brigand). Le dérangement est donc de 1, donc impair. La plupart du temps, calculer le dérangement est fastidieux mais il permet de vérifier que le jeu est soluble. En effet, si le dérangement est impair, les pièces ne peuvent pas être repositionnées dans l’ordre désiré. D’un rangement R donné des nombres de 1 à 15 (ou de 1 à un entier quelconque) par rapport au rangement par ordre croissant. On dira qu’une paire de nombres présente une inversion dans le rangement R si le plus grand des deux nombres vient avant le plus petit dans R. Par exemple, dans le rangement suivant des nombres de 1 à 9

On a prouvé par ordinateur que le jeu de taquin n’exige jamais plus de 80 mouvements.

Fifteen Puzzle

Le jeu proposé par ISS et Rax est magnifique. Moderne, en Hires et agrémenté au choix de bruitages et de musique, il met en oeuvre plusieurs designs ; des classiques dés numérotés de 1 à 15 à de beaux puzzles qui tirent parti des capacités graphiques de l’Oric (NDLR : Ils auraient quand meme se mettre à la page de l’égalité homme-femme).

Pour finir en toute tranquillité ce puzzle, sans altérer l’oeuvre des auteurs.

Ici, point de peek, de poke, de call … il y a une méthode infaillible que j’ai réussi à mettre en oeuvre sans mettre en oeuvre de compétences oriciennes.
Partons du principe que la case vide est placée en bas à droite du puzzle.

1. remettre le jeu dans l’ordre ligne par ligne en commençant par la ligne du haut. répéter la manip pour la seconde ligne.
2. quand il ne reste plus que les deux lignes du bas mélangées, les réordonner colonne par colonne en commençant par celle de gauche.
3. lorsque les 2 colonnes de gauche sont ordonnées, il ne nous reste plus qu’à conclure en mettant en ordre les 3 derniers carrés à leurs places respectives.

Bien sur, les experts de ce type de jeu boucleront l’énigme rapidement est en un nombre minimal de coups mais cette méthode est simple à mémoriser et aboutit dans tous les cas (si la solution est possible)