NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 12/04/2018

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique       Brèves de Maths    

            

Jeux et énigmes

 

Débutants

Général

DÉPLACEMENTS

 

Glossaire

Général

 

 

INDEX

 

Casse-têtes

 

Chaîne

Tranchée

Fortin

Étoile

Pair

Croix

Taquin

Âne rouge

Cavalier

Tour de Hanoi

Baguenaudier

 

Sommaire de cette page

>>> Le défi et popularité du jeu

>>> Étapes de ma solution

>>> Du Pennant puzzle à Rush Hour Puzzle

>>> Chercher la solution

>>> Anglais

 

 

 

 

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

 

 

 

Le défi et popularité du jeu

 

Terrain de jeu

Le plateau est composé de 10 pièces:

*      quatre carrés élémentaires (C),

*      cinq rectangles (2C x C) et

*      un grand carré (2C).

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:

*      Red Donkey (âne rouge)

*      Dad's puzze (puzzle de papa)

*      Pennant puzzle,

*      Huarong Pass: Les Trois Royaumes,

*      Klotski (blocs de bois en japonais),

*      Khun Phaen Escapes to Freedom,

*      Forget-me-not,

*      La sœur dans la boite,

*      Etc.

 

 

 

Étapes de la solution en 81 coups

 

 

Solution animée complète en Stavenger-guide

 

 

Du Pennant Puzzle à Rush Hour Puzzle

 

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.

 

 

Chercher la solution des jeux de pousse-pousse

 

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:

*      Taquin (15-puzzle),

*      Rush-hour puzzle, Traffic jam, Parking lot, Unblock me …

*      Tip over,

*      Junk Hanoi,

*      The Warehouseman's problem,

*      Âne rouge (Klotski),

*      Century (inventé par Conway),

*      Sokoban (jeu vidéo),

*      Jeu du 2048,

*      Cube de Rubik,

*      Etc.

 

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.

 

English corner

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

*    Taquin

*    Solitaire

*    Cavalier sur échiquier

Voir

*    Échecs

*    Échiquier tronqué

*    Élections

*    Énigmes – Filles

*    Groupe alterné

*    Jeux et puzzlesIndex

DicoNombre

*    Nombre 81

Cette page

http://villemin.gerard.free.fr/aJeux1/Deplacem/Anerouge.htm

 

Sites généraux

*      L'âne rouge – Wikipédia

*      KlotskiWikipedia

*      Century – Wikipédia 

*      Jeu du 2048 – Déplacez des tuiles, comme sur un jeu de taquin – jeu à la mode en 2014

Sites sur les solutions

*      Recherche de solution de l'Ane Rouge – Défis C & C++ – Développez.com

*      Solving sliding-block puzzles – Ruben Spaans – 2009 – pdf 104 pages

*      Sliding Block Puzzles - CS 474 – Object Orient Languages and Environments – 2016

Livre

*      Games, Puzzles, and Computation – Robert A. Hearn et Erik D. Demaine – 2006 –153 pages – Thèse qui est devenu un livre publié en 2009