Ce jeu est sorti le 5 janv. 2010, et a été ajouté en base le 5 janv. 2010 par 20.100

édition 2009

Standalone
Par : scand1sk | samedi 19 décembre 2009 à 15:18
Default
scand1sk
scand1sk
Quelqu'un sur BGG a posé cette question… et le problème est loin d'être trivial. Pour les deux du fond que ça intéresse, je l'ai résolu de manière informatique. Je ne suis même pas sûr qu'il soit possible de le résoudre de manière purement analytique. Si quelqu'un se sent de le faire…

Je rappelle les règles : on place 10 tuiles (qui existent toutes en double, il y a donc en fait 5 groupes de 2 tuiles), de sorte que 2 tuiles identiques ne soient pas adjacentes (c'est cette règle qui rend l'analyse mathématique difficile).

Je pose le problème sous la forme d'un problème de satisfaction de contraintes. On a donc 10 variables v1 à v10 (correspondant aux 10 tuiles), pouvant prendre une valeur entre 1 et 10 (la position de la tuile sur le plateau, v3=5 signifie que la tuile n°3 doit être à la 5e place).

Chaque variable doit donc prendre une valeur différente. On pose la contrainte all_different(v1..v10).

v1 et v2 représentent des tuiles identiques, de même que v3 et v4, v5 et v6, etc. (v1=1, v2=3) et (v1=3, v2=1) représente donc la même solution. Pour éliminer ces solutions « parasites », on pose les contraintes v1
Deux tuiles identiques ne peuvent être adjacentes. Pour coder cette contrainte, il suffit de remplacer les contraintes précédentes par v1
Finalement, on peut remarquer que pour une solution donnée, on peut en obtenir une autre en inversant deux types de tuile. On peut donc simplifier les calculs en rajoutant la contrainte (v1
Voici le programme Prolog correspondant :

yotd(N) :-
length(V,10),
fd_domain(V,1,10),
fd_all_different(V),
adjacency(V),
permut(V),
findall(V, fd_labeling(V), S),
length(S, N1),
N is N1*120.
adjacency([V1,V2|V]) :-
V1 #<# V2-1,
adjacency(V).
adjacency([]).
permut([V1,_,V3|V]) :-
V1 #<# V3,
permut([V3|V]).
permut([_,_]).


Et donc le résultat : 39 480 configurations de départ différentes.
Actorios
Actorios
scand1sk dit:Quelqu'un sur BGG a posé cette question… et le problème est loin d'être trivial. Pour les deux du fond que ça intéresse, je l'ai résolu de manière informatique. Je ne suis même pas sûr qu'il soit possible de le résoudre de manière purement analytique. Si quelqu'un se sent de le faire…
Je rappelle les règles : on place 10 tuiles (qui existent toutes en double, il y a donc en fait 5 groupes de 2 tuiles), de sorte que 2 tuiles identiques ne soient pas adjacentes (c'est cette règle qui rend l'analyse mathématique difficile).
Je pose le problème sous la forme d'un problème de satisfaction de contraintes. On a donc 10 variables v1 à v10 (correspondant aux 10 tuiles), pouvant prendre une valeur entre 1 et 10 (la position de la tuile sur le plateau, v3=5 signifie que la tuile n°3 doit être à la 5e place).
Chaque variable doit donc prendre une valeur différente. On pose la contrainte all_different(v1..v10).
v1 et v2 représentent des tuiles identiques, de même que v3 et v4, v5 et v6, etc. (v1=1, v2=3) et (v1=3, v2=1) représente donc la même solution. Pour éliminer ces solutions « parasites », on pose les contraintes v1Deux tuiles identiques ne peuvent être adjacentes. Pour coder cette contrainte, il suffit de remplacer les contraintes précédentes par v1Finalement, on peut remarquer que pour une solution donnée, on peut en obtenir une autre en inversant deux types de tuile. On peut donc simplifier les calculs en rajoutant la contrainte (v1Voici le programme Prolog correspondant :

yotd(N) :-
length(V,10),
fd_domain(V,1,10),
fd_all_different(V),
adjacency(V),
permut(V),
findall(V, fd_labeling(V), S),
length(S, N1),
N is N1*120.
adjacency([V1,V2|V]) :-
V1 #<# V2-1,
adjacency(V).
adjacency([]).
permut([V1,_,V3|V]) :-
V1 #<# V3,
permut([V3|V]).
permut([_,_]).

Et donc le résultat : 39 480 configurations de départ différentes.


Je dois faire partie des deux du fond... Même si la démonstration me passe un peu au dessus de la tête (mes cours de stats sont bien loin), la réponse est intéressante. :wink:
Mon top
Aucun jeu trouvé
scand1sk
scand1sk
Ce n'est pas une démonstration à proprement parler, c'est l'ordinateur qui fait ce travail, je lui dis juste ce qu'il faut démontrer…
Gadget
Gadget
Si Actorios est le premier, je suis le 2e du fond :wink:
Merci pour le calcul, c'est effectivement intéressant.

David, près du radiateur.
Mon top
Actorios
Actorios
scand1sk dit:Ce n'est pas une démonstration à proprement parler, c'est l'ordinateur qui fait ce travail, je lui dis juste ce qu'il faut démontrer…


C'est déjà plus que ce que je ne peux faire... :D
Je corrige donc en remplaçant "démonstration" par "formulation" du problème.
Mon top
Aucun jeu trouvé
Wlam
Wlam
Intéressant - je ne m'étais jamais vraiment posé la question. Après un petit quart d'heure devant une feuille blanche, je ne vois pas de solution simple pour calculer ça. C'est assez facile de majorer par 10! / 2^5, mais pour aller plus loin...

Mais j'ai trouvé ça sur l'OEIS : http://www.research.att.com/~njas/sequences/A114938

Donc la formule serait a(n)=Sum_{k=0..n}((C(n, k)*(-1)^(n-k)*(n+k)!)/2^k) avec n=5.

Ce n'est pas une démonstration non plus...
Mon top
Aucun jeu trouvé
loïc
loïc
La solution dépend du nombre de joueurs, non ?
Mon top
Aucun jeu trouvé
Actorios
Actorios
loic dit:La solution dépend du nombre de joueurs, non ?


Ici, on parle de la situation de départ... avant la sélection des personnages... Parce que s'il faut pondérer les différents choix possibles, il faut ajouter un facteur selon le nombre de joueurs. Qui veut se lancer dans ce calcul (beaucoup plus simple)?
Mon top
Aucun jeu trouvé
scand1sk
scand1sk
Actorios dit:
loic dit:La solution dépend du nombre de joueurs, non ?

Ici, on parle de la situation de départ... avant la sélection des personnages... Parce que s'il faut pondérer les différents choix possibles, il faut ajouter un facteur selon le nombre de joueurs. Qui veut se lancer dans ce calcul (beaucoup plus simple)?


Pour les personnages, c'est facile : comme au début, on ne peut choisir que des jeunes, chaque joueur prend deux personnages parmi neuf. Le premier joueur a le choix entre (9 2) = 36 combinaisons possibles, le deuxième 35, etc. Suivant si on considère l'ordre comme important ou non (il l'est pendant le choix, mais ne l'est plus une fois fait puisque l'ordre du tour dépend alors du choix), il y a 36!/(36-n)! ou (36 n) combinaisons possibles (respectivement 45 239 040 et 376 992)
loïc
loïc
J'étais un peu fatigué, j'avais mal compris. J'aurais jamais cru qu'un problème de ce genre pouvait poser problème justement.
Mon top
Aucun jeu trouvé