Appariments pour des jeux à plus de 2 joueurs

Bonjour,

ON trouve beaucoup de choses sur les appariement et l’organisation de jeux à 2 joueurs, par exemple la table de Berger. Les objectifs sont:

• Tout le monde rencontre tout le monde exactement une fois
• Les parties avec les blancs ou les matchs à domicile sont équilibrées, i.e. un joueur donné a autant de fois l’avantage qu’il ne l’a pas, et il ne joue pas plus de deux fois d’affilée dans la même configuration avantageuse ou désavantageuse

Par contre, je ne trouve absolument rien en ce qui concerne des jeux à plus de deux joueurs. Dans mon cas je n’ai pas de notion d’avantage type commencer avec les blancs ou jouer à domicile, mais sinon l’objectif de base demeure:

Étant donné un jeu à J joueurs et N participants, le but est de générer automatiquement une grille d’organisation telle que:

• Chaque joueur rencontre chaque autre joueur exactement une fois pendant le tournoi; ou à défaut de pouvoir rencontrer tout le monde on évite à tout prix que deux joueurs se retrouvent ensemble plusieurs fois.
• Tous les joueurs sont toujours occupés, i.e. pas de "tour d’attente", ou autrement dit un maximum de parties se jouent simultanément. On partira du principe que N%J=0 (pas de laissé pour compte ni de victoire par forfait)
• Combien chaque joueur jouera-t-il de parties ? OU combien au maximum sans qu’il n’y ait de double rencontre ?
• Est-ce toujours possible ?

Prenons un exemple: j’ai 9 participants qui vont jouer à un jeu qui se joue à 3. Au premier tour c’est facile, on a :

• 1, 2, 3
• 4, 5, 6
• 7, 8, 9

Au deuxième tour c’est facile, on peut intervertir les axes:

• 1, 4, 7
• 2, 5, 8
• 3, 6, 9

Au troisième tour, on prend en diagonale:

• 1, 5, 9
• 2, 6, 7
• 3, 4, 8

Au quatrième tour, on prend en diagonale dans l’autre sens:

• 1, 6, 8
• 2, 4, 9
• 3, 5, 7

Et on peut s’arrêter là car tout le monde a rencontré tout le monde. Preuve: chaque joueur a disputé 4 parties et a rencontré 2 autres joueurs à chaque fois, chacun a donc rencontré les 8 autres joueurs, CQFD.

Maintenant si on fait le même exercice avec 16 participants pour un jeu à 4 joueurs, on obtient:

Tour 1:

• 1, 2, 3, 4
• 5, 6, 7, 8
• 9, 10, 11, 12
• 13, 14, 15, 16

Tour 2:

• 1, 5, 9, 13
• 2, 6, 10, 14
• 3, 7, 11, 15
• 4, 8, 12, 16

Tour 3:

• 1, 6, 11, 16
• 2, 7, 12, 13
• 3, 8, 9, 14
• 4, 5, 10, 15

Si on continue avec l’idée des diagonales on arrive à:

• 1, 8, 11, 14
• 2, 5, 12, 15
• 3, 6, 9, 16
• 4, 7, 10, 13

Or 1 et 11 se sont déjà rencontrés, tout comme 2 et 12 et 6 et 16. Donc ça marche pas. Est-ce que mon truc est foireux ou est-ce que c’est effectivement impossible d’aller au-delà de 3 parties ? Si on voulait que tout le monde rencontre tout le monde il nous en faudrait 5.

J’ai essayé de calculer avec 25 joueurs pour un jeu à 5, et là j’ai réussi à le faire, avec le truc des diagonales puis ensuite des décalages modulo 2. IL y a 6 parties; comme 6*4=24 on sait que tout le monde a rencontré tout le monde.

Si on suit l’intuition, à 36 on serait limité à 5 tours sans avoir rencontré tout le monde, et à 49 ça marche avec 8 tours ? Ca ne marcherait pas pour 5 tours à 16 et pourtant le cas trivial de 3 tours à 4 participants lui fonctionne ?

Je me fiche de savoir s’il y a plusieurs répartitions parfaites possibles en pratique, mais c’est aussi une question intéressante. Mon intuition mathématique me dit qu’il doit y avoir un lien avec les carrés latins, les carrés magiques ou les sudoku, mais je n’entrevois qu’à moitié comment… pareil avec un petit truc dans la combinatoire qui doit me faire défaut.

Retour à mon cas réel, avec la difficulté ultime: mon jeu se joue à 4 ou à 5 (j’ai le choix), et surtout il n’y aura pas forcément ni 16 ni 25 joueurs. Les inscriptions sont encore ouvertes, la limite est à 50 mais plus probablement il y aura entre 15 et 30 participants.

Alors évidemment avec une grille non carrée l’objectif tout le monde rencontre tout le monde est clairement impossible (j’ai pas de preuve, c’est uniquement de l’intuition). Mais est-ce que si je choisis la version à 4 joueurs pour 20, 24 ou 28 participants je peux faire plus de 3 tours sans que personne ne se retrouve deux fois ? Et est-ce que pour la version à 5 joueurs, généralement perçue comme tactiquement plus intéressante, je peux faire 4 tours ou plus s’il y a 20 ou 30 participants ?

Est-ce qu’on peut généraliser tout ça avec un algorithme ?

Merci !

P.S. J’ai posté dans sciences car j’estime que le problème est plus mathématique qu’informatique, et j’ai volontairement formulé la chose de manière agnostique au langage. Mais n’hésitez pas à déplacer si nécessaire.

Je cite : évidemment avec une grille non carrée l’objectif tout le monde rencontre tout le monde est clairement impossible.

Une grille non carrée, c’est une grille où on aurait un nombre J de joueurs, avec J qui n’est pas un carré parfait, c’est ça l’idée ? Et J serait le carré de T, le nombre de joueurs qu’on met ensemble à une même table.

Si c’est bien ça l’idée, alors je ne suis pas d’accord.

Dans le cas de 2 joueurs, il y a une configuration qui marche très bien. On a par exemple 10 Tables, numérotées de 1 à 10, et chaque table a 2 places ( Nord et Sud). Le joueur qui est assis en Nord-1 restera à cette place pendant toute l’épreuve. Les autres joueurs font toujours le même mouvement : Ceux qui sont assis en Nord montent d’une table à chaque changement. Celui qui est en Nord-10 va en Sud-10, ceux qui sont assis en Sud descendent d’une table à chaque changement. Et celui qui est en Sud-A va en Nord-2.

Ce mouvement marche quelque soit le nombre de tables, avec 2 joueurs par table. Je pense que par des mouvements plus ou moins du même genre, tu peux trouver des bonnes bases pour des solutions pour le cas de jeux à plus de 2 joueurs.

Une grille non carrée, c’est une grille où on aurait un nombre J de joueurs, avec J qui n’est pas un carré parfait, c’est ça l’idée ? Et J serait le carré de T, le nombre de joueurs qu’on met ensemble à une même table.

Tu me perds un peu avec ton nord/sud, je ne suis pas bien sûr de comprendre le mouvement que tu proposes. Mais effectivement, à un jeu à deux joueurs ça marche toujours, c’est la table de Berger que j’ai mis en lien plus haut.

L’idée c’est effectivement que J ne soit pas un carré parfait. Par exemple prends un jeu à T=3 joueurs et J=12 participants.

Dans la configuration T=3 et J=12, non, on ne peut définitivement pas faire en sorte que chacun se voie exactement une fois. J’ai 11 joueurs à rencontrer et j’en vois deux à chaque ronde. Nécessairement il y en a un que je vois deux fois ou alors un que je ne vois jamais.

De là on peut déjà poser une première règle: (J -1) % (T -1) == 0.
Et du coup on comprend aussi pourquoi à deux joueurs ça marche toujours.

Par contre est-ce que je peux quand même faire 5 rondes ? Toujours pour l’exemple T=3 et J=12. J’ai beau le manipuler dans tous les sens à coups de shift et de miroirs, je bloque pour trouver une troisième ronde convenable.

Plus généralement, est-ce que je peux toujours faire R = floor( (J -1) / (T -1)) rondes ? Quitte à ne pas rencontrer tout le monde. ET si oui surtout comment ?

Est-ce qu’on peut généraliser tout ça avec un algorithme ?

Peut-être :\

Un truc qui pourrait être intéressant à regarder, c’est un "solveur de contrainte".

C’est un peu moins intéressant que de trouver un algo qui résout exactement ton problème (et du coup c’est dommage). Mais ça pourrait éventuellement servir dans plein plein d’autres cas que tu as.

Wiki : https://fr.wikipedia.org/wiki/Programmation_par_contraintes (y’a des exemples de bibliothèques qui font ça dans tout plein de langage tout en bas)

Désolé de pas te donner LA solution, c’est sûrement un peu frustrant, mais j’ai l’impression que ce domaine pourrait être intéressant pour toi.

Bonsoir,

Est-ce que tu aurais un tutoriel et/ou une bibliothèque en particulier à conseiller parmi tout ce qui est listé dans la page wikipedia ? Histoire de commencer de bon pied dans un domaine qui m’est mal connu, et d’acquérir les concepts de base qui me permettront de modéliser mon problème. Faire quelques essais me diront bien vite si c’est intéressant de poursuivre par là.

Pour l’instant le langage m’importe peu entre Java, C++ et Python, tant que ça s’installe assez facilement à la fois sous windows et linux; par contre ça m’arrangerais si c’était gratuit et pas un truc avec une GUI.

Du coup, vu ce que tu me recommandes, tu sous-entends que le problème générique est en fait NP complet ou pas loin ? Il faut que je me replonge dans mes cours…

Merci.

Essaie Choco en Java.

Ca fait facilement 7 ans que je n’y ai pas touché, à l’époque ça m’avait pris du temps de bien comprendre les concepts (comment on définit le domaine, les contraintes, etc.) mais j’étais hyper inexpérimenté donc j’imagine que ça devrait aller plus vite pour toi.

Une fois le jargon et les concepts à peu près compris, c’était assez facile de jouer avec.

Bon, c’est des souvenirs… Donc ça vaut pas grand chose, mais ça a l’air vachement mieux documenté qu’à l’époque où je me battais avec simplement la javadoc offline…

u sous-entends que le problème générique est en fait NP complet ou pas loin ? Il faut que je me replonge dans mes cours…

Oula non je ne sous-entends rien du tout, et surtout pas dans un domaine que je ne maîtrise absolument pas.

Simplement que pour résoudre des problèmes similaires (brute-forcer un problème qui possède des contraintes bien définies) ça m’avait vachement aidé.

Ca vaudrait le coup que moi aussi je relise bien la doc, parce que c’est quand même des systèmes assez intelligents, entre autre dans la façon dont ils "réduisent" le domaine d’origine.

Ca fait facilement 7 ans que je n’y ai pas touché, à l’époque ça m’avait pris du temps de bien comprendre les concepts (comment on définit le domaine, les contraintes, etc.) mais j’étais hyper inexpérimenté donc j’imagine que ça devrait aller plus vite pour toi.

Pas sûr, je n’ai jamais fait de programmation par contraintes donc pour l’instant je n’ai pas la moindre idée de comment on modélise un problème pour un tel système. Je vais découvrir.

Simplement que pour résoudre des problèmes similaires (brute-forcer un problème qui possède des contraintes bien définies) ça m’avait vachement aidé.

Ca fait certainement beaucoup mieux que de la brute-force, enfin j’espère. Parce que mine de rien ça fait R*J! possibilités, si je calcule bien. Très grossièrement arrondi, une recherche exhaustive pour savoir si vraiment 5 rondes à 4x4 joueurs c’est impossible, ça ferait déjà 5*16! = 2^46 combinaisons soit 64 mille milliards. J’ai pas un supercalculateur à disposition.

En attendant merci, je vais essayer Choco et vous tenir au courant.

Savoir si c’est NP complet, on s’en moque. Ces questions là seraient intéressantes si tu avais 100000 joueurs par exemple.

Pour 5 rondes à 4x4 joueurs, le nombre de combinaisons à explorer est beaucoup moins élevé que ce que tu dis.

1ère position, tu places tes 16 joueurs, au hasard. Fin, il n’y aura pas d’autre cas à analyser pour la 1ère position. Disons même que les joueurs 1 2 3 et 4 se sont rencontrés dans la salle n°1, les joueurs 5 6 7 et 8 dans la salle n°2 etc.

Pour les positions suivantes, le joueur n°1 ne bouge jamais. Ca ne sert à rien de le faire voyager vers la salle n°2 ou n°3 ou n°4. S’il doit rencontrer les joueurs X Y et Z, que cela se passe dans la salle 1 ou 2 ou 3 ou 4, peu importe.

Toujours pour les positions suivantes, chaque joueur a en fait 4 positions possibles et pas 16. Il y a 4 places dans la salle n°2. Mais ces 4 places sont parfaitement interchangeables.

Et comme 2 joueurs ne peuvent pas se rencontrer 2 fois, il y a plein de 'scénarios’ qui mènent très vite à une impasse.

Recenser toutes les combinaisons, et déterminer si oui ou non il y a une solution, ça ne prendra pas plus d’une minute. Et même pour des nombres de joueurs plus élevés.

Savoir si c’est NP complet, on s’en moque. Ces questions là seraient intéressantes si tu avais 100000 joueurs par exemple.

C’était une question bonus, pour la culture, et la beauté de la théorie. Mais effectivement pour un cas pratique on s’en fout complètement.

Pour 5 rondes à 4x4 joueurs, le nombre de combinaisons à explorer est beaucoup moins élevé que ce que tu dis.

JE calculais le brute-force en mode ultra-naïf. Evidemment qu’on peut faire beaucoup mieux.

1ère position, tu places tes 16 joueurs, au hasard. Fin, il n’y aura pas d’autre cas à analyser pour la 1ère position.

Pour les positions suivantes, le joueur n°1 ne bouge jamais.

Ca, ça me paraissait comme des évidences. La preuve, je n’ai même pas pris la peine de les expliciter.

Toujours pour les positions suivantes, chaque joueur a en fait 4 positions possibles et pas 16. Il y a 4 places dans la salle n°2. Mais ces 4 places sont parfaitement interchangeables.

En effet, bien vu. J’ai perdu des réflexes en combinatoires. Dans le cas 4x4 on peut donc diviser par 4!, sauf erreur.

Et comme 2 joueurs ne peuvent pas se rencontrer 2 fois, il y a plein de 'scénarios’ qui mènent très vite à une impasse.

Alors comment tu expliques que ça marche avec 5x5 si on ne peut pas avec 4x4 ? J’ai réussi à le faire à la main… Et qu’en est-il pour les grilles non carrées ? Combien de rondes je peux faire au maximum ?

Pour 16 joueurs, 5 positions, 4 tables de 4 joueurs, il y a une mise en place possible. Voici un lienvers une solution (début de la page 13).

Pour la question : Existe-til forcément une mise en place qui permette de faire floor(J-1)/(T-1) rondes … Si J/T est grand, très probablement oui. Plus on a de rondes et plus on a de joueurs, plus on a de 'leviers’ pour jouer sur le résultat.

Pour des petits nombres, il y a des risques de ne pas trouver de solution.

Tu parlais à un moment de pouvoir faire des tables de 4 ou 5 joueurs.

Imaginons que tu as 29 joueurs. Peux- tu dire : on va faire 5 tables de 5 joueurs et une table de 4 joueurs pour la 1ère ronde (55+4=29). Puis pour la 2ème ronde, on va faire une seule table de 5 joueurs, et 6 tables de 4 joueurs (5+64=29), etc etc …

Si ton jeu permet ça, alors ça assouplit pas mal les contraintes, et tu devrais pouvoir trouver des mises-en place pour à peu près tout nombre de joueurs.

Tu parlais à un moment de pouvoir faire des tables de 4 ou 5 joueurs.

Imaginons que tu as 29 joueurs. Peux- tu dire : on va faire 5 tables de 5 joueurs et une table de 4 joueurs pour la 1ère ronde (55+4=29). Puis pour la 2ème ronde, on va faire une seule table de 5 joueurs, et 6 tables de 4 joueurs (5+64=29), etc etc …

Non. En téhorie c’est possible, mais en pratique c’est injuste si toutes les tables n’ont pas le même nombre de joueurs. On ne joue pas de la même façon à 4 qu’à 5. En fait les derniers inscrits sont remplaçants en attendant de pouvoir constituer des tables supplémentaires.

Merci pour le pavé mis en lien. Leur système nord/sud/est/ouest me perturbe, j’ai du mal à penser de cette façon. Mais au moins maintenant on sait que la solution 5 rondes 4x4 existe.

Pendant ce temps j’ai commencé à faire quelques essais avec Choco. C’est intéressant, mais pour l’instant je n’y arrive pas.

Pour l’instant, mon idée est de modéliser chaque table avec une variable de type set (SetVar). Ca me parait plus facile qu’avec des variables entières: moins de variables à déclarer, et surtout je capture implicitement le fait que je me fiche de l’ordre d’apparition des joueurs à une table donnée, i.e. {1,2,3}, {1,3,2}, {2,1,3}, etc. sont tous égaux.

// matrice des tables: nRounds x nTables
// emptySet={}, fullSet={1, 2, 3, ..., nParticipants}
SetVar[][] allTables = model.setVarMatrix("table", nRounds, nTables, emptySet, fullSet);

// Définition des contraintes de base
for (SetVar[] tables: allTables) {
// à la même ronde, l'ensemble des participants aux tables prises deux à deux sont disjoints, i.e. un joueur ne peut pas se trouver à deux tables en même temps
model.allDisjoint(tables).post();
// Chaque table compte exactement tableSize participants
for (SetVar s: tables) s.setCard(tableSize);
}

Jusque-là, ça va, c’est après que ça se corse, évidemment.

Mon idée pour exprimer la contrainte principale est de dire que, pour toutes les tables T1 et T2 prises deux à deux, la cardinalité de l’intersection de T1 et T2 est 0 ou 1.

En plus clair, si T1 et T2 ont en commun 2 éléments ou plus, alors ça implique que les joueurs incriminés vont se rencontrer plusieurs fois. Par exemple dans {1,2,3} et {2,3,4} on voit bien que J2 et J3 vont se voir deux fois.

Par contre, j’arrive à formuler cette contrainte sur le papier, mais pas en code. J’ai essayé plusieurs choses dont celle-ci:

for (int i=0; i<nRounds; i++) {
for (int j=i+1; j<nRounds; j++) {
for (int k=0; k<nTables; k++) {
for (int l=0; l<nTables; l++) {
if (k==l) continue; //*1
SetVar[] vars = { allTables[i][k], allTables[j][l] };
SetVar intersection = model.setVar(emptySet, fullSet);
model.intersection(vars, intersection, true).post(); // J'ai pas encore compris à quoi sert le booléen, mais il ne change rien
model.member(uniqueSets, intersection).post(); // Variante 1
intersection.setCard(zeroOrOne); // Variante 2
}}}}

Pour la variante 1, je pose la condition que l’intersection soit une des possibilités {}, {1}, {2}, {3}, …, {nParticipants}. Autrement dit j’énumère les ensembles possibles contenant 0 ou 1 élément.

Dans la variante 2, j’instancie une nouvelle variable zeroOrOne pour chaque cas, qui, comme son nom l’indique, a un domaine {0, 1}. Puis je pose la condition que la cardinalité de l’intersection vaut donc 0 ou 1. Les deux variantes sont censées être identiques n’est-ce pas ?

Note: j’impose j>i dans la boucle parce que dans une même ronde, je suis normalement déjà couvert par la contrainte allDifferent posée au début.

Et le résultat est que… ces conditions sont ignorées. En lançant la résolution pour 4 rondes à 3x3, j’obtiens immédiatement {1, 2, 3}, {4, 5, 6}, {7, 8, 9} 4 fois.

Maintenant si je commente la ligne *1, le solveur tourne en boucle. Après plusieurs minutes je n’ai toujours pas de réponse. Pourtant pour 4 rondes à 3x3 ça devrait être assez rapide. Je ne comprends pas ce qui se passe. Ca veut dire que mes conditions ne sont peut-être pas si ignorées que ça en fait…

Mais bon, ça ne marche quand même pas.

Je crois savoir ce qui se passe. Quand j’écris: model.intersection(vars, intersection, true).post();, je crée une contrainte qui ne contraint en fait rien du tout. Je définis que l’intersection des deux tables peut valoir n’importe quoi entre {} et {1,2,3,…,nParticipants}. En clair, T1 inter T2 = X. Mais ce que je veux c’est l’inverse: poser X = T1 inter T2, puis ensuite poser des conditions sur X. Et ça, même en fouillant bien la doc, j’ai pas compris comment je peux le faire.

Du coup il faut trouver une autre idée de modélisation; et je sèche.

Merci.

L’histoire des Nord Sud Est Ouest, c’est quoi ? Dans un jeu de carte ou de monopoly ou autre … il y a une table. Supposons cette table carrée, et supposons qu’on ait 4 joueurs assis à cette table. Il y a donc un joueur qui est assis au Nord, un autre au sud, un autre à l’est et le dernier à l’ouest. Dans les tournois de jeu de cartes la position de chaque joueur à une importance, mais a priori, dans ton cas, ce que tu veux c’est que les 4 joueurs désignés jouent à la même table (ou dans la même salle) et chacun n’a pas une place attitrée à cette table.

Je ne connais pas du tout les outils que tu utilises pour programmer ça, je ne peux pas t’aider. Eventuellement, je vais le faire dans quelques jours, avec mes outils. Si je me lance, je te tiens au courant.

Un autre point qui mérite clarification.

Imaginons 27 joueurs, et le jeu s’organise en tables de 4 joueurs. A chaque tour, il y aura donc 6 tables de 4 joueurs et 3 joueurs en repos.

Le nombre de tours sera 9 tours et non 8. A chaque tour, 3 des joueurs seront en repos, et chaque joueur jouera 8 fois. Donc dans la formule R = Floor((J-1)/(T-1)), si R désigne le nombre de rondes jouées par chaque joueur, c’est ok. Mais a priori, R désigne le nombre total de rondes, et donc R = Floor((J-1)/(T-1))+1.

Je n’ai pas été assez clair visiblement. Je la refais: en fait il ne peut pas y avoir 27 joueurs. C’est une variante intéressante au problème initial, mais elle ne m’intéresse pas.

S’il y a 27 inscrits, il y a 24 joueurs effectifs, et 3 qui remplacent en cas d’absence, de retard, ou de problème de connexion. Si tout le monde est présent à l’heure, les remplaçants ne jouent jamais.

En combi c’est vraiment facile de tomber sur des problèmes non triviaux, et la version « combien de parties au maximum on peut jouer » de ton premier message s’appelle le Social Golfer Problem dans la littérature (spoiler : on sait pas montrer grand chose, cf. par exemple l’entrée correspondante sur OEIS).

Soit un jeu à J joueurs et N participants.

Si on part du principe qu'il n’y a pas de tour d’attente alors, à chaque tour, tous les joueurs jouent. Nécessairement, on a alors le nombre de groupes $G = \frac{N}{J}$

La règle « de socialisation maximale » (j’adore ce nom) nous donne qu’à chaque tour, un participant rencontre $J-1$ joueurs et donc pour rencontrer tout le monde on a directement qu’il doit faire: $\frac{N-1}{J-1}$ parties.

On a donc que pour un jeu à $J$ joueurs, $N$ ne peut pas être choisi au hasard. $N$ doit être un multiple de $J$ tel que $N-1$ soit un multiple de $J-1$.

On prouve que tous les carrées ($N=J^2$) respectent cette règle car :

$(x-1)(x+1) = x^2-1$

Je raconte que des évidences mais si ça peut aider quelqu’un, voilà.

PS: Rajout d’une hypothèse sur la première phrase.

@Ache: tu prouves qu’il est possible ou non que tout le monde rencontre tout le monde mais sans tenir compte de la règle deux personnes données ne se rencontrent pas plus d’une fois. Je ne sais pas si ça prouve en même temps que l’arrangement est toujours possible ?

J’avais pas fait le lien avec l’identité remarquable (mes années de maths pures commencent à s’éloigner) mais le reste de ce que tu dis me paraissait plus ou moins évident, effectivement.

Comme ce n’est pas moi qui impose N, on sait qu’on n’y arrivera pas toujours mais le but est de faire le maximum, i.e. le plus de rondes possibles tel que deux personnes ne se rencontrent pas plus d’une fois.

@Lucas-84: ah, eh bien nous y voilà. LE social golfer problem. J’aime bien aussi leur terme de socialisation maximale.

Du coup si on en sait si peu (vu ton lien, effectivement c’est pas grand chose), je pense qu’on peut en déduire que le problème est difficile, car sinon quelqu’un aurait sûrement déjà trouvé une solution. ET donc du coup la réponse la plus pratique et pragmatique pour répondre à quelques instances bien précises bien concrète du problème est celle de Javier. C’est sûrement plus simple que de concevoir un algorithme de A à Z soi-même.

Je suis content, j’ai découvert la programmation par contrainte. C’est probablement par là que je dois persévérer. Il faut que j’essaie d’écrire un propagateur personnalisé pour mon cas. Je vais vous tenir au courant de mon avancement de ce côté. Si vous avez autre chose à proposer n’hésitez pas quand même !

Merci à tous.

@Ache: tu prouves qu’il est possible ou non que tout le monde rencontre tout le monde mais sans tenir compte de la règle deux personnes données ne se rencontrent pas plus d’une fois.

Ah non non, je ne prouve rien du tout. Je dis juste que s’il existe une solution, il faut nécessairement que $J$ divise $N$ et que $J-1$ divise $N-1$. Ça ne prouve pas du tout qu’il existe une solution. Je contrainds la solution on va dire.

À propos du fait que je ne tiens pas compte de la rêgle règle deux personnes données ne se rencontrent pas plus d’une fois. Je fais même pire, j’utilise la règle deux personnes doivent se rencontrer une fois et une seule fois, d’où le $J-1$ divise $N-1$.

Si ce n’est pas toi qui choisi $N$ et qu’il n’y pas de tour d’attente. Alors généralement (càd si $N-1$ n’est pas multiple de $J-1$) tous les joueurs ne se rencontrerons pas tous. Et donc plus précisément aucun joueur ne rencontrera tous les autres joueurs.

Pour moi ce problème est moins intéressant, mais vu que c’est celui qui t’intéresse, je vais y réfléchir un peu

Edit: Dans ma tête, ce problème revient toujours à maximiser le nombre de $G-$partition distinctes (par leur arrètes) entre elles.

Salut,

Avec un SAT-solver ça doit bien se faire aussi je pense.

Juste pour insister sur ce qu’a dit @ache, votre $J-1 \mid N-1$ est une condition nécessaire d’existence d’une solution « parfaite » (comme tu l’as plus ou moins remarqué toi-même, il n’y a pas de solution parfaite pour $N=16$ et $J=4$, donc c’est pas suffisant). En fait, les deux conditions nécessaires $J\mid N$ et $J-1\mid N-1$ sont équivalentes à $N\equiv J\mod J(J-1)$ (par les restes chinois si on veut, mais bon c’est facile à montrer de manière ad hoc ici). En « notation informatique », ça veut dire que si n%(j*(j-1)) != j, tu n’auras pas de solution parfaite.

En fait c’est déjà plutôt fort comme condition : si t’imagines que tu te fixes un jeu à $J$ joueurs et qu’on t’envoie un nombre aléatoire uniforme de joueurs dans $\{1,\ldots,N_{m}\}$, à la limite la probabilité d’avoir une solution parfaite est inférieure à $1/(J(J-1))\approx 1/J^2$ (genre si t’as un jeu à 6 joueurs, tu sais déjà que dans 97% des cas ça va pas marcher). Note que le social golfer problem c’est calculer le nombre de maximum de jours qu’on peut tenir (ça a priori c’est difficile en général), et ça me surprendrait pas que le problème de décision « est-ce qu’il existe une solution parfaite ? » soit substantiellement plus simple.

Même si jamais c’est NP-difficile, ça veut pas dire qu’on peut rien faire : on peut regarder à quel point on peut descendre dans l’exposant de la complexité, est-ce qu’on peut trouver (et prouver ofc) des bonnes approximations, etc. Résoudre ça avec des solvers SAT ou CSP c’est moins intéressant scientifiquement, mais bon faut reconnaître que c’est bien utile en pratique. Pour le coup c’est un des cas où je dirais que c’est un peu une perte de temps de recoder ce genre de trucs (en tout cas perso je trouve pas ça super formateur), y a des gens qui passent leur vie à faire des trucs heuristiques qui vont forcément aller plus vite que tout ce que tu pourras faire (cf. par exemple le concours de SAT qu’ils organisent annuellement).

Bonsoir,

Quelques nouvelles, j’ai réussi à résoudre le problème avec Choco. J’ai fait un propagateur très simple en me basant sur le critère que j’ai déjà indiqué: l’intersection des participants des tables prises deux à deux n’admet jamais plus d’un élément en commun. J’ai pas le code pour l’instant (il est sur un autre PC), mais je le posterai si ça vous intéresse.

Je confirme que les 5 rondes à 4x4 c’est bel et bien possible. J’ignore si la solution est unique, mais ce qui est sûr c’est que quand on essaie de le faire à la main, le piège c’est de vouloir prendre les diagonales séparément. En fait ça bloque tout.

L’astuce à la troisième ronde après la première (horizontal) et la deuxième (vertical) c’est de prendre les deux diagonales en même temps (1, 6, 11, 16 et 4, 7, 11, 13). Muni de cette information, on trouve assez vite la répartition des deux dernières rondes. Alors qu’en prenant une diagonale seule au lieu des deux en même temps on se bloque au moins pour la dernière ronde. Il m’a trouvé la solution en moins d’une seconde.

La solution que Choco m’a trouvé pour 6 rondes à 5x5 est la même que celle que j’avais trouvée à la main, ça consiste basiquement en horizontal, vertical, puis ensuite des décalages de 1, 2, -1 et -2. Bizarrement c’est la configuration la plus lente, 10 secondes pour la trouver.

Il a été beaucoup plus rapide à trouver une solution pour les 9 rondes à 8x8, moins d’une seconde. J’ai du mal à comprendre pourquoi 6 rondes à 5x5 c’est 10 fois plus lent…

Là où c’est intéressant, c’est qu’il ne semble pas y avoir de solutions pour 6x6, 7x7, 9x9 et 10x10 au-delà de 3 rondes. Le problème c’est que dans ce genre de cas je n’ai pas de moyen simple de court-circuiter plus ou moins rapidement une recherche exhaustive. IL rame ad eternam. Ca serait un point d’amélioration. Quoi qu’il en soit j’ai du mal à l’expliquer. Sachant maintenant que le 4x4 est possible, j’imaginais que tous les carrés parfaits étaient possibles.

Merci.