Version imprimable
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:
Envoyé par ram-0000
Lister les 40 billiards de solutions prendrait en effet un certain temps.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.
J'avoue que je n'avais jamais fait le compte.Citation:
Envoyé par Jean-Marc.Bourguet
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
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:
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).
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 Jean-Marc.Bourguet
Si je ne me suis pas planté, oui, ce sont les seules configurations atteignables avec une seule pierre restante.Citation:
Envoyé par ram-0000
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
auquel on arrive après 6 mouvements (il y a 32 chemins avec uniquement 6 mouvements).Code:
2
3
4
5
6
7
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 :?.Citation:
Envoyé par Jean-Marc.Bourguet
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"
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)Code:
2
3
4
5
6
7
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:
Mais il me faut beaucoup plus de temps que 10 s pour arriver a ce genre de resultat. Et pas mal de memoire.Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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.
Aucune.Citation:
Envoyé par Jean-Marc.Bourguet
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.
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.Citation:
Envoyé par Sylvain Togni
Code:
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
Pas exactement. Il y a 4 configurations avec 1 bille atteignables :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.Code:
2
3
4
5
6
7
8
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 Sylvain Togni
Le européen moins de 1 Mo et 1 ms. Mais c'est pas aussi simple pour tous, par exemple celui làCitation:
Envoyé par Jean-Marc.Bourguet
prend environ 100 Mo et 7 secondes pour trouver une solution.Code:
2
3
4
5
6
7
8
9
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)
les solutions que je trouve sont toutes très différentes à chaque foisCode:
2
3
4
5
6
7