Solution minimale du jeu Traffic!

Un article de Wikipedia.

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

Version du 13 avril 2008 à 09:09

Sommaire

Solution minimale du jeu Traffic!

But

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

Introduction

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 »