Un article de Wikipedia.

Version du 21 avril 2008 à 06:26

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! :

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	Grille	Nombre de blocs	Solution	Nombre de coups	Durée des calculs (HH:MM:SS)	Nombre de grilles différentes
1		8	Media:Anim1.swf (5,2)->(2,2) (6,4)->(6,1) (1,6)->(2,6) (1,3)->(1,4) (1,1)->(1,2) (3,1)->(1,1) (4,3)->(4,1) (2,4)->(5,4)	8	00:05:41	1067
2		11		8	00:29:01	2753
3		6		14	00:01:40	770
4		7		9	00:00:23	356
5		11		9	00:23:14	2139
6		11		9	00:14:30	1637
7		9		13	01:23:17	4613
8		14		12	00:05:05	950
9		12		12	00:01:47	681
10		12		17	00:16:32	1847
11		8		25
12		8		17	00:04:45	1267
13		13		16
14		12		17
15		14		23
16		11		21
17		12		24
18		9		25
19		8		22
20		9		10
21		7		21
22		12		26
23		10		29
24		10		25
25		13		27
26		12		28
27		10		28
28		12		30
29		12		31
30		10		32	00:05:39	1158
31		11		37	01:18:17	3947
32		11		37	00:01:09	568
33		12		40	01:36:05	3960
34		12		43	01:58:33	4364
35		11		43
36		12		44	00:33:37	2556
37		13		47	00:24:18	1941
38		11		48	01:01:16	3755
39		12		50	00:59:53	3581
40		13		51	00:52:22	3024

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 que le nombre minimal de mouvements pour résoudre la grille est calculé lors de la résolution de la grille ou est-il préalablement connu ?
• PP Compiler génère une erreur de compilation "Out of memory(1)" si le nombre de grilles spécifiées dans Trafficsamples.pas dépasse les 35. Il faut donc procéder en plusieurs étapes pour résoudre les 40 grilles de Traffic!
• Un affichage graphique de la grille et de sa solution serait avantageux.

Ressources

• Jeu Rush Hour conçu par Nob Yoshigahara http://www.thinkfun.com
• Jeu gratuit Traffic! Media:Traffic.zip
• Solution minimale du jeu Traffic! Media:Traffic_pas.PDB et Media:Trafficsamples_pas.PDB
• Source Traffic.pas et Trafficsamples.pas