Solution minimale du jeu Traffic!

Un article de Wikipedia.

(Différences entre les versions)
(→Introduction)
(→Conclusions)
Ligne 124 : Ligne 124 :
== Conclusions ==
== Conclusions ==
 +
* Le nombre minimal des mouvements nécessaires pour résoudre une grille déterminé par ce logiciel correspond à celui indiqué par le programme Traffic!.
 +
* Dans le programme Traffic! le nombre minimal de mouvements nécessaire à résoudre une grille s'affiche qu'une fois la grille résolue. Une question se pose : ''Est-ce le nombre minimal de mouvements pour résoudre la grille est calculé lors de la résolution de la grille ou est-il connu à priori ?''
 +
== Ressources ==
== Ressources ==
* Jeu '''Rush Hour''' conçu par [http://en.wikipedia.org/wiki/Nob_Yoshigahara Nob Yoshigahara] http://www.thinkfun.com
* Jeu '''Rush Hour''' conçu par [http://en.wikipedia.org/wiki/Nob_Yoshigahara Nob Yoshigahara] http://www.thinkfun.com

Version du 13 avril 2008 à 09:33

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

  • Le nombre minimal des mouvements nécessaires pour résoudre une grille déterminé par ce logiciel correspond à celui indiqué par le programme Traffic!.
  • Dans le programme Traffic! le nombre minimal de mouvements nécessaire à résoudre une grille s'affiche qu'une fois la grille résolue. Une question se pose : Est-ce le nombre minimal de mouvements pour résoudre la grille est calculé lors de la résolution de la grille ou est-il connu à priori ?

Ressources

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