Century (puzzle)

Century (puzzle)
Century
casse-tête
Century.png
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

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é.

Sommaire

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.

Une solution en 100 coups par pas de 10 au puzzle Century

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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Century (puzzle) de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Puzzle People — Studio album by The Temptations Released September 23, 1969 …   Wikipedia

  • Puzzle — For other uses, see Puzzle (disambiguation). Puzzle solving redirects here. For the concept in Thomas Kuhn s philosophy of science, see normal science. Part of a series on Puzzles …   Wikipedia

  • Puzzle box — Japanese puzzle box A puzzle box (also called a secret, or trick box) is a box that can only be opened through some obscure or complicated series of manipulations.[1] Some puzzle boxes may require only a simple squeeze in the right spot, whereas… …   Wikipedia

  • puzzle — [16] The origin of puzzle is, appropriately, a puzzle. One suggestion is that it may be derived from the now obsolete verb pose ‘interrogate, perplex’ (which survives in poser ‘difficult question or problem’), a shortened form of appose… …   The Hutchinson dictionary of word origins

  • puzzle — [16] The origin of puzzle is, appropriately, a puzzle. One suggestion is that it may be derived from the now obsolete verb pose ‘interrogate, perplex’ (which survives in poser ‘difficult question or problem’), a shortened form of appose… …   Word origins

  • Century — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Century, terme anglais signifiant siècle, se retrouve dans : Sommaire 1 Toponymes 2 Musique …   Wikipédia en Français

  • Mechanical puzzle — Part of a series on Puzzles …   Wikipedia

  • Dissection puzzle — Part of a series on Puzzles …   Wikipedia

  • Frege's Puzzle — is a puzzle about the semantics of proper names, although the title is also sometimes applied to a related puzzle about indexicals. Frege introduced the puzzle at the beginning of his article Über Sinn und Bedeutung ( On Sense and Reference ),… …   Wikipedia

  • crossword puzzle — a puzzle in which words corresponding to numbered clues or definitions are supplied and fitted into correspondingly numbered sets of squares, one letter per square, the words being arranged horizontally or vertically so that most letters form… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”