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.
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 plateaux▲
Plusieurs types de plateaux 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 plateaux en forme de triangle comptant 15 trous.
Les différents types de plateaux :
- Européen, XVIIe siècle, 37 trous ;
- J. C. Wiegleb, 1779, Allemagne, 45 trous ;
- Asymétrique 3-3-2-2, XXe siècle ;
- Anglais, 33 trous ;
- Diamant, 41 trous ;
- 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. À l'issue, le programme doit s'arrêter ;
- « -v ». Cette option affiche le copyright du programme. À 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.
xxx
xxx
xxxxxxx
xxx.xxx
xxxxxxx
xxx
xxx3-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 toutes 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 :
- ram-0000 (organisateur de ce défi) ;
- gangsoleil ;
- koala01.
5. Analyse des résultats▲
5-1. Participants▲
Les personnes ayant participé jusqu'au bout à ce défi sont par ordre alphabétique :
- D[r]eadLock ;
- Sylvain Togni ;
- Ulmo.
Nous les remercions pour de leur participation à ce défi ainsi que tous les autres participants qui ne sont pas allé 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 :
xxx
xxx
xxxkfdkhdfsk
X.x
xxx
xxx
xxxxxx
x.x
xxx xxx
xxx
xxxxxxx
xxx.xxx
xxxxxxx
xxx
xxxxxxxxx
xxxxxx
xx.xxx
xxxxxx
xxxxxx
xxxxxx5-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 brouillons, un temps d'exécution assez long.
- D[r]eadLock : Un travail en C (saluons l'effort), un algorithme simple (par brute 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 trouver 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 :
$> ./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 -> Nord5-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.
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 tout noeud dans b1 faire
pour tout coup valide faire
b2 <- b2 + coup
fpour
fpour
échange(b1, b2)
fpour
si b1 contient p2
retourne chemin(p1, p2);
fsi
finCet 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.
fonction rechercheChemin (p1:plateau, p2:plateau) : chemin
début
taille : entier
taille <- 1
tant que !beamSearch(p1, p2, taille)
taille <- taille*2
fin
finL'heuristique utilisée part du principe qu'à un niveau donné, plus les pions sur un plateau sont resserrés, plus le plateau a 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 a 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 garanti, 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 souhaiterait 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 pu ê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 Nœud est déclarée et définie dans le fichier Solveur.cpp. Elle aurait mérité un fichier à part (Nœud.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.
xxx
xxx
xxx
xxxx.xxxx
xxxxxxxxx
xxx
xxx
xxxAprè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
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 sSolitaire.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 sSolitaire.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 sSolitaire.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 sSolitaire.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 sSolitaire.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 s5-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 descriptions :
- 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 estimé 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ée 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 configurations 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 autocommenté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 dû 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 dû 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 dû 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 autocommenté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 :
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] : 06. 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 € offert par la rédaction de developpez.com.
Nous espérons vous retrouver nombreux pour le prochain défi qui ne devrait plus tarder maintenant.