Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Solitaire sur tablier.

Posté par
Benwat
09-09-12 à 20:24

Bonjour à tous,

Je cherche à obtenir une méthode de résolution générale pour les jeux de solitaire sur tablier. Il s'agit d'un type de casse-tête relativement connue dont vous avez ici le plateau :

Solitaire sur tablier.

Ici, il s'agit d'un tablier anglais, mais des variantes existent.

Quand je dis "une méthode de résolution générale", je veut dire que le tablier possède une forme quelconque, qu'il contient initialement AU MOINS UNE case vide, et que les alignements de trous sont toujours parallèles ou perpendiculaires deux à deux (il existe en effet des tablier à case hexagonal où on joue alors dans 3 directions, et non 2).


Voilà !

J'attends vos réponses avec impatience, ne serait-ce que des pistes ou des idées.

Merci d'avance pour votre aide.  
* Océane > image placée sur le serveur de l' *

Posté par
DARK_DUCK
re : Solitaire sur tablier. 06-01-13 à 13:34

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

Posté par
Linaelle
re : Solitaire sur tablier. 06-01-13 à 17:28

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

Posté par
DARK_DUCK
re : Solitaire sur tablier. 06-01-13 à 17:43

Citation :
je vois d'autres facons d'attaquer le problème


Peux-tu m'éclairer je suis curieux de connaître d'autres approches.

Posté par
Linaelle
re : Solitaire sur tablier. 06-01-13 à 17:45

Alors autant pour moi il manque un "pas".

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

Posté par
DARK_DUCK
re : Solitaire sur tablier. 06-01-13 à 18:20

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 :/

Posté par
Linaelle
re : Solitaire sur tablier. 06-01-13 à 18:29

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

Posté par
DARK_DUCK
re : Solitaire sur tablier. 06-01-13 à 18:35

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

Posté par
Linaelle
re : Solitaire sur tablier. 06-01-13 à 18:38

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

Posté par
DARK_DUCK
re : Solitaire sur tablier. 06-01-13 à 19:19

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

Posté par
Benwat
re : Solitaire sur tablier. 09-01-13 à 19:23

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

Posté par
olafleury
re : Solitaire sur tablier. 24-02-18 à 13:07

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

Posté par
olafleury
re : Solitaire sur tablier. 24-02-18 à 13:31

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

Posté par
olafleury
re : Solitaire sur tablier. 24-02-18 à 13:36

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

Posté par
lafol Moderateur
re : Solitaire sur tablier. 24-02-18 à 21:00

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

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !