Century (puzzle)

Century casse-tête
position de départ
Ce jeu appartient au domaine public
Date de 1re édition	1975
Mécanisme	déplacements
Joueur(s)	1
Durée annoncée	variable
habileté physique  Non  réflexion décision  Oui générateur de hasard  Non info. compl. et parfaite  Oui
modifier

Century est un casse-tête de déplacements proche de l'Âne Rouge et pas très éloigné du taquin. Il a été inventé par John H. Conway (le jeu de la vie) en 1975 et a fait l'objet d'une étude dans Winning Ways for your Mathematical Plays^[1] où il est présenté comme le résultat d'une recherche systématique pour trouver le puzzle le plus difficile de ce type (pièces coulissantes rectangulaires sur un plateau 4x5). Même si d'autres puzzles plus difficiles (SuperCompo) ont été trouvés depuis, ce jeu reste un classique du genre caractérisé par une position de départ originale et symétrique. Il se différencie de l'Âne Rouge par la présence de 2 rectangles horizontaux (à la place de 1 pour l'Âne Rouge), ce qui rend plus difficile la descente du grand carré.

Le jeu et ses variantes

Comme avec l'Âne Rouge, le but du jeu est d'amener le grand carré en bas du plateau par glissements successifs des éléments. La solution optimale compte 100 coups d'où le nom de ce puzzle.

John H. Conway a proposé une variante de ce jeu qu'il a baptisé Century-and-half qui a une solution optimale en 150 coups et qui demande de retourner la configuration entière de haut en bas (obtenir l'image de cette configuration par une symétrie dont l'axe serait une droite horizontale passant par les milieux des côtés latéraux).

Gil Dogon^[2] a été le premier à publier la position de départ qui conduit le grand carré en bas à travers les mêmes pièces (la même structure que Century) par le chemin le plus long (en 138 coups). Il a baptisé cette position de départ Super-Century. Cette variante du jeu a été sélectionnée lors de l'exploration systématique de l'ensemble des possibilités par ordinateur pour sa difficulté, elle n'a donc pas la qualité esthétique de Century et n'est pas symétrique (voir illustration plus bas). Il se trouve que ce jeu est aussi le plus long pour cette structure lorsque l'on cherche à retourner la configuration dans son ensemble par une symétrie (230 coups).

Solution

On peut voir ici les 10 principales étapes d'une solution optimale pour amener le grand carré au milieu du côté du bas.

Données techniques sur le graphe

Nous considérons dans cette exploration de la structure du jeu tous les placements des 10 pièces sur le plateau comme équivalents et nous examinons avec un programme les connexions existantes entre les différents placements. Le jeu Century n'est plus ici qu'un placement parmi les autres. Nous devons préciser ici que le placement initial proposé par Conway n'est pas pris en compte à cause de la place inhabituelle du rectangle vertical du centre. Conway a trouvé ce point de départ qui apportait d'un même coup la symétrie de l'ensemble et les 100 coups qui justifient le nom (sinon on trouve 99 coups). Le placement de départ conforme au programme le plus proche de Century pousse le rectangle du centre sur un des côtés. Il y a 109 260 placements différents des pièces et 184 404 coups différents entre ces placements, ce qui correspond à une moyenne de 3.3755 coups par placement approximativement. Ces placements se répartissent entre 2653 composantes connexes différentes, dont 1 principale contenant 81 340 placements. Cette composante contient les placements symétriques par rapport aux 2 axes, horizontal et vertical, ce qui explique qu'elle soit unique. On peut donc passer d'un placement à son symétrique (par rapport à un des deux axes ou par rapport au centre du plateau) par un chemin (une suite de coups) pour 74% des placements. Parmi les autres ensembles connexes, beaucoup plus petits en taille (entre 2 et 240 placements), 4 ont un axe vertical. Le chemin le plus long dans l'ensemble connexe principal permet d'effectuer le demi-tour en 230 coups (pour les autres composantes, le diamètre maximum est de 39 coups). Le retournement selon un axe horizontal se fait au maximum en 229 coups et selon un axe vertival en 165 coups (à comparer avec 120 pour la structure de l'Âne Rouge). On peut amener le grand carré au milieu du côté du bas en un maximum de 138 coups (c'est le placement appelé Super-Century), dans un coin du bas en 89 coups, sur le bas du côté en 82 coups et sur le bas du centre en 56 coups.

Le jeu Century correspond à un placement inclus dans la composante connexe principale. Il peut donc être retourné selon un axe horizontal ou par un demi-tour. Le retournement selon un axe vertical n'a pas de sens (se fait en 0 coup) puisque ce placement possède lui-même un axe de symétrie vertical. Le plus long chemin à partir de ce placement mesure 188 coups. On peut amener le grand carré au milieu du côté du bas en 99 coups et effectuer le retournement selon un axe horizontal en 149 coups, 148 si on veut faire un demi-tour (ce qui amène à 150 si on veut placer le rectangle du centre à sa place, entre-deux positions). Il faut seulement 52 coups pour mener ce carré dans un des coins opposés, 48 pour l'amener en bas d'un des côtés et 43 pour l'amener en bas, au centre.

Placements records ayant même structure que Century. Les positions finales du grand carré sont indiquées en rouge pour les 4 figures de gauche.

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

Références

Liens externes

• Une version en ligne (sous Java) de Century,de Century-and-half et de Super-Century
• Applet java qui cherche les solutions et explore le graphe pour Century et d'autres configurations analogues
• Le site de Dries De Clercq contient de nombreux autres puzzles du même genre et une mesure de la difficulté de ces puzzles

• Portail des jeux