Solution minimale du jeu Traffic!

Un article de Wikipedia.

(Différences entre les versions)
(→Ressources)
Version actuelle (3 mai 2008 à 07:41) (modifier) (défaire)
(→Remarques)
 
(12 révisions intermédiaires masquées)
Ligne 53 : Ligne 53 :
** ''n'' pour les bloc ''normaux''
** ''n'' pour les bloc ''normaux''
** ''p'' pour le bloc ''principal'' à sortir de la grille
** ''p'' pour le bloc ''principal'' à sortir de la grille
 +
 +
==== Remarques ====
 +
* Les images des grilles ont été crées à l'aide de la librairie graphique GD http://www.libgd.org.
 +
* Les animations flash ont été créées à l'aide de la librairie Ming http://www.libming.org.
 +
* Les grilles ''13'', ''14'', ''16'', ''23'' et ''25'' ont été calculées à l'aide du logiciel "Rush Hour" (voir [[Solution minimale du jeu Traffic!#Ressources|Ressources]]) car le Palm bloque durant les calculs ! '''Merci''' à Henrik Theiling pour ce logiciel. Le calcul de n'importe quelle grille prend au maximum 20 secondes avec son logiciel !
=== Solutions de grilles ===
=== Solutions de grilles ===
Ligne 1 249 : Ligne 1 254 :
* 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 ?''
* 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 [[Solution minimale du jeu Traffic!#Ressources|Trafficsamples.pas]] dépasse les 35. Il faut donc procéder en plusieurs étapes pour résoudre les 40 grilles de Traffic!
* PP Compiler génère une erreur de compilation "Out of memory(1)" si le nombre de grilles spécifiées dans [[Solution minimale du jeu Traffic!#Ressources|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.
+
* Sur les 40 grilles, 35 peuvent être résolues par ce programme. Seulement 5 grilles demandant trop de ressources au Palm doivent être calculées différemment.
== Ressources ==
== Ressources ==
Ligne 1 256 : Ligne 1 261 :
* Solution minimale du jeu Traffic! [[Media:Traffic_pas.PDB]] et [[Media:Trafficsamples_pas.PDB]]
* Solution minimale du jeu Traffic! [[Media:Traffic_pas.PDB]] et [[Media:Trafficsamples_pas.PDB]]
* Source [[Traffic.pas]] et [[Trafficsamples.pas]]
* Source [[Traffic.pas]] et [[Trafficsamples.pas]]
-
* Logiciel de résolution Rush Hour disponible depuis le lien http://www.theiling.de/projects/rushhour.html
+
* Logiciel de résolution ''Rush Hour'' disponible depuis le lien http://www.theiling.de/projects/rushhour.html
 +
** Librairie de report d'erreurs [[Media:Liberror-2-1-80011.tgz.bz2]]
 +
** Logiciel de résolution de ''Rush Hour'' [[Media:Rush_hour-0.2.7-src.tar.bz2]]
[[Category:Logiciel]]
[[Category:Logiciel]]
[[Category:Pascal]]
[[Category:Pascal]]
[[Category:Palm]]
[[Category:Palm]]

Version actuelle

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 rouge 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.

Définition d'une grille

Les grilles sont définies dans le fichier Trafficsamples.pas des Ressources.

Les différents blocs de la grilles sont spécifiés par les entrées du tableau de string s avec l'encodage suivant :

  • Position x minimale du bloc
  • Position Texte italiquey minimale du bloc
  • Orientation du bloc
    • v pour vertical
    • h pour horizontal
  • Taille du bloc (2 ou 3)
  • Type de bloc
    • n pour les bloc normaux
    • p pour le bloc principal à sortir de la grille

Remarques

  • Les images des grilles ont été crées à l'aide de la librairie graphique GD http://www.libgd.org.
  • Les animations flash ont été créées à l'aide de la librairie Ming http://www.libming.org.
  • Les grilles 13, 14, 16, 23 et 25 ont été calculées à l'aide du logiciel "Rush Hour" (voir Ressources) car le Palm bloque durant les calculs ! Merci à Henrik Theiling pour ce logiciel. Le calcul de n'importe quelle grille prend au maximum 20 secondes avec son logiciel !

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 Image:Traffic1.jpg 8 Media:Anim1.swf
  1. (5,2)->(2,2)
  2. (6,4)->(6,1)
  3. (1,6)->(2,6)
  4. (1,3)->(1,4)
  5. (1,1)->(1,2)
  6. (3,1)->(1,1)
  7. (4,3)->(4,1)
  8. (2,4)->(5,4)
8 00:05:41 1067
2 Image:Traffic2.jpg 11

Media:Anim2.swf

  1. (5,2)->(4,2)
  2. (6,3)->(6,1)
  3. (1,4)->(2,4)
  4. (1,5)->(1,4)
  5. (4,6)->(1,6)
  6. (5,3)->(5,5)
  7. (4,4)->(4,5)
  8. (2,4)->(5,4)
8 00:29:01 2753
3 Image:Traffic3.jpg 6

Media:Anim3.swf

  1. (6,1)->(6,4)
  2. (3,1)->(5,1)
  3. (4,2)->(4,4)
  4. (2,3)->(5,3)
  5. (4,4)->(4,1)
  6. (2,4)->(3,4)
  7. (2,1)->(2,5)
  8. (3,4)->(2,4)
  9. (4,1)->(4,4)
  10. (5,1)->(2,1)
  11. (5,3)->(2,3)
  12. (6,4)->(6,1)
  13. (4,4)->(4,1)
  14. (2,4)->(5,4)
14 00:01:40 770
4 Image:Traffic4.jpg 7

Media:Anim4.swf

  1. (1,4)->(1,1)
  2. (2,4)->(1,4)
  3. (3,2)->(3,5)
  4. (1,4)->(2,4)
  5. (1,1)->(1,4)
  6. (3,1)->(1,1)
  7. (4,3)->(1,3)
  8. (4,4)->(4,1)
  9. (2,4)->(5,4)
9 00:00:23 356
5 Image:Traffic5.jpg 11

Media:Anim5.swf

  1. (1,4)->(1,1)
  2. (2,4)->(1,4)
  3. (3,2)->(3,5)
  4. (1,4)->(2,4)
  5. (1,1)->(1,4)
  6. (3,1)->(1,1)
  7. (4,3)->(1,3)
  8. (4,4)->(4,1)
  9. (2,4)->(5,4)
9 00:23:14 2139
6 Image:Traffic6.jpg 11

Media:Anim6.swf

  1. (1,4)->(1,1)
  2. (2,4)->(1,4)
  3. (3,2)->(3,5)
  4. (1,4)->(2,4)
  5. (1,1)->(1,4)
  6. (3,1)->(1,1)
  7. (4,3)->(1,3)
  8. (4,4)->(4,1)
  9. (2,4)->(5,4)
9 00:14:30 1637
7 Image:Traffic7.jpg 9

Media:Anim7.swf

  1. (6,3)->(6,2)
  2. (5,5)->(5,2)
  3. (6,5)->(6,4)
  4. (3,6)->(5,6)
  5. (4,4)->(4,5)
  6. (2,4)->(3,4)
  7. (2,5)->(2,2)
  8. (3,4)->(2,4)
  9. (4,5)->(4,4)
  10. (5,6)->(2,6)
  11. (4,4)->(4,5)
  12. (6,4)->(6,5)
  13. (2,4)->(5,4)
13 01:23:17 4613
8 Image:Traffic8.jpg 14

Media:Anim8.swf

  1. (3,5)->(1,5)
  2. (4,6)->(1,6)
  3. (3,3)->(3,5)
  4. (4,3)->(4,5)
  5. (5,3)->(4,3)
  6. (5,4)->(5,5)
  7. (1,4)->(4,4)
  8. (3,1)->(3,3)
  9. (4,1)->(3,1)
  10. (4,2)->(3,2)
  11. (6,4)->(6,1)
  12. (4,4)->(5,4)
12 00:05:05 950
9 Image:Traffic9.jpg 12

Media:Anim9.swf

  1. (5,2)->(5,1)
  2. (1,4)->(2,4)
  3. (1,1)->(1,4)
  4. (2,3)->(1,3)
  5. (4,4)->(4,2)
  6. (5,5)->(4,5)
  7. (2,4)->(3,4)
  8. (2,5)->(2,4)
  9. (3,6)->(2,6)
  10. (5,6)->(4,6)
  11. (6,3)->(6,5)
  12. (3,4)->(5,4)
12 00:01:47 681
10 Image:Traffic10.jpg 12

Media:Anim10.swf

  1. (5,6)->(4,6)
  2. (6,3)->(6,4)
  3. (2,3)->(4,3)
  4. (2,4)->(4,4)
  5. (3,5)->(3,1)
  6. (1,5)->(2,5)
  7. (1,6)->(2,6)
  8. (1,2)->(1,4)
  9. (4,3)->(1,3)
  10. (6,4)->(6,3)
  11. (4,6)->(5,6)
  12. (4,4)->(2,4)
  13. (4,1)->(4,5)
  14. (5,1)->(4,1)
  15. (5,2)->(4,2)
  16. (6,3)->(6,1)
  17. (2,4)->(5,4)
17 00:16:32 1847
11 Image:Traffic11.jpg 8

Media:Anim11.swf

  1. (1,4)->(1,1)
  2. (2,4)->(1,4)
  3. (3,2)->(3,4)
  4. (4,3)->(3,3)
  5. (6,1)->(6,4)
  6. (3,1)->(4,1)
  7. (3,3)->(4,3)
  8. (3,4)->(3,1)
  9. (1,4)->(2,4)
  10. (1,1)->(1,4)
  11. (4,3)->(1,3)
  12. (4,4)->(4,3)
  13. (2,6)->(5,6)
  14. (4,3)->(4,4)
  15. (1,3)->(4,3)
  16. (1,4)->(1,1)
  17. (2,4)->(1,4)
  18. (3,1)->(3,5)
  19. (1,4)->(2,4)
  20. (1,1)->(1,4)
  21. (4,1)->(1,1)
  22. (4,3)->(1,3)
  23. (6,4)->(6,2)
  24. (4,4)->(4,1)
  25. (2,4)->(5,4)
25 00:02:27 821
12 Image:Traffic12.jpg 8

Media:Anim12.swf

  1. (2,6)->(4,6)
  2. (3,3)->(3,4)
  3. (4,3)->(2,3)
  4. (5,1)->(5,4)
  5. (1,1)->(4,1)
  6. (2,3)->(4,3)
  7. (3,4)->(3,1)
  8. (4,6)->(3,6)
  9. (5,4)->(5,5)
  10. (1,4)->(4,4)
  11. (1,5)->(1,4)
  12. (3,6)->(1,6)
  13. (3,1)->(3,4)
  14. (4,1)->(3,1)
  15. (4,3)->(3,3)
  16. (6,4)->(6,1)
  17. (4,4)->(5,4)
17 00:04:45 1267
13 Image:Traffic13.jpg 13

Media:Anim13.swf

  1. (3,4)->(3,2)
  2. (6,3)->(6,4)
  3. (2,3)->(2,2)
  4. (4,4)->(1,4)
  5. (3,2)->(3,4)
  6. (4,3)->(5,3)
  7. (4,1)->(4,4)
  8. (5,3)->(3,3)
  9. (5,2)->(3,2)
  10. (5,5)->(5,2)
  11. (5,1)->(4,1)
  12. (6,4)->(6,1)
  13. (3,6)->(5,6)
  14. (3,4)->(3,5)
  15. (4,4)->(4,5)
  16. (1,4)->(5,4)
16 --- (8213)
14 Image:Traffic14.jpg 12

Media:Anim14.swf

  1. (1,3)->(1,2)
  2. (2,3)->(2,2)
  3. (3,4)->(1,4)
  4. (3,5)->(3,4)
  5. (1,6)->(4,6)
  6. (3,4)->(3,5)
  7. (1,4)->(3,4)
  8. (1,2)->(1,5)
  9. (2,2)->(2,5)
  10. (3,4)->(1,4)
  11. (3,3)->(1,3)
  12. (3,1)->(3,3)
  13. (5,2)->(1,2)
  14. (5,3)->(5,2)
  15. (6,3)->(6,2)
  16. (3,3)->(3,2)
  17. (1,4)->(5,4)
17 --- (9568)
15 Image:Traffic15.jpg 14

Media:Anim15.swf

  1. (4,1)->(5,1)
  2. (2,1)->(3,1)
  3. (1,2)->(1,1)
  4. (2,2)->(2,1)
  5. (2,6)->(1,6)
  6. (4,6)->(5,6)
  7. (3,4)->(1,4)
  8. (3,2)->(3,3)
  9. (4,2)->(4,3)
  10. (5,2)->(3,2)
  11. (5,3)->(5,2)
  12. (6,3)->(6,2)
  13. (3,5)->(5,5)
  14. (3,3)->(3,5)
  15. (4,3)->(4,5)
  16. (1,4)->(3,4)
  17. (1,1)->(1,2)
  18. (2,1)->(2,2)
  19. (3,1)->(1,1)
  20. (5,1)->(3,1)
  21. (5,2)->(5,1)
  22. (6,2)->(6,1)
  23. (3,4)->(5,4)
23 00:01:21 521
16 Image:Traffic16.jpg 11

Media:Anim16.swf

  1. (1,4)->(1,2)
  2. (3,5)->(1,5)
  3. (2,3)->(2,2)
  4. (3,2)->(3,1)
  5. (4,4)->(1,4)
  6. (5,5)->(5,4)
  7. (3,6)->(4,6)
  8. (3,1)->(3,4)
  9. (1,1)->(3,1)
  10. (2,2)->(2,1)
  11. (4,3)->(2,3)
  12. (5,4)->(5,1)
  13. (2,3)->(4,3)
  14. (2,1)->(2,2)
  15. (3,1)->(1,1)
  16. (3,4)->(3,1)
  17. (1,4)->(4,4)
  18. (3,1)->(3,4)
  19. (4,3)->(3,3)
  20. (6,4)->(6,1)
  21. (4,4)->(5,4)
21 --- (2500)
17 Image:Traffic17.jpg 12

Media:Anim17.swf

  1. (5,1)->(5,3)
  2. (6,1)->(6,3)
  3. (3,5)->(2,5)
  4. (4,1)->(4,3)
  5. (1,1)->(4,1)
  6. (1,2)->(4,2)
  7. (3,3)->(3,1)
  8. (1,3)->(2,3)
  9. (2,6)->(4,6)
  10. (1,4)->(2,4)
  11. (1,5)->(1,1)
  12. (2,3)->(1,3)
  13. (2,5)->(1,5)
  14. (2,4)->(1,4)
  15. (3,1)->(3,5)
  16. (1,3)->(2,3)
  17. (1,4)->(2,4)
  18. (1,1)->(1,3)
  19. (4,1)->(1,1)
  20. (4,2)->(1,2)
  21. (4,3)->(4,1)
  22. (5,3)->(5,2)
  23. (6,3)->(6,2)
  24. (2,4)->(5,4)
24 00:28:11 2104
18 Image:Traffic18.jpg 9

Media:Anim18.swf

  1. (1,1)->(4,1)
  2. (1,2)->(1,1)
  3. (2,2)->(5,2)
  4. (2,3)->(4,3)
  5. (2,4)->(1,4)
  6. (3,5)->(3,1)
  7. (1,5)->(2,5)
  8. (1,6)->(2,6)
  9. (1,4)->(2,4)
  10. (1,1)->(1,4)
  11. (4,3)->(1,3)
  12. (4,4)->(4,2)
  13. (2,5)->(5,5)
  14. (2,6)->(5,6)
  15. (4,2)->(4,4)
  16. (1,3)->(4,3)
  17. (1,4)->(1,1)
  18. (2,4)->(1,4)
  19. (3,1)->(3,5)
  20. (1,4)->(2,4)
  21. (1,1)->(1,4)
  22. (4,1)->(1,1)
  23. (4,3)->(1,3)
  24. (4,4)->(4,1)
  25. (2,4)->(5,4)
25 00:11:54 1578
19 Image:Traffic19.jpg 8

Media:Anim19.swf

  1. (2,3)->(2,5)
  2. (3,3)->(1,3)
  3. (3,4)->(1,4)
  4. (3,5)->(3,4)
  5. (4,6)->(3,6)
  6. (5,4)->(5,5)
  7. (5,2)->(5,3)
  8. (1,2)->(4,2)
  9. (3,4)->(3,1)
  10. (1,3)->(3,3)
  11. (1,4)->(3,4)
  12. (2,5)->(2,1)
  13. (3,3)->(1,3)
  14. (3,6)->(1,6)
  15. (3,4)->(1,4)
  16. (3,1)->(3,5)
  17. (1,3)->(3,3)
  18. (1,4)->(3,4)
  19. (2,1)->(2,3)
  20. (4,2)->(2,2)
  21. (5,3)->(5,2)
  22. (3,4)->(5,4)
22 00:00:44 482
20 Image:Traffic20.jpg 10

Media:Anim20.swf

  1. (4,4)->(4,3)
  2. (2,5)->(4,5)
  3. (3,3)->(3,5)
  4. (3,1)->(3,3)
  5. (4,1)->(3,1)
  6. (4,2)->(1,2)
  7. (3,3)->(3,2)
  8. (6,2)->(6,1)
  9. (4,3)->(4,2)
  10. (1,4)->(5,4)
10 00:06:45 1639
21 Image:Traffic21.jpg 7

Media:Anim21.swf

  1. (1,3)->(1,1)
  2. (2,3)->(4,3)
  3. (2,4)->(1,4)
  4. (3,5)->(3,1)
  5. (1,6)->(2,6)
  6. (1,4)->(2,4)
  7. (1,1)->(1,4)
  8. (4,3)->(1,3)
  9. (4,4)->(4,3)
  10. (2,6)->(5,6)
  11. (4,3)->(4,4)
  12. (1,3)->(4,3)
  13. (1,4)->(1,1)
  14. (2,4)->(1,4)
  15. (3,1)->(3,5)
  16. (1,4)->(2,4)
  17. (1,1)->(1,4)
  18. (4,1)->(1,1)
  19. (4,3)->(1,3)
  20. (4,4)->(4,1)
  21. (2,4)->(5,4)
21 00:00:11 255
22 Image:Traffic22.jpg 12

Media:Anim22.swf

  1. (1,1)->(1,2)
  2. (3,2)->(4,2)
  3. (1,4)->(1,5)
  4. (2,4)->(1,4)
  5. (3,5)->(3,2)
  6. (1,4)->(2,4)
  7. (1,5)->(1,4)
  8. (4,6)->(1,6)
  9. (4,3)->(4,4)
  10. (5,3)->(4,3)
  11. (6,1)->(6,3)
  12. (2,1)->(4,1)
  13. (2,2)->(2,1)
  14. (4,2)->(5,2)
  15. (3,2)->(3,1)
  16. (4,3)->(2,3)
  17. (4,4)->(4,2)
  18. (5,5)->(2,5)
  19. (6,3)->(6,5)
  20. (4,2)->(4,4)
  21. (2,3)->(5,3)
  22. (2,1)->(2,2)
  23. (3,1)->(3,2)
  24. (4,1)->(1,1)
  25. (4,4)->(4,1)
  26. (2,4)->(5,4)
26 01:02:04 3572
23 Image:Traffic23.jpg 10

Media:Anim23.swf

  1. (3,1)->(1,1)
  2. (4,2)->(4,1)
  3. (5,3)->(4,3)
  4. (6,4)->(6,3)
  5. (3,6)->(4,6)
  6. (3,4)->(3,5)
  7. (4,4)->(1,4)
  8. (3,5)->(3,4)
  9. (4,6)->(3,6)
  10. (6,3)->(6,4)
  11. (4,3)->(5,3)
  12. (4,1)->(4,2)
  13. (1,1)->(4,1)
  14. (3,2)->(3,1)
  15. (3,4)->(3,3)
  16. (4,5)->(1,5)
  17. (3,3)->(3,4)
  18. (4,2)->(4,4)
  19. (5,3)->(1,3)
  20. (6,4)->(6,3)
  21. (3,6)->(4,6)
  22. (3,4)->(3,5)
  23. (3,1)->(3,3)
  24. (5,2)->(1,2)
  25. (3,3)->(3,2)
  26. (4,4)->(4,2)
  27. (4,1)->(3,1)
  28. (6,3)->(6,1)
  29. (1,4)->(5,4)
29 --- (2354)
24 Image:Traffic24.jpg 10

Media:Anim24.swf

  1. (1,3)->(1,5)
  2. (2,3)->(1,3)
  3. (2,4)->(2,5)
  4. (3,4)->(1,4)
  5. (3,5)->(3,4)
  6. (4,6)->(3,6)
  7. (5,3)->(5,5)
  8. (5,1)->(5,3)
  9. (1,1)->(4,1)
  10. (1,2)->(4,2)
  11. (3,4)->(3,1)
  12. (1,3)->(3,3)
  13. (1,4)->(3,4)
  14. (1,5)->(1,1)
  15. (2,5)->(2,1)
  16. (3,3)->(1,3)
  17. (3,6)->(1,6)
  18. (3,4)->(1,4)
  19. (3,1)->(3,5)
  20. (1,3)->(3,3)
  21. (1,4)->(3,4)
  22. (2,1)->(2,3)
  23. (4,2)->(2,2)
  24. (5,3)->(5,2)
  25. (3,4)->(5,4)
25 01:41:39 4336
25 Image:Traffic25.jpg 13

Media:Anim25.swf

  1. (5,6)->(4,6)
  2. (6,3)->(6,4)
  3. (1,2)->(1,1)
  4. (2,4)->(1,4)
  5. (5,3)->(5,4)
  6. (2,3)->(4,3)
  7. (3,5)->(3,1)
  8. (1,6)->(2,6)
  9. (1,5)->(2,5)
  10. (1,4)->(2,4)
  11. (1,1)->(1,4)
  12. (4,3)->(1,3)
  13. (4,1)->(4,4)
  14. (1,3)->(4,3)
  15. (1,4)->(1,1)
  16. (2,6)->(1,6)
  17. (2,5)->(1,5)
  18. (2,4)->(1,4)
  19. (3,1)->(3,5)
  20. (4,3)->(2,3)
  21. (5,2)->(3,2)
  22. (5,4)->(5,2)
  23. (5,1)->(4,1)
  24. (6,4)->(6,1)
  25. (4,6)->(5,6)
  26. (4,4)->(4,5)
  27. (1,4)->(5,4)
27 --- (8623)
26 Image:Traffic26.jpg 12

Media:Anim26.swf

  1. (1,2)->(1,1)
  2. (2,3)->(1,3)
  3. (6,3)->(6,4)
  4. (6,1)->(6,2)
  5. (4,1)->(5,1)
  6. (4,4)->(4,1)
  7. (2,4)->(3,4)
  8. (2,5)->(2,4)
  9. (4,6)->(1,6)
  10. (5,3)->(5,4)
  11. (1,3)->(3,3)
  12. (6,4)->(6,5)
  13. (2,4)->(2,1)
  14. (3,3)->(1,3)
  15. (3,4)->(2,4)
  16. (4,1)->(4,5)
  17. (5,1)->(4,1)
  18. (6,2)->(6,1)
  19. (1,3)->(4,3)
  20. (3,1)->(3,2)
  21. (1,1)->(1,2)
  22. (2,4)->(3,4)
  23. (2,1)->(2,4)
  24. (4,1)->(1,1)
  25. (3,2)->(3,1)
  26. (4,3)->(2,3)
  27. (5,4)->(5,1)
  28. (3,4)->(5,4)
28 02:14:34 4806
27 Image:Traffic27.jpg 10

Media:Anim27.swf

  1. (6,2)->(6,4)
  2. (4,3)->(5,3)
  3. (4,4)->(4,2)
  4. (2,5)->(4,5)
  5. (2,6)->(4,6)
  6. (3,3)->(3,5)
  7. (1,4)->(2,4)
  8. (1,5)->(1,1)
  9. (2,4)->(1,4)
  10. (3,5)->(3,3)
  11. (4,5)->(1,5)
  12. (3,3)->(3,4)
  13. (4,6)->(1,6)
  14. (4,2)->(4,4)
  15. (5,3)->(1,3)
  16. (3,4)->(3,3)
  17. (4,4)->(4,2)
  18. (1,5)->(4,5)
  19. (3,3)->(3,5)
  20. (1,3)->(2,3)
  21. (1,4)->(2,4)
  22. (1,1)->(1,4)
  23. (2,3)->(1,3)
  24. (3,1)->(3,2)
  25. (4,1)->(1,1)
  26. (6,4)->(6,1)
  27. (4,2)->(4,1)
  28. (2,4)->(5,4)
28 00:30:00 2741
28 Image:Traffic28.jpg 12

Media:Anim28.swf

  1. (6,1)->(6,2)
  2. (3,1)->(5,1)
  3. (1,1)->(3,1)
  4. (1,2)->(1,1)
  5. (2,2)->(2,1)
  6. (4,5)->(4,4)
  7. (1,6)->(4,6)
  8. (3,3)->(3,4)
  9. (4,3)->(1,3)
  10. (4,4)->(4,3)
  11. (5,5)->(4,5)
  12. (6,2)->(6,3)
  13. (3,2)->(4,2)
  14. (3,4)->(3,2)
  15. (4,5)->(1,5)
  16. (3,2)->(3,4)
  17. (4,3)->(4,4)
  18. (1,3)->(4,3)
  19. (1,1)->(1,2)
  20. (2,1)->(2,2)
  21. (3,1)->(1,1)
  22. (5,1)->(4,1)
  23. (3,4)->(3,1)
  24. (4,6)->(1,6)
  25. (4,4)->(4,5)
  26. (1,4)->(4,4)
  27. (3,1)->(3,3)
  28. (4,2)->(3,2)
  29. (6,3)->(6,1)
  30. (4,4)->(5,4)
30 00:17:17 1927
29 Image:Traffic29.jpg 12

Media:Anim29.swf

  1. (6,3)->(6,4)
  2. (4,3)->(5,3)
  3. (4,1)->(4,4)
  4. (2,2)->(4,2)
  5. (5,3)->(4,3)
  6. (6,1)->(6,2)
  7. (1,1)->(4,1)
  8. (1,2)->(1,1)
  9. (2,3)->(1,3)
  10. (3,4)->(3,1)
  11. (1,3)->(2,3)
  12. (1,6)->(2,6)
  13. (1,4)->(2,4)
  14. (1,1)->(1,5)
  15. (2,3)->(1,3)
  16. (2,4)->(1,4)
  17. (3,1)->(3,4)
  18. (4,1)->(1,1)
  19. (6,2)->(6,1)
  20. (4,2)->(2,2)
  21. (4,3)->(5,3)
  22. (4,4)->(4,1)
  23. (5,3)->(3,3)
  24. (5,4)->(5,1)
  25. (2,6)->(4,6)
  26. (3,4)->(3,5)
  27. (1,4)->(4,4)
  28. (3,5)->(3,4)
  29. (4,6)->(3,6)
  30. (6,4)->(6,5)
  31. (4,4)->(5,4)
31 01:54:50 4326
30 Image:Traffic30.jpg 10

Media:Anim30.swf

  1. (3,1)->(4,1)
  2. (1,1)->(2,1)
  3. (3,3)->(4,3)
  4. (1,3)->(2,3)
  5. (1,4)->(1,1)
  6. (2,4)->(1,4)
  7. (3,5)->(3,4)
  8. (4,6)->(3,6)
  9. (6,1)->(6,4)
  10. (4,1)->(5,1)
  11. (4,3)->(5,3)
  12. (4,4)->(4,1)
  13. (5,3)->(4,3)
  14. (6,4)->(6,3)
  15. (3,6)->(4,6)
  16. (3,4)->(3,5)
  17. (1,4)->(4,4)
  18. (1,1)->(1,4)
  19. (2,1)->(1,1)
  20. (2,3)->(1,3)
  21. (3,5)->(3,1)
  22. (1,3)->(2,3)
  23. (1,4)->(1,3)
  24. (4,6)->(1,6)
  25. (6,3)->(6,4)
  26. (4,3)->(5,3)
  27. (4,4)->(2,4)
  28. (4,1)->(4,5)
  29. (5,1)->(4,1)
  30. (5,3)->(4,3)
  31. (6,4)->(6,1)
  32. (2,4)->(5,4)
32 00:05:39 1158
31 Image:Traffic31.jpg 11

Media:Anim31.swf

  1. (1,6)->(2,6)
  2. (1,3)->(1,5)
  3. (2,4)->(1,4)
  4. (3,1)->(3,3)
  5. (1,2)->(4,2)
  6. (3,3)->(3,1)
  7. (1,4)->(2,4)
  8. (1,5)->(1,1)
  9. (2,6)->(1,6)
  10. (2,4)->(1,4)
  11. (3,1)->(3,4)
  12. (4,3)->(1,3)
  13. (3,4)->(3,1)
  14. (4,4)->(4,3)
  15. (5,5)->(4,5)
  16. (6,2)->(6,3)
  17. (4,2)->(5,2)
  18. (4,3)->(4,2)
  19. (1,4)->(4,4)
  20. (3,1)->(3,4)
  21. (1,3)->(2,3)
  22. (1,1)->(1,4)
  23. (2,3)->(1,3)
  24. (3,4)->(3,1)
  25. (1,6)->(2,6)
  26. (1,4)->(1,5)
  27. (4,4)->(1,4)
  28. (3,1)->(3,3)
  29. (4,2)->(4,3)
  30. (5,2)->(1,2)
  31. (3,3)->(3,1)
  32. (4,3)->(4,2)
  33. (1,4)->(4,4)
  34. (3,1)->(3,2)
  35. (4,1)->(3,1)
  36. (6,3)->(6,1)
  37. (4,4)->(5,4)
37 01:18:17 3947
32 Image:Traffic32.jpg 11

Media:Anim32.swf

  1. (4,5)->(4,4)
  2. (5,6)->(4,6)
  3. (6,1)->(6,4)
  4. (4,3)->(5,3)
  5. (4,1)->(4,2)
  6. (1,1)->(5,1)
  7. (4,2)->(4,1)
  8. (1,2)->(1,1)
  9. (2,3)->(1,3)
  10. (5,3)->(4,3)
  11. (6,4)->(6,3)
  12. (3,4)->(3,1)
  13. (4,6)->(5,6)
  14. (4,4)->(4,5)
  15. (1,4)->(4,4)
  16. (3,1)->(3,4)
  17. (1,3)->(2,3)
  18. (1,1)->(1,4)
  19. (2,3)->(1,3)
  20. (3,4)->(3,1)
  21. (1,6)->(2,6)
  22. (1,4)->(1,5)
  23. (4,4)->(1,4)
  24. (3,1)->(3,2)
  25. (4,5)->(4,4)
  26. (5,6)->(4,6)
  27. (6,3)->(6,4)
  28. (4,3)->(5,3)
  29. (4,1)->(4,2)
  30. (5,1)->(1,1)
  31. (4,2)->(4,1)
  32. (5,3)->(4,3)
  33. (6,4)->(6,1)
  34. (3,2)->(3,1)
  35. (4,6)->(5,6)
  36. (4,4)->(4,5)
  37. (1,4)->(5,4)
37 00:01:09 568
33 Image:Traffic33.jpg 12

Media:Anim33.swf

  1. (5,6)->(4,6)
  2. (6,1)->(6,4)
  3. (4,3)->(5,3)
  4. (4,1)->(4,4)
  5. (1,1)->(2,1)
  6. (1,2)->(1,1)
  7. (2,3)->(1,3)
  8. (5,3)->(3,3)
  9. (5,1)->(5,4)
  10. (2,1)->(4,1)
  11. (2,2)->(5,2)
  12. (3,3)->(5,3)
  13. (4,4)->(4,2)
  14. (3,4)->(3,1)
  15. (4,6)->(3,6)
  16. (5,4)->(5,5)
  17. (1,4)->(4,4)
  18. (2,5)->(2,4)
  19. (3,6)->(1,6)
  20. (3,1)->(3,4)
  21. (1,3)->(2,3)
  22. (1,1)->(1,4)
  23. (2,3)->(1,3)
  24. (3,4)->(3,1)
  25. (1,6)->(3,6)
  26. (1,4)->(1,5)
  27. (2,4)->(2,5)
  28. (4,4)->(1,4)
  29. (4,2)->(4,3)
  30. (3,1)->(3,3)
  31. (5,2)->(1,2)
  32. (4,3)->(4,2)
  33. (3,3)->(3,1)
  34. (1,4)->(4,4)
  35. (3,1)->(3,2)
  36. (4,1)->(1,1)
  37. (4,2)->(4,1)
  38. (5,3)->(4,3)
  39. (6,4)->(6,1)
  40. (4,4)->(5,4)
40 01:36:05 3960
34 Image:Traffic34.jpg 12

Media:Anim34.swf

  1. (4,1)->(5,1)
  2. (4,2)->(4,1)
  3. (1,3)->(2,3)
  4. (5,3)->(5,4)
  5. (1,4)->(2,4)
  6. (1,5)->(1,2)
  7. (4,6)->(1,6)
  8. (6,3)->(6,4)
  9. (2,3)->(4,3)
  10. (4,4)->(4,5)
  11. (2,4)->(1,4)
  12. (3,1)->(3,4)
  13. (1,1)->(2,1)
  14. (1,2)->(1,1)
  15. (4,3)->(1,3)
  16. (4,1)->(4,3)
  17. (5,2)->(2,2)
  18. (4,3)->(4,1)
  19. (1,3)->(2,3)
  20. (6,4)->(6,3)
  21. (4,5)->(4,4)
  22. (1,6)->(4,6)
  23. (3,4)->(3,5)
  24. (1,4)->(2,4)
  25. (1,1)->(1,5)
  26. (2,1)->(1,1)
  27. (2,2)->(1,2)
  28. (2,4)->(1,4)
  29. (3,5)->(3,4)
  30. (4,6)->(3,6)
  31. (6,3)->(6,4)
  32. (2,3)->(4,3)
  33. (3,4)->(3,1)
  34. (4,3)->(1,3)
  35. (4,1)->(4,2)
  36. (5,1)->(4,1)
  37. (5,4)->(5,2)
  38. (6,4)->(6,1)
  39. (1,4)->(2,4)
  40. (1,5)->(1,4)
  41. (3,6)->(1,6)
  42. (4,4)->(4,5)
  43. (2,4)->(5,4)
43 01:58:33 4364
35 Image:Traffic35.jpg 11

Media:Anim35.swf

  1. (1,1)->(2,1)
  2. (5,1)->(5,4)
  3. (1,2)->(1,1)
  4. (2,3)->(1,3)
  5. (6,4)->(6,3)
  6. (4,6)->(5,6)
  7. (4,4)->(4,5)
  8. (4,1)->(4,3)
  9. (2,1)->(5,1)
  10. (2,2)->(5,2)
  11. (4,3)->(4,1)
  12. (4,5)->(4,4)
  13. (5,6)->(4,6)
  14. (6,3)->(6,4)
  15. (1,3)->(4,3)
  16. (3,4)->(3,1)
  17. (1,4)->(2,4)
  18. (1,1)->(1,5)
  19. (2,4)->(1,4)
  20. (3,1)->(3,4)
  21. (4,3)->(1,3)
  22. (6,4)->(6,3)
  23. (4,6)->(5,6)
  24. (4,4)->(4,5)
  25. (4,1)->(4,3)
  26. (5,1)->(1,1)
  27. (5,2)->(1,2)
  28. (4,3)->(4,1)
  29. (5,4)->(5,1)
  30. (4,5)->(4,4)
  31. (5,6)->(4,6)
  32. (6,3)->(6,4)
  33. (1,3)->(4,3)
  34. (3,4)->(3,1)
  35. (4,6)->(2,6)
  36. (4,4)->(4,5)
  37. (1,4)->(4,4)
  38. (1,5)->(1,4)
  39. (2,6)->(1,6)
  40. (3,1)->(3,4)
  41. (4,3)->(3,3)
  42. (6,4)->(6,1)
  43. (4,4)->(5,4)
43 01:25:03 3963
36 Image:Traffic36.jpg 12

Media:Anim36.swf

  1. (4,2)->(4,1)
  2. (1,3)->(2,3)
  3. (1,4)->(1,3)
  4. (3,5)->(4,5)
  5. (2,6)->(1,6)
  6. (5,6)->(4,6)
  7. (6,3)->(6,4)
  8. (2,3)->(4,3)
  9. (3,4)->(4,4)
  10. (3,1)->(3,4)
  11. (4,3)->(3,3)
  12. (6,4)->(6,3)
  13. (4,6)->(5,6)
  14. (1,6)->(2,6)
  15. (1,3)->(1,4)
  16. (3,3)->(1,3)
  17. (4,1)->(4,2)
  18. (1,1)->(5,1)
  19. (4,2)->(4,1)
  20. (1,3)->(2,3)
  21. (1,4)->(1,3)
  22. (2,6)->(1,6)
  23. (5,6)->(4,6)
  24. (6,3)->(6,4)
  25. (2,3)->(4,3)
  26. (3,4)->(3,1)
  27. (4,3)->(3,3)
  28. (6,4)->(6,3)
  29. (2,4)->(2,1)
  30. (4,5)->(2,5)
  31. (4,6)->(5,6)
  32. (1,6)->(2,6)
  33. (1,3)->(1,4)
  34. (3,3)->(1,3)
  35. (4,4)->(2,4)
  36. (4,1)->(4,4)
  37. (5,1)->(4,1)
  38. (5,2)->(4,2)
  39. (1,3)->(2,3)
  40. (6,3)->(6,1)
  41. (1,4)->(1,3)
  42. (2,6)->(1,6)
  43. (4,4)->(4,5)
  44. (2,4)->(5,4)
44 00:33:37 2556
37 Image:Traffic37.jpg 13

Media:Anim37.swf

  1. (1,1)->(2,1)
  2. (1,2)->(1,1)
  3. (2,4)->(1,4)
  4. (3,5)->(3,4)
  5. (5,6)->(3,6)
  6. (5,3)->(5,4)
  7. (6,3)->(6,4)
  8. (2,3)->(4,3)
  9. (3,4)->(3,2)
  10. (1,5)->(2,5)
  11. (1,4)->(2,4)
  12. (1,1)->(1,2)
  13. (2,1)->(1,1)
  14. (3,2)->(3,1)
  15. (4,3)->(2,3)
  16. (5,4)->(5,3)
  17. (3,6)->(4,6)
  18. (1,6)->(2,6)
  19. (1,2)->(1,4)
  20. (2,3)->(1,3)
  21. (4,1)->(4,4)
  22. (5,1)->(4,1)
  23. (1,3)->(2,3)
  24. (1,4)->(1,3)
  25. (2,6)->(1,6)
  26. (4,6)->(3,6)
  27. (5,3)->(5,4)
  28. (2,3)->(4,3)
  29. (3,1)->(3,2)
  30. (1,1)->(2,1)
  31. (1,3)->(1,1)
  32. (2,5)->(1,5)
  33. (2,4)->(1,4)
  34. (3,2)->(3,4)
  35. (5,2)->(3,2)
  36. (4,3)->(2,3)
  37. (5,4)->(5,3)
  38. (6,4)->(6,1)
  39. (3,6)->(5,6)
  40. (4,4)->(4,5)
  41. (3,4)->(3,5)
  42. (1,4)->(2,4)
  43. (1,1)->(1,2)
  44. (2,1)->(1,1)
  45. (4,1)->(3,1)
  46. (5,3)->(5,1)
  47. (2,4)->(5,4)
47 00:24:18 1941
38 Image:Traffic38.jpg 11

Media:Anim38.swf

  1. (4,6)->(3,6)
  2. (6,2)->(6,4)
  3. (4,2)->(5,2)
  4. (4,3)->(5,3)
  5. (4,4)->(4,3)
  6. (2,5)->(4,5)
  7. (3,3)->(3,4)
  8. (3,1)->(3,2)
  9. (4,1)->(1,1)
  10. (4,3)->(4,1)
  11. (5,3)->(4,3)
  12. (6,4)->(6,3)
  13. (3,6)->(4,6)
  14. (3,4)->(3,5)
  15. (1,4)->(2,4)
  16. (1,5)->(1,2)
  17. (2,4)->(1,4)
  18. (3,5)->(3,4)
  19. (4,6)->(3,6)
  20. (6,3)->(6,4)
  21. (4,3)->(5,3)
  22. (4,1)->(4,2)
  23. (1,1)->(4,1)
  24. (3,2)->(3,1)
  25. (3,4)->(3,3)
  26. (1,2)->(1,1)
  27. (4,5)->(1,5)
  28. (3,3)->(3,4)
  29. (4,2)->(4,4)
  30. (5,3)->(1,3)
  31. (6,4)->(6,3)
  32. (3,4)->(3,3)
  33. (4,4)->(4,3)
  34. (1,5)->(4,5)
  35. (3,6)->(4,6)
  36. (3,3)->(3,5)
  37. (1,3)->(2,3)
  38. (1,4)->(2,4)
  39. (1,1)->(1,5)
  40. (2,3)->(1,3)
  41. (2,4)->(1,4)
  42. (3,1)->(3,3)
  43. (4,1)->(3,1)
  44. (5,2)->(1,2)
  45. (3,3)->(3,2)
  46. (6,3)->(6,1)
  47. (4,3)->(4,2)
  48. (1,4)->(5,4)
48 01:01:16 3755
39 Image:Traffic39.jpg 12

Media:Anim39.swf

  1. (3,1)->(5,1)
  2. (3,2)->(4,2)
  3. (3,3)->(3,1)
  4. (3,5)->(3,4)
  5. (4,6)->(3,6)
  6. (6,2)->(6,4)
  7. (4,2)->(5,2)
  8. (4,3)->(5,3)
  9. (4,4)->(4,1)
  10. (5,3)->(4,3)
  11. (6,4)->(6,3)
  12. (3,6)->(4,6)
  13. (3,4)->(3,5)
  14. (1,4)->(4,4)
  15. (3,5)->(3,4)
  16. (4,6)->(3,6)
  17. (6,3)->(6,4)
  18. (4,3)->(5,3)
  19. (1,3)->(3,3)
  20. (1,1)->(1,5)
  21. (2,1)->(2,5)
  22. (3,3)->(1,3)
  23. (5,3)->(4,3)
  24. (6,4)->(6,3)
  25. (3,6)->(4,6)
  26. (3,4)->(3,5)
  27. (4,4)->(1,4)
  28. (3,5)->(3,4)
  29. (4,6)->(3,6)
  30. (6,3)->(6,4)
  31. (4,3)->(5,3)
  32. (4,1)->(4,4)
  33. (5,3)->(4,3)
  34. (6,4)->(6,3)
  35. (3,6)->(4,6)
  36. (3,4)->(3,5)
  37. (3,1)->(3,3)
  38. (5,1)->(2,1)
  39. (5,2)->(1,2)
  40. (3,3)->(3,2)
  41. (3,5)->(3,4)
  42. (4,6)->(3,6)
  43. (6,3)->(6,4)
  44. (4,3)->(5,3)
  45. (4,4)->(4,1)
  46. (5,3)->(4,3)
  47. (6,4)->(6,1)
  48. (3,6)->(4,6)
  49. (3,4)->(3,5)
  50. (1,4)->(5,4)
50 00:59:53 3581
40 Image:Traffic40.jpg 13 Media:Anim40.swf
  1. (4,1)->(5,1)
  2. (4,2)->(4,1)
  3. (6,3)->(6,4)
  4. (1,3)->(4,3)
  5. (3,1)->(3,2)
  6. (1,1)->(2,1)
  7. (1,4)->(1,1)
  8. (2,4)->(2,2)
  9. (2,6)->(1,6)
  10. (3,4)->(3,5)
  11. (4,4)->(1,4)
  12. (3,5)->(3,4)
  13. (5,5)->(5,4)
  14. (1,6)->(4,6)
  15. (3,4)->(3,5)
  16. (1,4)->(3,4)
  17. (1,1)->(1,4)
  18. (2,1)->(1,1)
  19. (3,2)->(3,1)
  20. (2,2)->(2,5)
  21. (4,3)->(1,3)
  22. (6,4)->(6,3)
  23. (4,6)->(5,6)
  24. (3,4)->(2,4)
  25. (4,1)->(4,5)
  26. (5,1)->(4,1)
  27. (5,2)->(4,2)
  28. (1,3)->(3,3)
  29. (2,4)->(3,4)
  30. (2,5)->(2,2)
  31. (3,4)->(2,4)
  32. (4,5)->(4,4)
  33. (5,6)->(4,6)
  34. (6,3)->(6,4)
  35. (3,3)->(4,3)
  36. (3,1)->(3,2)
  37. (1,1)->(2,1)
  38. (1,4)->(1,1)
  39. (2,4)->(1,4)
  40. (3,5)->(3,4)
  41. (4,6)->(1,6)
  42. (4,4)->(4,5)
  43. (3,4)->(3,5)
  44. (5,4)->(5,5)
  45. (1,4)->(2,4)
  46. (1,1)->(1,2)
  47. (2,1)->(1,1)
  48. (3,2)->(3,1)
  49. (4,3)->(3,3)
  50. (6,4)->(6,1)
  51. (2,4)->(5,4)
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!
  • Sur les 40 grilles, 35 peuvent être résolues par ce programme. Seulement 5 grilles demandant trop de ressources au Palm doivent être calculées différemment.

Ressources

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