Solution minimale du jeu Traffic!

Un article de Wikipedia.

(Différences entre les versions)
(→Ressources)
(→Introduction)
Ligne 5 : Ligne 5 :
-
Premièrement, '''Merci''' à ''Phillip Cheng'' pour l'implémentation de [[Solution minimale du jeu Traffic!#Ressources|Traffic!]] et un '''Grand Merci''' posthume à ''Nob Yoshigahara'' pour sa lumineuse idée.
+
Premièrement, '''Merci''' à ''Phillip Cheng'' pour l'implémentation de [[Solution minimale du jeu Traffic!#Ressources|Traffic!]] et un '''Grand Merci''' posthume à ''[http://en.wikipedia.org/wiki/Nob_Yoshigahara Nob Yoshigahara]'' pour sa lumineuse idée.

Version du 13 avril 2008 à 09:28

Sommaire

Solution minimale du jeu Traffic!

But

Déterminer le nombre minimal de mouvements pour résoudre une grille du jeu Traffic!.

Introduction

Premièrement, Merci à Phillip Cheng pour l'implémentation de Traffic! et un Grand Merci posthume à Nob Yoshigahara pour sa lumineuse idée.


Traffic! est une implémentation gratuite sous Palm du jeu 'Rush Hour' conçu par Nob Yoshigahara.

Il consiste en un plateau carré de 6 unités sur lequel se trouve des blocs de 2 ou 3 unités qui peuvent se déplacer verticalement ou horizontalement.

Le but du jeu est de faire sortir un bloc de 2 unités horizontalement en déplaçant les autres blocs.

Une croquis vaut mieux qu'un long discours, donc voici une image d'une grille de Traffic! :

Image:Traffic.gif

Le bloc blanc doit être déplacé vers la sortie.

Résultats

La méthode utilisée pour résoudre une grille de Traffic! est de disposer de trois listes.

  • La première contient la liste des grilles en traitement.
  • La deuxième contient la liste des grilles à traiter à la prochaine étape.
  • La troisième contient la liste des grilles déjà connues.

Méthode de résolution d'une grille

Initialement (niveau 0), la première et la troisième liste contiennent la liste de Traffic! à résoudre; la deuxième liste est vide.

A chaque niveau de la résolution,

  • Pour chaque grille de la première liste, l'ensemble des coups (déplacements des blocs) est calculé.
  • S'il est possible de terminer une grille par le déplacement du bloc à sortir de la grille, c'est le seul coup qui est considéré pour la grille.
  • Si jouer le coup pour la grille en question conduit à une grille inconnue, c'est à dire qui n'est pas dans la troisième liste, cette nouvelle grille est ajoutée à la deuxième liste et à la troisième liste des grilles connues.
  • Sinon un nouveau coup est considéré, jusqu'à épuisement des coups et des grilles de la première liste.
  • A la fin du niveau, la deuxième liste des grilles à traiter prend la place de la première liste des grilles en traitement et la deuxième liste redevient vide.

Solutions de grilles

Niveau Solution Nombre de coups Durée des calculs (HH:MM:SS)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

Conclusions

Ressources

Récupérée de « http://zigloo.ch/index.php/Solution_minimale_du_jeu_Traffic%21 »