Bonjour,

j'ai une solution mais je ne sais pas si c'est la plus optimisée :
Tout d'abord il faut créer ta table de jeu. Personnellement  voila ce que je propose.

Chaque case est représentée par un objet qui contient deux propriétés :
- boolean état (présence de boule ou non)
- un tableau de déplacements possible (objet définit plus tard)

Les déplacements possibles ont deux propriétés:
- lien vers la case "mangée"
- lien vers la case de destination

On considère ensuite un objet de type plateau qui contient la totalité des cases.

Ensuite tu définit chaque case comme vide ou pleine en fonction de la condition de départ que tu désire.

Ensuite on va créer un arbre de possibilités
à la racine on a l'arbre de départ.

On recherche tous les déplacements possible (si tu as un problème la dessus je peux expliciter l'algorithme)
pour chaque déplacement possible on créé une nouvelle branche dans l'arbre qui contient une version du plateau où on a joué le coup.
Comme la plupart des plateaux de jeux sont symétriques on peut gagner énormément de temps en ignorant tous les coups symétriques (dans la photo de ton exemple en réalité il n'y a qu'un seul coup à jouer au départ car ils sont tous équivalents).

on génère l'arbre en refaisant l'algorithme pour chaque noeud de l'arbre. Si on arrive à un noeud ou on ne peut plus jouer alors on coupe le branche. Si il n'y a plus de cases pleine alors on a trouvé une solution. il n'y a plus qu'a remonter l'arbre jusqu'à la racine pour trouver les différentes étapes de jeu.

Cet algorithme n'est sans doute pas super rapide mais il a le mérite de fonctionner

"Cet algorithme n'est sans doute pas super rapide"

C'est le moins qu'on puisse dire ! Initialement si il n'y a qu'un trou, ca fait 32 boules derrière.

A la louche, dans le cas défavorable ca fait 2^32 chemins potentiels (plus de 4 milliards).
Même avec un calcul de 1 ms par parcours, ca fait quand même 4 millions de secondes.

Enfin je peux largement me tromper, et de toute facon je vois d'autres facons d'attaquer le problème.

Alors autant pour moi il manque un "pas".

En te relisant je me trouvais impétueux ! Non justement j'ai pas vraiment mieux à proposer.

J'ai un peu réfléchis au problème.

Je me trompe peut être mais il me semble que l'estimation soit bien pire que ce que tu propose.
le nombre de chemins que tu propose correspond à un arbre binaire de rang 32. Or en moyenne il y a plus de 2 manière différentes de jouer(ce nombre augmente d'autant plus qu'on avance dans la partie).On a donc un arbre de 32 niveau mais dont le nombre de ramifications indéterminé. Cet algorithme n'est donc vraiment pas implémentable :/

Oui je me suis dit ca aussi.

En fait tu as 1 ou 2 possibilités au début.
Ensuite, avec deux trous, tu as donc entre 2 et 4 possibilités.
3 trous, 3 et 6 possibilités.

Donc ca resemble plutot à du (2*32)^32

Je vois 4 façons de jouer le premier coup. Mais on peut les ramener à une en considérant qu'elles sont équivalents à cause de la symétrie du plateau.(je pense que c'est un énorme facteur d'optimisation).

Bah bien sur, c'est pourquoi j'ai dis que pour 1 trou, on a 2 possibilités, les 2 autres sont symétriques.

les 4 premiers coups sont symétriques. il y a 4 axes de symétries sur le plateau :
- y = 0
- x = 0
- y = 1/2x
- y = -1/2x

Holala ! Ca faisait longtemps ça, je n'y pensais plus.


Oui j'ai pensé à tracer un arbre des possibles, mais comme vous l'avez dit, ça peut être très long.
Quand à considérer des coups symétriques, il faut aussi que le tablier soit symétrique. Alors, pour les premiers coups, ça va, mais très rapidement on se retrouve avec beaucoup de coup possible.

Il y aurait un autre facteur de simplification possible : deux coups sont parfois complètement indépendants. A partir d'un tablier donné, faire l'un puis l'autre, ou l'autre puis l'un donne le même résultat. Ca permet juste d'éviter d'avoir des nœuds identiques sur des branches différentes.

Pour user de cette simplification, il faudrait d'avance déterminer les configurations possibles (nœud), virer les cas semblables, et tracer des branches entre deux situations quand on peut passer de l'une à l'autre par un coup.
Ce serait déjà sans doute moins pire, mais bon...

Je sais pas si je suis très clair, et là je vais devenir plus obscur encore, mais... dans ma tête, j'ai l'impression qu'on peut ranger les nœuds-situations par "nombre de bille". Avec cette visualisation, les seuls branches-coups possibles serait tracés entre deux nœuds-situations avec une différence de bille égale à 1.
En plus, ça permet de repéré qu'en fait, on a 1 seul nœuds-situations à 30 billes au lieu de 496 potentiels.


Il y a une idée que j'ai pas encore explicité à fond en fait, je me demande si elle est pas plus intéressante à modéliser.

On considère le tablier comme un tableau (jusque là rien ne change) mais on mets pas de booléen dans les cases, mais un nombres de billes.
L'astuce se serait de s'autoriser à mettre autre chose que 0 ou 1. Mais genre 2, ou 3, voir même pourquoi pas, -1 ou -2.
Avec cette conception, les coups deviendrait plutôt des genres de "domino" |-1|-1|+1| qu'on essayerai de poser sur le jeu.
Cette idée m'est venu en considérant les fameux coups "permutables" dont j'ai parlé plus haut. Ici, puisqu'on peut mettre plusieurs billes ou même un nombre négatifs de billes, sans que ça pose de souci, tous les coups sont permutables.

Du coup, il suffirait de choisir 30 emplacements pour mettre les dominos, sachant qu'il y a 108 emplacements possibles, on a (108^30)/(30!) combinaisons d'emplacement à tester soit 3,7.10^28... ce qui fait un peu beaucoup aussi.

Mais c'est pareil, il y a sans doute des simplifications possibles, même si elles me paraissent moins évidentes, hormis les combinaisons symétriques qui divise pas 8 le nombre ci-dessus.

Voilà.  

un algorithme pour trouver une solution systematique est assez simple le but est de trouver le plus rapide notamment par fonctions recurentes ensuite le temps d'excecution depends du degres de recurrence,suis nouveau ici mais vais me pencher sur ce probleme interressant car mon pere y joue souvent et reussi de temps en temps a le finir mais je ne pense pas qu'il se rappelle de la "technique" qu'il a utilisé.porutant la solution est beaucoup simple qu'il n'y parait par rapport a d'autres jeu comme les echecs  ou encore plus complexe avec le jeu de go,a bientot

il faut a mon premier avis considerer que chaque action poduit evidemment un nombre de reactions possibles croissant au cours de la progression du jeu le principe est justement eliminer celles qui seront "nefastes" a la solution finale,coment reduire ce nombre de reaction n'aboutissant pas a notre objectif final,une idée me viens,pourquoi ne pas prendre le probleme a "l'envers",pour l'instant suis trop fatigué pour poursuivre ce raisonnement,n'ai pas dormis de la nuit (joué au echecs sur sparkchess) desolé mais mes yeux se ferment tout seuls a bientot

la symetrie  est forcement a prendre en compte ,pouvons nous voir ce jeu a plus que ses deux dimensions et augmenter d'une dimension a chaque coup

sympa de répondre à un sujet vieux de cinq ans, quand tous les intervenants sauf un se sont désinscrits du site ....