2ème défi C & C++ : Recherche de solution au solitaire

Bonjour à toutes et à tous,

Vous étiez nombreux à attendre l'annonce d'un nouveau défi, le voilà.

Le sujet de ce deuxième défi concerne la recherche de solution au jeu du solitaire. Ce défi commence maintenant (lundi 2 février 2009) et les copies sont ramassées le dimanche 8 mars à minuit.

Pour plus d'information, les différents points d'entrée sont :

• Serveur des défis C & C++
• Les règles générales des défis C & C++
• Les règles particulières de ce défi

Parmi les changements dans ce 2ème défi, on notera :

• Les défis sont aussi ouverts au langage C++ (pas de sectarisme primaire :P)
• Les défis sont ouverts aux modérateurs, rédacteurs et autres responsables du forum. Toutefois, leur classement sera à part et ne donnera pas lieu à un prix (c'est pour le fun uniquement)
• Les défis sont ouverts aux équipes.

Si vous prévoyez de participer au défi, envoyer un petit MP aux organisateurs. Il ne s'agit nullement d'un engagement de votre part mais cela nous permet de composer un jury avec suffisamment de membres en fonction du nombre de challenger prévisibles.

Si vous avez la moindre question concernant ce défi ou si un point du règlement vous parait obscur, il suffit de poster dans la suite de ce message (les questions et les réponses sont publiques).

Bon courage à tous

Bonjour,
Le descriptif du défi mentionne un solitaire triangulaire. Celui ci n'est pas représentable avec la convention donnée (avec "." "x" et " ").
Est-ce intentionnel ?

Citation:

---

Envoyé par Ulmo

Bonjour,
Le descriptif du défi mentionne un solitaire triangulaire. Celui ci n'est pas représentable avec la convention donnée (avec "." "x" et " ").
Est-ce intentionnel ?

---

Le descriptif du défi reprend la page de Wikipédia.

Effectivement, le modèle en triangle n'est pas adaptable au défi courant (de même que d'autres modéles plus exotiques avec des cases hexagonales).

Les seuls modèles utilisables par ce défi sont les modèles de plateau avec des cases carrées.

Citation:

---

Envoyé par Ulmo

Bonjour,
Le descriptif du défi mentionne un solitaire triangulaire. Celui ci n'est pas représentable avec la convention donnée (avec "." "x" et " ").
Est-ce intentionnel ?

---

J'allais justement poser la même question !

Citation:

---

Envoyé par ram-0000

Le descriptif du défi reprend la page de Wikipédia.

Effectivement, le modèle en triangle n'est pas adaptable au défi courant (de même que d'autres modéles plus exotiques avec des cases hexagonales).

Les seuls modèles utilisables par ce défi sont les modèles de plateau avec des cases carrées.

---

Ca va faciliter un peu le problème ça :mouarf:

Est-ce qu'il faut toutes les solutions (l'intitule le laisse penser), ou une solution (la formulation le laisse penser)?

Citation:

---

Envoyé par Jean-Marc.Bourguet

Est-ce qu'il faut toutes les solutions (l'intitule le laisse penser), ou une solution (la formulation le laisse penser)?

---

Pour ce défi, il suffit de trouver une seule solution (certaines configurations de plateau de jeu ont plusieurs milliers de solutions).

Titre du post rectifié.

Règles du défi clarifiées, paragraphe 3.1

Citation:

---

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.

---

Peut-on utiliser Boost.Graph? (dans le sujet, c'est spécifié d'utiliser avec parcimonie les libs externes)

Citation:

---

Envoyé par Trunks

Peut-on utiliser Boost.Graph? (dans le sujet, c'est spécifié d'utiliser avec parcimonie les libs externes)

---

N'oubliez pas que votre programme sera testé et recompilé sur une machine qui ne dispose peut être pas de l'environnement de développement dont vous avez l'habitude. L'usage de librairies externes peut avoir un impact non négligeable sur l'aspect déploiement de la solution.

De plus, le but d'un défi, à la différence de la vraie vie, n'est pas de savoir si vous savez utiliser LA librairie qui implémente l'algorithme de la mort qui tue mais plutôt si vous savez implémenter vous même cet algorithme.

Je dirais donc, dans la mesure du possible, restez classique, ce défi peut être résolu uniquement avec les librairies et les concepts de base.

Et pour compiler, il faut avoir un make ou un projet Visual ? J'imagine qu'utiliser SCons n'est pas recommandé :(

Citation:

---

Envoyé par Matthieu Brucher

Et pour compiler, il faut avoir un make ou un projet Visual ? J'imagine qu'utiliser SCons n'est pas recommandé :(

---

Je viens de lire la doc de SCons que je ne connaissais pas et ce que je lis :

Citation:

---

Envoyé par La documentation SCons

Because SCons is written in Python, you must obviously have Python installed on your system to use SCons. Before you try to install Python, you should check to see if Python is already available on your system by typing python -V (capital 'V') or python --version at your system's command-line prompt.

---

ne m'incite pas à le choisir dans le cadre de ce défi. Attention, je ne dis pas que SCons est mauvais mais je pense que vu la taille du projet final, un portage avec un Makefile ou sous la forme d'un projet Visual Studio me semble plus simple.

Je m'autorise un post en passant, qui n'est pas une question pour une fois:
Le sujet n'a pas l'air évident, bon courage à tous les participants ;)

On peut utiliser tr1/tr2 (pour shared_ptr)?

Citation:

---

Envoyé par Trunks

On peut utiliser tr1/tr2 (pour shared_ptr)?

---

J'avoue ne pas bien comprendre la question. Un petit peu plus d'explications s'il te plait ?

Il s'agit de Technical Reports qui proposent de nouvelles choses qui sont souvent implémentées dans les dernières versions des compilateurs (GCC 4.3, ICC 11, ...).

Citation:

---

Envoyé par Matthieu Brucher

Il s'agit de Technical Reports qui proposent de nouvelles choses qui sont souvent implémentées dans les dernières versions des compilateurs (GCC 4.3, ICC 11, ...).

---

Dans ce cas, j'aurai la même réponse que pour l'usage de la librairie Boost.Graph :

Citation:

---

Envoyé par ram-0000

N'oubliez pas que votre programme sera testé et recompilé sur une machine qui ne dispose peut être pas de l'environnement de développement dont vous avez l'habitude. L'usage de librairies externes peut avoir un impact non négligeable sur l'aspect déploiement de la solution.

De plus, le but d'un défi, à la différence de la vraie vie, n'est pas de savoir si vous savez utiliser LA librairie qui implémente l'algorithme de la mort qui tue mais plutôt si vous savez implémenter vous même cet algorithme.

Je dirais donc, dans la mesure du possible, restez classique, ce défi peut être résolu uniquement avec les librairies et les concepts de base.

---

Il n'est pas possible d'être exhaustif et de dire vous avez le droit d'utiliser ca ca et ca mais pas ca ca et ca. Il y a bien trop de bibliothèques et je ne veux pas brider les gens dans leurs idées.

Maintenant, il faut aussi que les personnes qui participent à ce défi se posent les questions :

• Est ce que ce "machin" est vraiment utile pour ce que je veux faire
• Est ce que c'est standard ou couramment admis/utilisé
• Est ce que le jury risque de l'avoir par défaut
• Est ce que si j'en ai vraiment besoin et que le jury risque de ne pas l'avoir, je peux le réimplémenter facilement
• ...

Je pense que c'est par rapport à la gestion mémoire (pointeurs intelligents). Ca ne pèse pas lourd (qqs en-têtes). Au pire, on les ajoute (c'est ce que je comptais faire de mon côté).

Si c'est C ou C++ windows et linux,
peut être proposer un compilateur commun. Par exemple :
- mingw sous linux
- gcc 4.x sous linux

non?
cela donnerais une base de ce que l'on as droit ou non de base?

Citation:

---

Envoyé par Mongaulois

Si c'est C ou C++ windows et linux,
peut être proposer un compilateur commun. Par exemple :
- mingw sous linux
- gcc 4.x sous linux

non?
cela donnerais une base de ce que l'on as droit ou non de base?

---

Je garde cette excellente idée pour le prochain défi (car il y en aura un). Pour le défi courant, c'est trop tard.

ram-0000, si je ne me suis pas planté, tu as légèrement sous-estimé le nombre de solutions...

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

1.02154e+16 ways to reach   .x. ... ....... ....... ....... ... ...   1.02154e+16 ways to reach   ... ... ....... x...... ....... ... ...   4.08616e+16 ways to reach   ... ... ....... ...x... ....... ... ...   1.02154e+16 ways to reach   ... ... ....... ......x ....... ... ...   1.02154e+16 ways to reach   ... ... ....... ....... ....... ... .x.

---

Et j'ai pas assez de mémoire pour les autres plateaux avec mon algo actuel. (Il faudrait passer en 64 bits pour l'utiliser d'ailleurs).

Citation:

---

Envoyé par Jean-Marc.Bourguet

ram-0000, si je ne me suis pas planté, tu as légèrement sous-estimé le nombre de solutions...

---

Juste une remarque, j'espère que tu as bien compris et correctement interprété cette règle particulière du défi

Citation:

---

Envoyé par les règles de ce défi

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

---

dans le paragraphe 3.3. Format du fichier de description du plateau de jeu

De toute façon, le but de ce défi n'est pas de trouver toutes les solutions (et là, je suis d'accord, il peut y en avoir plusieurs suivant la configuration initiale du plateau) mais une solution.

Citation:

---

Envoyé par ram-0000

Juste une remarque, j'espère que tu as bien compris et correctement interprété cette règle particulière du défi

dans le paragraphe 3.3. Format du fichier de description du plateau de jeu

---

Oui, je l'ai vu. Tu avais écrit qu'il pouvait avoir plusieurs milliers de solutions, le contraste avec les 40 billiards de solutions auxquelles j'arrive m'amusait.

Citation:

---

De toute façon, le but de ce défi n'est pas de trouver toutes les solutions (et là, je suis d'accord, il peut y en avoir plusieurs suivant la configuration initiale du plateau) mais une solution.

---

Lister les 40 billiards de solutions prendrait en effet un certain temps.

Citation:

---

Envoyé par Jean-Marc.Bourguet

Oui, je l'ai vu. Tu avais écrit qu'il pouvait avoir plusieurs milliers de solutions, le contraste avec les 40 billiards de solutions auxquelles j'arrive m'amusait.

---

J'avoue que je n'avais jamais fait le compte.

En fait, si je regarde les 5 configurations que tu présentes et leurs nombres de solutions, je constate que les configurations 1, 2, 4 et 5 sont équivalentes. C'est juste une rotation qui est faite de la configuration. Il est donc normal que leurs nombres de solution semblent égaux (je dit semble car l'affichage n'est pas assez précis).

Citation:

---

Envoyé par ram-0000

J'avoue que je n'avais jamais fait le compte.

---

Citation:

---

En fait, si je regarde les 5 configurations que tu présentes et leurs nombres de solutions, je constate que les configurations 1, 2, 4 et 5 sont équivalentes. C'est juste une rotation qui est faite de la configuration. Il est donc normal que leurs nombres de solution semblent égaux (je dit semble car l'affichage n'est pas assez précis).

---

Ils sont bien égaux. Et la 3 a exactement 4 fois plus de solutions (seul le dernier mouvement est différent entre la 3 et les autres). Ce qui est amusant c'est qu'il n'y a pas d'autres positions atteignables -- si je ne me suis pas planté.

Citation:

---

Envoyé par Jean-Marc.Bourguet

Ils sont bien égaux. Et la 3 a exactement 4 fois plus de solutions (seul le dernier mouvement est différent entre la 3 et les autres). Ce qui est amusant c'est qu'il n'y a pas d'autres positions atteignables -- si je ne me suis pas planté.

---

Tu veux dire que sur un plateau de cette forme, ce sont les seules configurations qui amènent au moins une solution ?

Citation:

---

Envoyé par ram-0000

Tu veux dire que sur un plateau de cette forme, ce sont les seules configurations qui amènent au moins une solution ?

---

Si je ne me suis pas planté, oui, ce sont les seules configurations atteignables avec une seule pierre restante.

En cadeau, les nombres précis sont 10215411760019992 et 40861647040079968. Il y a 31*2^64 + 5185367236233589640 chemins qui mènent à des culs de sac. Le premier de ceux-ci est

Code:

---

1 2 3 4 5 6 7

xxx x.x xxxxxxx x.x.x.. xxxxxxx x.x x.x

---

auquel on arrive après 6 mouvements (il y a 32 chemins avec uniquement 6 mouvements).

Citation:

---

Envoyé par Jean-Marc.Bourguet

En cadeau, les nombres précis sont 10215411760019992 et 40861647040079968.

---

Quand j'étais jeune, je jouais souvent au solitaire sur un vrai plateau avec des vraies billes et je n'ai jamais trouvé de solution manuelle. Avec autant de solutions possibles, c'est vraiment que j'ai pas eu de chance :?.

J'aime bien ce genre de problèmes NP-complets :D
Si j'avais pas autant de boulot, je crois bien que je me lancerais dedans ^^
Bon courage à tous les participants en tout cas :)

salut

est-ce que pour le solitaire "européen"

Code:

---

1 2 3 4 5 6 7

xxx xxxxx xxx xxx xxxxxxx xxxxxxx xxxxx xxx

---

il est possible de faire un algo qui trouve rapidement ( < 10s) une solution, et trouvée aléatoirement bien sur (pas de raison de trouver une solution qui ressemble à la précédente d'une fois sur l'autre)

Je suppose qu'il faut créer un algo qui soit capable d'évaluer une position (dire si elle est gagnante ou perdante) et à partir de là, tente d'aller sur une des positions possibles et gagnantes à partir de la position courante en choisissant au hasard quand il y a plusieur choix possibles.

J'ai toutefois peur que, vu ce qu'à montré Jean-Marc.Bourguet précédemment, l'arbre des choix possibles soit énorme et que cela nécessite beaucoup de mémoire (vive ou disque) pour le construire.

Je retourne la question dans un autre domaine : est il possible de trouver un algorithme qui joue aux échecs en choisissant ses coups de manière aléatoire parmi les coups qui lui permettent de gagner et qui en plus sache gagner.

Intuitivement, je ne pense pas. Je pense qu'il y a une (ou plusieurs) stratégies globallement gagnante et si on veut coller à cette stratégie, on ne peut plus jouer au hasard. Toutefois, ce raisonement est purement intuitif et parfois l'intuition joue des tours.

Apres simplifications dues aux symmetries, il y a 211.831.865 configurations atteignables apres 19 coups avec ce plateau. Il y en a 3 apres 35:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

... ..... ...x... ....... ....... ..... ...     ... ..x.. ....... ....... ....... ..... ...     x.. ..... ....... ....... ....... ..... ...

---

Mais il me faut beaucoup plus de temps que 10 s pour arriver a ce genre de resultat. Et pas mal de memoire.

Le plateau anglais a 3.626.632 configurations atteignables après 17 coups. Si je ne me trompe pas, de celles-ci 204.992 permettent d'atteindre la position finale désirée.

Comme déjà écrit, le plateau européen a 211.831.865 configurations atteignables après 19 coups. Je ne connais pas combien permettent d'atteindre la position finale.

Ca y ai j'ai fait quelque chose, ca teste en boucle les solutions, vu le nombre de possibilitées il ne donne rien (sauf peut etre si je le laisse toute la nuit, ou tout le week end :aie:). C'est la que je vois que je suis bien plus fort (ou moins mauvais ) en prog qu'en math...
Je donnerai quand même mes sources au concours, j'ai hâte de voir le mois prochain les divers solutions.

Citation:

---

Envoyé par Jean-Marc.Bourguet

Comme déjà écrit, le plateau européen a 211.831.865 configurations atteignables après 19 coups. Je ne connais pas combien permettent d'atteindre la position finale.

---

Aucune.

Plus que 2 semaines avant la clôture de ce défi. C'est toujours pour le dimanche 8 mars à minuit, pas de changement à ce sujet.

Un petit conseil, n'oubliez pas de relire les règles afin de voir si vous n'oubliez rien par rapport à ce qui est attendu.

Citation:

---

Envoyé par Sylvain Togni

Aucune.

---

J'ai l'impression que tu n'as remarqué que ce n'est pas la bille centrale qui est à enveler au départ. Il y a 3 configurations (aux symmétries près) finales possibles.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

1/1 2/3 3/10 4/47 5/251 6/1248 7/5915 8/26178 9/106417 10/394935 11/1320808 12/3936239 13/10367468 14/23961963 15/48363474 16/85085072 17/130489036 18/174784172 19/205162486 20/211831865 21/192959346 22/155376882 23/110711524 24/69800398 25/38881550 26/19086780 27/8226236 28/3091084 29/1004958 30/280194 31/65918 32/12810 33/2053 34/256 35/23 36/3   ... ..... ...x... ....... ....... ..... ...     ... ..x.. ....... ....... ....... ..... ...     x.. ..... ....... ....... ....... ..... ...

---

Pas exactement. Il y a 4 configurations avec 1 bille atteignables :

Code:

---

1 2 3 4 5 6 7 8

XXX ... ... ... ... XXXXX ..X.. ..... ..... ..... XXX.XXX ....... ....... ....... ....... XXXXXXX => ....... ....... ....... ....... XXXXXXX ....... X...... ...X... ......X XXXXX ..... ..... ..... ..... XXX ... ... ... ...

---

Mais aucune n'étant la symétrique de la configuration de départ, le plateau n'a pas de solution au sens du défi.

Citation:

---

Envoyé par Sylvain Togni

Pas exactement. Il y a 4 configurations avec 1 bille atteignables :

Code:

---

1 2 3 4 5 6 7 8

XXX ... ... ... ... XXXXX ..X.. ..... ..... ..... XXX.XXX ....... ....... ....... ....... XXXXXXX => ....... ....... ....... ....... XXXXXXX ....... X...... ...X... ......X XXXXX ..... ..... ..... ..... XXX ... ... ... ...

---

Mais aucune n'étant la symétrique de la configuration de départ, le plateau n'a pas de solution au sens du défi.

---

Je crois que j'ai compris mon bug -- dans la gestion de la symétrie, j'utilise la symétrie du tableau plutôt que de la configuration initiale. Un petite question: tu as besoin de combien de mémoire et de temps pour arriver à ce résultat?

Citation:

---

Envoyé par Jean-Marc.Bourguet

Un petite question: tu as besoin de combien de mémoire et de temps pour arriver à ce résultat?

---

Le européen moins de 1 Mo et 1 ms. Mais c'est pas aussi simple pour tous, par exemple celui là

Code:

---

1 2 3 4 5 6 7 8 9

xxx xxx xxx xxxxxxxxx xxxx.xxxx xxxxxxxxx xxx xxx xxx

---

prend environ 100 Mo et 7 secondes pour trouver une solution.

salut,

il faut toujours préciser quand vous spécifiez le temps avant de trouver une première solution : trouver une solution, mais toujours la même (en suivant toujours le même cheminement dans votre arbre/graphe ou autre, et ce qui n'a donc pas beaucoup d'intéret), ou trouver en moyenne une solution en tant de temps, et en précisant donc aussi le pire cas

merci !

moi sur le plateau anglais le pire cas est de 1,5 minute et 600mo, et en moyenne 20 ou 30s, 250 ou 300mo

sur le solitaire anglais

j'ai un algo qui met environ 10-15 sec pour trouver une solution (dans le pire cas il peut mettre beaucoup plus je pense)

Code:

---

1 2 3 4 5 6 7

xxx xxx xxxxxxx xxx.xxx xxxxxxx xxx xxx

---

les solutions que je trouve sont toutes très différentes à chaque fois