|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Jeu de pousse-pousse ÂNE ROUGE Le Puzzle de Papa Jeu de puzzle solitaire,
voisin de celui du taquin. Pièces
prisonnières d'un cadre. Il faut passer d'une configuration à une autre en
faisant glisser les pièces sans sortir
du cadre. |
Configurations départ et arrivée
|
Anglais: Red donkey game / Dad's puzzle / Sliding block puzzle
|
|
||
|
Terrain de jeu Le
plateau est composé de 10 pièces:
Un espace
est laissé libre Les pièces
peuvent glisser en vertical et en horizontal. Défi Le but
est de faire glisser ces pièces dans le cadre du plateau jusqu'à à amener le
grand carré rouge (dit "âne rouge") jusqu'à la porte de sortie
matérialisée par la barre noire en bas. Le défi est
terrible! L'âne ne veut par sortir tant l'herbe est verte dans son pré … |
|
|
|
Solution La
solution minimale, vérifiée par ordinateur, exige 81 mouvements. La page
Wikipédia en montre une animation. Vous y trouverez également
l'historique du jeu. En 1990, Microsoft incluait ce jeu dans Windows Entertainment Pack et de
nombreuses versions pour ordinateurs suivirent, comme Bricks (par Andreas
Rottler – 1998). On a pu dénombrer pas moins de 270 variantes à ce puzzle. |
Historique Le premier à publier la solution minimale a été Martin Gardner,
en février 1964 dans le magazine Scientific American. Il déclarait que la
théorie de ces jeux était à inventer et que seules les solutions par essais
successifs (trials and error) étaient possibles. Et, personne ne connait les
solutions minimales. Connu aussi sous le nom de:
|
|
|
|
|
|
Solution animée complète en Stavenger-guide |
|
|
|
||
|
Pennant puzzle ou Dad's puzzle Configurations départ et arrivée
Ce jeu a été breveté en 1907. |
|
|
|
Junk Hanoi
Créé par Toshi Junk Kato |
Sokoban (jeu vidéo)
Crée au Japon par Hiroyuki Imabayashi en 1980 Sokoban = garde d'entrepôt. |
|
|
|
||
|
La
recherche de la solution des jeux de pousse-pousse (slide-blok puzzles) n'est
pas triviale face à l'explosion combinatoire de ce jeu. Ce qui
veut dire qu'une simple exploration exhaustive prend souvent trop de temps
même avec un ordinateur. |
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. Jeux dans cette catégorie:
|
|
|
Les
puzzles de pousse-pousse de ce type sont un champ idéal pour la recherche en intelligence
artificielle. |
Domaine plus simple néanmoins que celui des Échecs ou du jeu de Go. |
|
|
Un des
domaines de recherche consiste à déterminer si le puzzle possède une
solution. Ce
problème est du type NP. |
Un programme débute par véfifier que toutes les pièces sont
sur le plateau et dans une position légale. |
|
|
Une
fonction détermine le degré de mobilité de chaque pièce |
Cette fonction permet d'épargner des recherches inutiles et
de minimiser le temps de traitement. |
|
|
Un graphe
est mis en place: les nœuds sont les états, et les branches représentent les
mouvements possibles. Le graphe
est exploré avec un algorithme
de parcours en largeur (breadth first search), par exemple. L'art du
chercheur consiste à trouver le meilleur algorithme, le meilleur parcours
d'exploration. |
Algorithme de parcours en largeur: partant d'un nœud du graphe, il explore
d'abord tous ses successeurs avant de passer au niveau suivant. |
|
|
A sliding block
puzzle consists of blocks of possibly different sizes. A block consists of at least one or
more connected unit squares. A block can slide in one of the 4
directions (up, down, left, right) if there is enough space. The objective is to reach a certain
end-configuration. |
Merci à
Jérôme Mayer – Voir sa page sur l'âne rouge
Jeu réalisé par des enfants
|
Suite |
|
|
Voir |
|
|
DicoNombre |
|
|
Cette
page |
|
Sites
généraux |
|
|
Sites
sur les solutions |
|
|
Livre |
|
