1. Recherche de solution du "Solitaire"

Les règles générales des "Défis C & C++" sont décrites à cet endroit. Certaines de ces règles sont modifiées par le présent document.

Le défi de ce mois consiste à créer un programme qui recherche et affiche une solution au jeu de "Solitaire".

Ce document présente :

  • Le rappel des règles du jeu de "Solitaire",
  • La description de ce que doit faire le programme pour répondre au besoin de ce défi,
  • L'organisation mise en place autour de ce défi.

2. Rappel des règles du jeu de "Solitaire"

Ce paragraphe s'inspire largement de la description faite par Wikipédia.

Image non disponible
Solitaire

2.1. Histoire du jeu

L'origine exacte du "Solitaire" est imprécise : une légende veut qu'il ait été inventé par un prisonnier de la Bastille inspiré par un tablier du "jeu du renard et des poules" (Fox and Geese) alors qu'un texte d'Ovide le décrirait en détail. Il aurait aussi été inventé au XVIe siècle par un Français explorant l'Amérique en observant un jeu amérindien.

Une gravure de 1697 représente la Princesse de Soubise jouant au "Solitaire". Le premier texte français décrivant le "Solitaire" semble remonter à 1710 et être dû à G. W. von Leibniz. Son engouement fut important au XVIIIe siècle.

2.2. Les différents types de plateau

Plusieurs types de plateau de jeu existent. Les plus courants sont les plateaux anglais (en forme de Croix grecque) et européens (en forme de cercle). En comptant celui du milieu, le plateau anglais compte 33 trous et l'européen 37. Il existe aussi des plateau en forme de triangle comptant 15 trous.

Image non disponible
Différents plateau

Les différents types de plateau :

  1. Européen, XVIIe siècle, 37 trous;
  2. J. C. Wiegleb, 1779, Allemagne, 45 trous;
  3. Asymétrique 3-3-2-2, XXe siècle;
  4. Anglais, 33 trous;
  5. Diamant, 41 trous;
  6. Triangulaire, 15 trous.

2.3. But du jeu

Le but du jeu est très simple puisqu'il consiste à enlever toutes les billes du plateau sauf une pour n'en conserver qu'une seule.

2.4. Déroulement du jeu

Pour supprimer une pièce, il faut que deux pièces soient adjacentes et suivies d'une case vide. La première pièce "saute" par-dessus la seconde et rejoint la case vide. La seconde pièce est alors retirée du tablier. On ne peut sauter qu'horizontalement ou verticalement, et une seule pièce à la fois.

2.5. Les variantes du jeu

Les variantes du Solitaire concernent essentiellement :

  • La forme du plateau de jeu,
  • La position initiale du premier trou,
  • La position finale de la dernière pièce.

3. Spécification du programme

3.1. Fonctionnement du programme

Le programme doit utiliser les règles spécifiées dans le paragraphe précédent

Le programme doit rechercher et afficher la liste des coups à jouer pour obtenir la solution (ou une des solutions s'il y en a plusieurs) ainsi qu'éventuellement un système de coordonnées permettant de reproduire les coups à jouer.

S'il n'y a pas de solution, le programme doit le détecter et l'afficher.

3.2. Paramètres du programme

Le programme doit accepter les paramètres suivants :

  • "-h". Cette option affiche l'aide en ligne du programme. A l'issue, le programme doit s'arrêter.
  • "-v". Cette option affiche le copyright du programme. A l'issue, le programme doit s'arrêter.
  • "-f <fichier>". Cette option permet d'indiquer au programme le nom du fichier décrivant le plateau de jeu à utiliser.

3.3. Format du fichier de description du plateau de jeu

La forme du plateau de jeu n'est pas connue par le programme, elle figure dans un fichier annexe.

Le format du fichier décrivant le plateau de jeu est le suivant :

  • C'est un fichier texte pouvant contenir plusieurs lignes,
  • Chaque caractère peut être " x " ou " . " ou " " (espace),
    • Le caractère « » (espace) signifie que cette case est interdite.
    • Le caractère « x » signifie que la case est initialement occupée.
    • Le caractère « . » signifie que la case est initialement vide. Il signifie aussi que la dernière bille restante doit être sur cette case pour que la solution soit valide (règle particulière du « Solitaire » pour ce défi).
  • Les lignes contenant des caractères invalides (autres que " x " ou " . " ou " " (espace) doivent être complètement ignorées.

L'exemple suivant montre le contenu d'un fichier permettant de spécifier la forme du plateau de jeu ainsi que la position initiale du premier trou et donc la position finale de la dernière bille devant rester en jeu.

 
Sélectionnez
  xxx
  xxx
xxxxxxx
xxx.xxx
xxxxxxx
  xxx
  xxx

3.4. Contraintes supplémentaires

Les contraintes suivantes doivent être respectées :

  • Le programme doit être écrit en C ou en C++.
  • Le programme doit être écrit pour les environnements Microsoft ou Linux.
  • L'environnement de développement utilisé pour écrire le programme est libre.
  • Le programme doit fonctionner en mode « console » uniquement.
  • L'usage des librairies externes s'il n'est pas interdit doit être très limité. Le challenger ne doit pas perdre de vue que le programme doit pouvoir s'exécuter dans un environnement qui n'est pas forcément un environnement de développement.
  • Le programme doit être livré avec une documentation décrivant le fonctionnement interne du programme, les algorithmes utilisés, les techniques de développement utilisées et tout les autres choses qui pourraient être intéressantes.
  • Le programme doit être livré avec une description sur la manière de recompiler entièrement le programme.

4. Déroulement du défi

4.1. Durée du défi

La durée du défi est de 5 semaines à compter de son ouverture publique. Cette durée pourra éventuellement être modifiée si des conditions particulières l'exigent.

La date de début du défi est fixée au lundi 2 février et la date de fin des soumissions des projets est fixée au dimanche 8 mars 2009 à minuit (c'est la date et heure de dépôt du fichier qui fera foi).

4.2. Critères d'évaluation des programmes

Les différents programmes des challengers seront notés sur les points suivants :

  • Respect des spécifications imposées.
  • Capacité du programme à résister à un mauvais paramètre.
  • Capacité du programme à résister à un mauvais format de fichier de spécification du plateau.
  • Obtention d'une solution valide.
  • Affichage de la solution.
  • Comportement face à une solution impossible.
  • Vitesse d'obtention de la solution.
  • Aspect extérieur du programme.
  • Lisibilité du code.
  • Simplicité du code.
  • Innovation dans les idées implémentées dans le code.
  • Complétude de la procédure de recompilation du programme.
  • Utilisation de librairies externes.
  • Recompilation du programme.

4.3. Composition du jury

Le jury est composé des personnes suivantes :

5. Analyse des résultats

5.1. Participants

Les personnes ayant participé jusqu'au bout à ce défi sont par ordre alphabétique :

Nous les remercions pour de leur participation à ce défi ainsi que tous les autres participants qui ne sont pas allées jusqu'au bout de la démarche mais qui ont tenté de participer.

5.2. Critères de notations

Chacun des projets proposés est noté sur 20 et les critères de notation retenus pour ce défi sont les suivants :

  • Fonctionnement du programme (sur 7 points)
    • Capacité du programme à résister à un mauvais paramètre (Test des paramètres).
    • Capacité du programme à résister à un mauvais format de fichier de spécification du plateau (Test du programme avec plusieurs fichiers).
    • Obtention d'une solution valide (Test du programme avec un fichier témoin).
    • Affichage de la solution (Test du programme avec un fichier témoin).
    • Vitesse d'obtention de la solution (Test du programme avec un fichier témoin).
    • Comportement face à une solution impossible (Test du programme avec un fichier témoin).
  • Documentation (sur 3 points)
    • Complétude par rapport à ce qui est demandé.
    • Innovation dans les idées implémentées dans le code.
  • Analyse du code (sur 7 points)
    • Aspect extérieur du programme.
    • Découpage en module/classe.
    • Organisation des fichiers.
    • Lisibilité du code.
    • Simplicité du code.
    • Bonus C vs C++ (cet extra bonus est fait pour redonner un petit avantage aux programmes écrits en C).
  • Recompilation (sur 3 points)
    • Complétude de la procédure de recompilation du programme.
    • Non utilisation de librairies externes.
    • Recompilation du programme.

5.3. Comportement attendu du programme

Ligne de commande Comportement attendu
binaire bla bla doit dire que les paramètres "bla" et "bla" sont incorrect/interdit
binaire -h doit afficher l'aide en ligne (pas d'erreur comme quoi il n'y a pas de fichier à analyser)
binaire -v doit afficher le numéro de version (pas d'erreur comme quoi il n'y a pas de fichier à analyser)
binaire -h -v comportement non spécifié, à voir :-)
binaire -f "fichier_inexistant" doit dire que le fichier est inexistant
binaire -f vide.txt doit dire que le fichier est vide ou alors qu'il n'y a pas de solution
binaire -f impossible.txt doit dire qu'il n'y a pas de solution
binaire -f invalide1.txt doit dire qu'il n'y a pas de solution
binaire -f invalide2.txt doit dire qu'il n'y a pas de solution
binaire -f simple.txt doit trouver et afficher rapidement (quelques secondes) 1 solution
binaire -f autre.txt doit trouver et afficher 1 solution (la durée de résolution peut être plus longue)

Les fichiers de test soumis aux différents projets sont les suivants :

invalide1.txt
Sélectionnez
xxx
xxx
xxx
invalide2.txt
Sélectionnez
kfdkhdfsk
X.x
xxx
xxx
xxx
impossible.txt
Sélectionnez
xxx
x.x
xxx
simple.txt
Sélectionnez
  xxx
  xxx
xxxxxxx
xxx.xxx
xxxxxxx
  xxx
  xxx
autre.txt
Sélectionnez
xxxxxx
xxxxxx
xx.xxx
xxxxxx
xxxxxx
xxxxxx

5.4. Notes des participants

  • D[r]eadLock a obtenu une note de 14/20. Cette note prend en compte le bonus de 2 points attribués aux projets écrits en C.
  • Sylvain Togni a obtenu une note de 16/20.
  • Ulmo a obtenu une note de 13/20.

Le gagnant de ce défi est donc Sylvain Togni et nous le félicitons tous.

De manière globale, on retiendra :

  • Sylvain Togni, un vrai travail de recherche d'algorithme, une présentation des résultats soignée, un temps d'exécution très rapide, un algorithme de détection des solutions impossibles mis en défaut 1 seule fois.
  • Ulmo, un travail de recherche d'algorithme (un peu moins poussé), une présentation des résultats un peu brouillon, un temps d'exécution assez long.
  • D[r]eadLock : Un travail en C (saluons l'effort), un algorithme simple (par brut force) mais qui montre ses limites sur des plateaux un peu plus complexes.

5.5. Commentaires sur les solutions proposées

5.5.1. D[r]eadLock

La solution proposée par D[r]eadLock peut être téléchargée ici (format zip) ou ici (format tgz). Il s'agit d'une solution développée avec gcc sous Linux. Le temps de réalisation est de 10 heures.

L'algorithme implémenté est un algorithme de type brute-force. Par manque de temps et aussi de connaissance il n'a pas été possible d'implémenter un autre algorithme plus optimisé. Avec plus de temps, la solution se serait rapprochée de ce qui est décrit sur ce site.

Critère   Note
Fonctionnement du programme   5/7
  Capacité du programme à résister à un mauvais paramètre (Test des paramètres) OK. Simple et efficace
  Capacité du programme à résister à un mauvais format de fichier de spécification du plateau (Test du programme avec plusieurs fichiers) OK, sort en erreur en précisant que l'on a déjà donné le premier fichier
  Obtention d'une solution valide (Test du programme avec un fichier témoin) OK avec le plateau simple. Pas trouvé de solution pour le plateau plus complexe
  Affichage de la solution (Test du programme avec un fichier témoin) OK, deux affichages disponibles (un simple avec juste les coordonnées, un plus complet avec une représentation du tableau de jeu)
  Vitesse d'obtention de la solution (Test du programme avec un fichier témoin) OK pour la solution simple. Temps trop long pour la solution plus complexe
  Comportement face à une solution impossible (Test du programme avec un fichier témoin) OK, en un temps très court
Documentation   1/3
  Complétude par rapport à ce qui est demandé le programme fait exactement tout ce qui est demandé
  Innovation dans les idées implémentées dans le code algorithme brute-force, qui est bon sur les solutions simples, mais devient très limité sur les plateaux plus complexes
Analyse du code   5,5/7
  Aspect extérieur du programme 1 seul fichier C de 1006 lignes, pas de fichier d'en-tête
  Découpage en module/classe Pas de découpage en modules. Bon découpage en fonctions, avec des fonctions courtes, donc plus facilement lisibles
  Organisation des fichiers 1 seul fichier un peu long. Il aurait été préférable pour gagner en lisibilité d'utiliser un fichier d'en-tête pour toutes les définitions nécessaires au programme
  Lisibilité du code Code un peu complexe, mais relativement agréable a lire. Manque un peu d'espacement et de commentaires par endroit
  Simplicité du code L'algorithme est simple et efficace, mais le code est complexe a lire
  Bonus C vs C++ (cet extra bonus est fait pour redonner un petit avantage aux programmes écrits en C) Oui, 2 points
Recompilation   2,5/3
  Complétude de la procédure de recompilation du programme OK, fichier Makefile livré avec le programme
  Non utilisation de librairies externes OK, pas de librairie externe
  Recompilation du programme Compile sans problème mais 3 warnings sont générés avec gcc 3.3

Le résultat présenté par le programme présente la forme suivante :

 
Sélectionnez

$> ./solitaire -f simple.txt
Found real plateau starting at j = 2
Using hash of 18 bits (2.62e+05 entries)
Vertical      (|) symetry found
X/Y 0123456 (32)
00:
01:
02:   xxx
03:   xxx
04: xxxxxxx
05: xxx.xxx
06: xxxxxxx
07:   xxx
08:   xxx
[0]3:3 -> Sud
[1]4:1 -> Est
[2]2:2 -> Sud
[3]2:4 -> Ouest
[4]4:3 -> Ouest
[5]4:0 -> Est
[6]4:4 -> Nord
[7]4:6 -> Ouest
[8]5:2 -> Nord
[9]2:2 -> Sud
[10]5:0 -> Est
[11]5:2 -> Nord
[12]5:4 -> Nord
[13]2:4 -> Sud
[14]5:6 -> Ouest
[15]5:4 -> Nord
[16]7:2 -> Nord
[17]6:0 -> Est
[18]6:2 -> Nord
[19]3:2 -> Sud
[20]5:2 -> Est
[21]6:4 -> Nord
[22]3:4 -> Sud
[23]6:6 -> Ouest
[24]6:3 -> Est
[25]8:4 -> Nord
[26]5:4 -> Sud
[27]8:2 -> Est
[28]8:4 -> Nord
[29]6:5 -> Ouest
[30]7:3 -> Nord

5.5.2. Sylvain Togni

La solution proposée par Sylvain Togni peut être téléchargée ici. Il s'agit d'une solution développée avec Visual Studio Express 2005 sur une machine Windows XP. Le temps de réalisation est de 30 heures.

L'algorithme utilisé est de type « beam search », c'est à dire un parcours en largeur du graphe des plateaux, en ne gardant à chaque niveau que les n-meilleurs plateaux au sens d'une heuristique.

Algorithme
Sélectionnez

    fonction beamSearch (p1:plateau, p2:plateau, taille:entier) : chemin
        début
            b1:beam
			n:entier
            b1 <- p1
			pour n décroissant de nombreDePions(p1) à nombreDePions(p2)+1 faire
			    b2:beam
				pour tous noeud dans b1 faire
					pour tous coup valide faire
						b2 <- b2 + coup
					fpour
				fpour
				échange(b1, b2)
			fpour
			si b1 contient p2
				retourne chemin(p1, p2);
			fsi
        fin

Cet algorithme est répété un certain nombre de fois, avec des tailles de beam de plus en plus grandes, jusqu'à l'obtention d'une solution ou jusqu'à avoir parcouru tous les plateaux atteignables.

Algorithme
Sélectionnez

    fonction rechercheChemin (p1:plateau, p2:plateau) : chemin
        début
            taille : entier
            taille <- 1
            tant que !beamSearch(p1, p2, taille)
                taille <- taille*2
            fin
        fin

L'heuristique utilisée part du principe qu'à un niveau donné, plus les pions sur un plateau sont resserrés, plus le plateau à de chances de mener à une solution. La grandeur utilisée est la somme des carrés des écarts types des coordonnées des pions, qui à l'avantage d'être facilement et rapidement calculable avec des opérations entières :

heuristique := \sum{i^2 + j^2}\sum{1} - \sum{i}^2 - \sum{j}^2

Cet algorithme à base de beam search semble largement surpasser les algorithmes de type backtracking, y compris ceux utilisant le même type d'heuristique. Il converge plus rapidement vers une solution et consomme moins de mémoire, étant donné qu'il n'a pas besoin de stocker tous les plateaux visités, mais seulement ceux sur deux niveaux consécutifs à la fois.

Néanmoins, pour gérer plus efficacement les plateaux n'ayant aucune solution, un test de non-faisabilité a été ajouté au début de l'algorithme. Connu dans la littérature sous le nom de « règle de trois », il consiste à utiliser une fonction phi() qui associe une valeur phi(p) à chaque plateau p avec la propriété que phi(p + c) = phi(p) quelque soit le coup valide c. La fonction phi() est donc constante tout au long du jeu, sur tous les plateaux atteignables. Ce qui signifie que si phi(p0) != phi(p1), p0 étant le plateau initial et p1 le plateau final, alors le plateau ne peut avoir de solution. À noter que l'inverse n'est pas garantis, mais en pratique la règle de trois permet d'écarter la plupart des plateaux sans solution, évitant ainsi une longue vérification exhaustive.

Le lecteur qui souhaiterais plus de détails sur la règle de trois ou sur d'autres aspects du jeu du Solitaire pourra se reporter au site suivant : http://eternitygames.free.fr/Solitaire.html

Critère   Note
Fonctionnement du programme   6/7
  Capacité du programme à résister à un mauvais paramètre (Test des paramètres) OK
  Capacité du programme à résister à un mauvais format de fichier de spécification du plateau (Test du programme avec plusieurs fichiers) OK, une petite amélioration est possible dans la mémorisation du plateau de jeu qui ne devrait pas avoir d'influence sur les performances du programme
  Obtention d'une solution valide (Test du programme avec un fichier témoin) OK, mis en défaut avec un fichier (pas trouvé de solutions mais semble tout de même avoir une solution)
  Affichage de la solution (Test du programme avec un fichier témoin) OK
  Vitesse d'obtention de la solution (Test du programme avec un fichier témoin) OK et extrêmement rapide
  Comportement face à une solution impossible (Test du programme avec un fichier témoin) OK
Documentation   2/3
  Complétude par rapport à ce qui est demandé Les explications données sur l'algorithme utilisé sont un peu superficielles, il aurait été utile d'approfondir.
  Innovation dans les idées implémentées dans le code OK
Analyse du code   5/7
  Aspect extérieur du programme OK
  Découpage en module/classe OK, 4 classes + quelques fonctions globales
  Organisation des fichiers Aurait mérité un découpage plus fin
  Lisibilité du code OK, code agréable à lire, bien indenté et commenté quand il le faut
  Simplicité du code OK, pas de structure de code compliquée
  Bonus C vs C++ (cet extra bonus est fait pour redonner un petit avantage aux programmes écrits en C) Non
Recompilation   3/3
  Complétude de la procédure de recompilation du programme OK
  Non utilisation de librairies externes utilisation de la STL
  Recompilation du programme OK, aucun problème de génération d'une version en mode release ou d'une debug. 0 warning

On notera les points suivants :

  • Petite amélioration/optimisation faisable : suppression de l'espace en début de ligne si toutes les lignes ont un espace en début de ligne.
  • La classe Beam est une classe inline only, le mot clé explicite inline devant chacune des fonctions auraient put être rajouté.
  • La classe Beam est déclarée et définie dans le fichier Solveur.cpp. Elle aurait mérité un fichier à part (Beam.h).
  • La structure Noeud est déclarée et définie dans le fichier Solveur.cpp. Elle aurait mérité un fichier à part (Noeud.h) et peut être aussi être une classe (pour rester cohérent).
  • Le programme est mis en défaut avec le plateau de jeu suivant. Il cherche 1 solution et 2 heures plus tard ne l'a toujours pas trouvée.
 
Sélectionnez
   xxx
   xxx
   xxx
xxxx.xxxx
xxxxxxxxx
   xxx
   xxx
   xxx

Après demande d'information auprès de Sylvain Togni, il s'avère que la fonction de règle de 3 utilisée pour savoir s'il y a une solution dit souvent la vérité mais se trompe parfois.

Sylvain Togni nous agrémente son projet avec quelques formes originales de plateaux de jeu

plateau10.txt
Sélectionnez

Solitaire.exe -f plateau10.txt
Lecture du fichier plateau10.txt...OK

  abcdefghijk
  -----------
1|    xxx
2|   xxxxx
3|  xxxxxxx
4| xxxxxxxxx
5|xxxxx.xxxxx
6| xxxxxxxxx
7|  xxxxxxx
8|   xxxxx
9|    xxx


Recherche d'une solution...OK

d5f5 d3d5 c5e5 a5c5 b4d4 d7d5 b6d6 f3d3 f1f3 c3e3 d2f2 f7d7 c7e7 f9f7 d8f8 e4e2
e1e3 e6e8 e9e7 g2e2 e2e4 e4e6 c5e5 g4g2 g1g3 i4g4 h2h4 i6i4 k5i5 f3h3 i3g3 i4i6
g4i4 j4h4 f7d7 d7d5 d4d6 h7f7 g9g7 h5h7 j6h6 f5f3 f3h3 h3h5 h5f5 e5g5 f7f5 d6f6
g6g8 i7g7 f5h5 h5h7 h7f7 f7f9 h8f8 f9f7 f7f5

Nombre de positions explorées : 13252
Mémoire utilisée : 102 Ko
Temps de recherche : 0.219 s
plateau11.txt
Sélectionnez

Solitaire.exe -f plateau11.txt
Lecture du fichier plateau11.txt...OK

  abcdefghijk
  -----------
1|   xxxxx
2|  xxxxxxx
3| xxxxxxxxx
4|xxxxx.xxxxx
5| xxxxxxxxx
6|  xxxxxxx
7|   xxxxx


Recherche d'une solution...OK

f2f4 d3f3 b3d3 c5c3 a4c4 e1e3 c2e2 g1e1 d1f1 c3c5 d4d2 d2f2 d6d4 b5d5 e5c5 c6c4
e7e5 e4e6 c4e4 g7e7 d7f7 e3e5 e6e4 g3e3 f1f3 i3g3 h1h3 i5i3 k4i4 e3e5 g5i5 e5g5
f7f5 h7h5 f4f2 f2h2 h4j4 i2i4 g3i3 j3h3 h2h4 h4f4 f4f6 f6h6 j4h4 i6g6 h4h6 j5h5
h6f6 h5f5 f6f4

Nombre de positions explorées : 5958
Mémoire utilisée : 45 Ko
Temps de recherche : 0.078 s
plateau12.txt
Sélectionnez

Solitaire.exe -f plateau12.txt
Lecture du fichier plateau12.txt...OK

  abcdefghijklm
  -------------
1|   xx
2|  xxxx
3| xxxxxxxxxxx
4|xxxxxx.xxxxxx
5| xxxxxxxxxxx
6|      xxxxx
7|       xxx


Recherche d'une solution...OK

e4g4 c4e4 a4c4 d2d4 b3d3 c5c3 c2c4 e5c5 b5d5 d4d2 d1d3 e3c3 c3c5 c5e5 e1e3 f2f4
h3f3 e3g3 j3h3 l3j3 e5e3 g3i3 f5f3 e3g3 k5k3 m4k4 i5k5 l5j5 k3k5 j3h3 g3i3 i3i5
k6k4 k4i4 i5i3 g4i4 i3i5 i5k5 j7j5 k5i5 g6g4 i5g5 i7i5 h7h5 g4g6 i5g5 g6g4

Nombre de positions explorées : 2746
Mémoire utilisée : 22 Ko
Temps de recherche : 0.031 s
plateau14.txt
Sélectionnez

Solitaire.exe -f plateau14.txt
Lecture du fichier plateau14.txt...OK

  abcdefghi
  ---------
1|xxxxxxxxx
2|xxxxxxxxx
3|xxxxxxxxx
4|xxxx.xxxx
5|xxxxxxxxx
6|xxxxxxxxx
7|xxxxxxxxx


Recherche d'une solution...OK

c4e4 c2c4 a2c2 a4a2 a1a3 a3c3 a6a4 d6d4 b5d5 c7c5 a7c7 c4c6 a4c4 b6d6 c3c5 c1c3
e1c1 b1d1 g1e1 i1g1 d1f1 f1h1 i3i1 i1g1 e2c2 c2c4 c4c6 c7c5 g3i3 g1g3 i4i2 i2g2
g2e2 d4d2 d2f2 f4d4 f2f4 e6e4 c5e5 d7d5 d5d3 d3f3 e4e6 e7e5 f3h3 g5g3 e5g5 h3f3
f3f5 g6g4 i5g5 i7i5 h7h5 f7h7 h4h6 h7h5 g4g6 i5g5 g6e6 g5e5 e6e4

Nombre de positions explorées : 14648
Mémoire utilisée : 99 Ko
Temps de recherche : 0.203 s
plateau15.txt
Sélectionnez

Solitaire.exe -f plateau15.txt
Lecture du fichier plateau15.txt...OK

  abcdefghi
  ---------
1|xxxxxx
2|xxxxxx
3|xxx
4|xxxxxxxxx
5|xxxx.xxxx
6|xxxxxxxxx
7|      xxx
8|   xxxxxx
9|   xxxxxx


Recherche d'une solution...OK

c5e5 a5c5 a3a5 c3a3 b1b3 d1b1 a1c1 a2a4 a5a3 a3c3 f1d1 d1b1 d2b2 b1b3 b3b5 c4c2
c6c4 a6c6 f2d2 d2b2 d4b4 b5b3 b2b4 f4d4 e6e4 c6e6 e4c4 b4d4 g5e5 e6e4 d4f4 i5g5
h7h5 h4h6 f4h4 i4g4 h9h7 f9h9 d9f9 f8h8 d8f8 i9g9 f9h9 i8g8 f8h8 h7h5 h9h7 f6h6
g4g6 i7i5 i5g5 h7h5 h5f5 g7g5 g5e5

Nombre de positions explorées : 97288
Mémoire utilisée : 765 Ko
Temps de recherche : 1.406 s
plateau16.txt
Sélectionnez

Solitaire.exe -f plateau16.txt
Lecture du fichier plateau16.txt...OK

  abcdefghijklmno
  ---------------
1|   xxxxxxxxx
2| xxxxxxxxxxxxx
3|xxxxxxxxxxxxxxx
4|xxxxxxxxxxxxxxx
5|xxxxxxx.xxxxxxx
6|xxxxxxxxxxxxxxx
7|xxxxxxxxxxxxxxx
8| xxxxxxxxxxxxx
9|   xxxxxxxxx


Recherche d'une solution...OK

f5h5 d5f5 d7d5 b6d6 b8b6 a6c6 a4a6 a7a5 c5e5 a5c5 b3b5 b5d5 d3b3 a3c3 d1d3 b2d2
c3c5 c6c4 c8c6 d9d7 e5g5 e3e5 c4e4 d2d4 d5f5 d7d5 d4d6 e7e5 c6e6 e1e3 e9e7 f5d5
f7f5 f9f7 e7e5 f4f6 d5f5 e4e2 g1e1 e1e3 g3g1 e3g3 h1f1 f1f3 f6f8 h9f9 f9f7 h8f8
f8f6 f6f4 f3f5 h4f4 f5f3 h2h4 f3h3 h5f5 g7g5 f5h5 j1h1 h4h2 h1h3 j9h9 h6h8 h9h7
j8h8 h8h6 h6h4 h3h5 l9j9 j6j8 j9j7 j4j6 h5j5 i7i5 i4i6 i2i4 j2j4 l1j1 l2j2 j1j3
n2l2 m4m2 o4m4 l2n2 n2n4 k3i3 i3i5 o6o4 o3o5 k5k3 i5k5 l3j3 j3j5 k6k4 i6k6 l4j4
j4j6 m4o4 o4o6 o7o5 m5k5 o5m5 l8j8 n8l8 n7n5 n5l5 m6m8 m8k8 j8l8 k6m6 l8l6 m6k6
l5j5 k7i7 k6i6 i7i5 j5h5

Nombre de positions explorées : 230005
Mémoire utilisée : 1493 Ko
Temps de recherche : 7.016 s

5.5.3. Ulmo

La solution proposée par Ulmo peut être téléchargée ici. Il s'agit d'une solution développée avec MinGW sous Windows XP. Le temps de réalisation est de 30 heures.

Il existe 3 types d'emplacements : les cases vides, les cases occupées par un pion, et les cases hors du plateau (mais qui ont des coordonnées). Il m'a semblé préférable de gérer des cases à 2 états. Un plateau de jeu contient donc 2 description :

  • l'ensemble des cases disponibles.
  • l'ensemble des cases occupées par un pion.

Les mouvements possibles sur le plateau sont pré-calculés et mémorisés. Cela présente 2 avantages :

  • On isole facilement la routine de calcul des mouvements possibles. La lisibilité est meilleure, en particulier si on veut autoriser ou pas d'autres types de mouvements (en diagonale par exemple).
  • ces mouvements sont calculés à partir de la description des cases, mais sont utilisés sur la description des pions. On utilise bien la séparation cases/pions.

J'ai choisi de ne pas gérer les symétries du plateau. La principale raison à cela est qu'un plateau "générique" n'en présentera pas (mais en même temps, tous les exemples proposés en proposent au moins une). D'autre part, j'ai estimer que cela n'améliorera pas tant que cela les performances : on y gagne au maximum un facteur 8 sur les configurations à étudier, et on doit tester tous les symétriques d'une configuration donnée pour savoir si elle a déjà été rencontrée.

2 algorithmes ont été implémentés.

Le premier est récursif : partant d'une configuration, il essaye successivement tous les mouvements possibles. Les mouvements valides lancent l'exploration de la configuration obtenue (donc à nouveau le test de tous les mouvements possibles). Si on atteint la configuration finale, on remonte en mémorisant le chemin parcouru et c'est fini. Quand aucune exploration n'a abouti, on prévient que c'est un cul de sac.

Il est extrêmement efficace de mémoriser les configurations déjà atteintes. On peut ainsi immédiatement identifier une situation qui n'aboutira pas. En contrepartie, cela consomme de la mémoire en grande quantité. Dans le cas peu probable d'une machine très rapide mais avec peu de mémoire, on pourra désactiver la mémorisation des positions parcourues. La mémorisation des configurations atteintes est implémentées très facilement avec un "set" de la bibliothèque standard (ce qui demande de définir un ordre entre les configurations). Ainsi la mémoire est gérée automatiquement. Plus précisément, il y a un "set" par nombre de pions sur le plateau, pour accélérer la recherche.

Le second algorithme explore toutes les configurations atteignables. Il n'est pas capable de reconstituer une solution (un chemin allant de la configuration initiale à celle finale), mais donne des informations sur le nombre de chemins possibles, de chemins menant à une position bloquée, et de chemins arrivant à une solution. Il part de l'ensemble des positions à N pions atteignables (ainsi que du nombre de chemins arrivant à ces solutions), et en appliquant tous les mouvements possibles à toutes ces configurations, on obtient l'ensemble des positions atteignables à N-1 pions et le nombre de chemins y conduisant.

En pratique, la consommation de mémoire fait que l'algorithme bloquera avant la fin (en fait avant la moitié, puisque le nombre de configuration est maximal lorsqu'une case sur 2 est vide, et que cela ne doit pas être très différent pour les configurations atteignables).

Critère   Note
Fonctionnement du programme   4/7
  Capacité du programme à résister à un mauvais paramètre (Test des paramètres) OK
  Capacité du programme à résister à un mauvais format de fichier de spécification du plateau (Test du programme avec plusieurs fichiers) OK
  Obtention d'une solution valide (Test du programme avec un fichier témoin) Temps d'obtention très long (20 secondes) pour un plateau relativement simple
  Affichage de la solution (Test du programme avec un fichier témoin) L'affichage fait un peu "brouillon"... une mise en forme disons... un peu plus... élaborée eut été intéressante
  Vitesse d'obtention de la solution (Test du programme avec un fichier témoin) OK, paradoxalement, l'obtention de la solution est rapide alors que le plateau de jeu est supposé plus complexe
  Comportement face à une solution impossible (Test du programme avec un fichier témoin) OK
Documentation   2/3
  Complétude par rapport à ce qui est demandé Le readme est bien fait, la doc à l'intérieur du projet est quelque peu minimaliste mais récupérée par le choix des identifiants
  Innovation dans les idées implémentées dans le code Utilisation de template, bonne étude générale des besoins
Analyse du code   5/7
  Aspect extérieur du programme bon malgré la surprise des deux fichiers d'en-tête ImplementationBit
  Découpage en module/classe OK
  Organisation des fichiers OK malgré quelques includes manquants
  Lisibilité du code OK, correctement indenté, identifiants auto-commentés, mais manque de commentaires utiles
  Simplicité du code Très correcte, sauf pour le parsing des arguments
  Bonus C vs C++ (cet extra bonus est fait pour redonner un petit avantage aux programmes écrits en C) Non
Recompilation   2/3
  Complétude de la procédure de recompilation du programme tout est prévu, mais -ansi n'est pas utilisable
  Non utilisation de librairies externes utilisation de la STL
  Recompilation du programme Pas sans intervention sur les fichiers mais ces modifications restent minimes

On notera les points suivants :

Quelques problèmes de compilation:

  • EXIT_FAILURE non déclaré (dans main.cpp dans ArgumentsLigneCommande.cpp), j'ai du rajouter <cstdlib> pour y remédier.
  • La déclaration anticipée de template<class>Mouvement dans ImplementationListe.h n'était pas suffisante pour assurer la compilation (Gcc 4.3.0)... j'ai du rajouter l'en-tête Mouvement.h (cela semble cohérent, vu qu'il y a un membre de type std::list<Mouvement<Point> > dans ImplementationListe.
  • L'option de compilation -ansi empêche la compilation (::swprintf et ::vswprintf non déclarés)... j'ai du retirer l'option du Makefile.

Pour le reste :

  • Le fichier readme est bien fait, mais la documentation du code est quelque peu minimaliste.
  • Les noms de variables sont bien auto-commentés, mais quelques commentaires supplémentaires n'auraient pas été superflus.
  • De trop nombreuses parties de code ont été commentées, et non purement et simplement supprimées, ce n'est pas très professionnel.
  • J'ai été surpris par la présence de ImplementationBit.h et de ImplementationBit.hpp. Un choix de nom différent eut été opportun.
  • Je trouve dommage d'avoir recours à un static_cast<int> pour éviter un avertissement là où l'utilisation d'un unsigned int (ou un size_t) aurait très bien fonctionné.
  • L'exécution du programme est particulièrement longue.

Le résultat présenté par le programme présente la forme suivante :

 
Sélectionnez

C:\Documents and Settings\Raymond\Bureau\Solitaire\ulmo>"solitaire.exe" -f ../simple.txt
  XXX
  XXX
XXXXXXX
XXX.XXX
XXXXXXX
  XXX
  XXX

  XXX
  XXX
XXXXXXX
X..XXXX
XXXXXXX
  XXX
  XXX

  XXX
  XXX
XXXXXXX
X.X..XX
XXXXXXX
  XXX
  XXX

  XXX
  XXX
XXXXXXX
X.X.X..
XXXXXXX
  XXX
  XXX

  XXX
  X.X
XXX.XXX
X.XXX..
XXXXXXX
  XXX
  XXX

  XXX
  X.X
X..XXXX
X.XXX..
XXXXXXX
  XXX
  XXX

  XXX
  X.X
X.X..XX
X.XXX..
XXXXXXX
  XXX
  XXX

  XXX
  X.X
X.X..XX
XX..X..
XXXXXXX
  XXX
  XXX

  XX.
  X..
X.X.XXX
XX..X..
XXXXXXX
  XXX
  XXX

  ..X
  X..
X.X.XXX
XX..X..
XXXXXXX
  XXX
  XXX

  ..X
  ...
X...XXX
XXX.X..
XXXXXXX
  XXX
  XXX

  ..X
  ..X
X....XX
XXX....
XXXXXXX
  XXX
  XXX

  ...
  ...
X...XXX
XXX....
XXXXXXX
  XXX
  XXX

  ...
  ...
X...XXX
XXX.X..
XXXX.XX
  XX.
  XXX

  ...
  ...
X...XXX
XXX.X..
XX..XXX
  XX.
  XXX

  ...
  ...
X...XXX
XXX.X..
..X.XXX
  XX.
  XXX

  ...
  ..X
X....XX
XXX....
..X.XXX
  XX.
  XXX

  ...
  ..X
X...X..
XXX....
..X.XXX
  XX.
  XXX

  ...
  ...
X......
XXX.X..
..X.XXX
  XX.
  XXX

  ...
  ...
.......
.XX.X..
X.X.XXX
  XX.
  XXX

  ...
  ...
.......
.XX....
X.X..XX
  XXX
  XXX

  ...
  ...
.......
.XX....
X.X.X..
  XXX
  XXX

  ...
  ...
.......
.XX....
X.XXX..
  X.X
  X.X

  ...
  ...
.......
.XX....
X.X..X.
  X.X
  X.X

  ...
  ...
.......
.XX....
X.X.XX.
  X..
  X..

  ...
  ...
.......
.XX....
X.XX...
  X..
  X..

  ...
  ...
.......
.XX....
XX.....
  X..
  X..

  ...
  ...
.......
.XX....
XXX....
  ...
  ...

  ...
  ...
.......
.X.....
XX.....
  X..
  ...

  ...
  ...
.......
.X.....
..X....
  X..
  ...

  ...
  ...
.......
.XX....
.......
  ...
  ...

  ...
  ...
.......
...X...
.......
  ...
  ...

Dictionnaire[32] : 1
Dictionnaire[31] : 1
Dictionnaire[30] : 1
Dictionnaire[29] : 1
Dictionnaire[28] : 1
Dictionnaire[27] : 1
Dictionnaire[26] : 1
Dictionnaire[25] : 2
Dictionnaire[24] : 5
Dictionnaire[23] : 18
Dictionnaire[22] : 71
Dictionnaire[21] : 282
Dictionnaire[20] : 1016
Dictionnaire[19] : 3244
Dictionnaire[18] : 9205
Dictionnaire[17] : 23198
Dictionnaire[16] : 51137
Dictionnaire[15] : 97946
Dictionnaire[14] : 161661
Dictionnaire[13] : 226301
Dictionnaire[12] : 266134
Dictionnaire[11] : 261195
Dictionnaire[10] : 211882
Dictionnaire[9] : 141398
Dictionnaire[8] : 78218
Dictionnaire[7] : 35569
Dictionnaire[6] : 12998
Dictionnaire[5] : 3849
Dictionnaire[4] : 910
Dictionnaire[3] : 137
Dictionnaire[2] : 23
Dictionnaire[1] : 0

6. Conclusion

Encore une fois, nous tenons à remercier tous les participants à ce défi et à féliciter notre grand gagnant Sylvain Togni qui se verra remettre rapidement son prix sous la forme d'un bon d'achat Amazon de 40€ offerts par la rédaction de developpez.com.

Nous espérons vous retrouver nombreux pour le prochain défi qui ne devrait plus tarder maintenant.