Remplissage d’une grille pseudo-aléatoire sous contraintes type sudoku

Bonjour à tous

ça fait plusieurs jours que j’essaie de chercher quelque chose ressemblant à mon problème sur différents forums et je suis toujours bredouille…

J’aurais besoin de remplir une grille de 28 lignes (7 blocs de 4), sur 4 colonnes avec uniquement des 1, des 2, des 3 et des 4, répondant à certaines contraintes (pas de doublon sur une même ligne, pas de doublon sur une même colonne pour chacun des 7 blocs, certaines cellules impérativement égales (par exemple B3 est toujours égale à E5) et certaines cellules devant être impérativement différentes de certaines autres cellules (du genre B3 doit forcément être différente de B10,…).
En fait cela correspond à une rotation de groupes de module sur 4 périodes pour des élèves d’une école avec un fonctionnement particulier. Depuis des années on fait ça à la main, en tâtonnant, par essais successifs, mais si on peut automatiser l’affaire ce serait pas mal.

Est ce que quelqu’un aurait une idée de la manière dont on pourrait s’y prendre ? Avec la fonction ALEA ? (Mais comment faire du ALEA sous contraintes avec autant de contraintes ?). J’ai essayé le solveur en entrant toutes les contraintes mais il ne les respecte pas du tout…

merci beaucoup d’avance !!

Question 1 : pouvez-vous nous donner la liste exhaustive des contraintes ? Lorsque vous écrivez "par exemple B3 est toujours égale à E5", ce n'est qu'un exemple. On ne peut pas travailler avec un exemple s'il n'obéit pas à une règle.

Question 2 : pouvez-vous illustrer par des couleurs ces contraintes à l'aide d'un tableau fait à la main ?

Question 3 : je suppose qu'un même chiffre (de 1 à 4) ne peut pas se répéter dans une même ligne ou une même colonne d'un bloc 4x4. Vous confirmez ?

Bonjour,

merci beaucoup pour votre réponse. Oui désolé je suis resté trop évasif.

Pour la question 3 : oui je confirme.

Pour les questions 1 et 2, voici la grille exacte, avec toutes les contraintes écrites. Par contre, je ne voyais pas comment exprimer toutes ces contraintes avec des couleurs... L'idée c'est de savoir s'il existe un moyen qu'Excel donne toutes les possibilités correspondant à ces contraintes.

N'hésitez pas à me dire si quelque chose n'est pas clair... ou si ce n'est pas faisable ...!

Merci beaucoup d'avance !

Ca commence mal.
Pour les deux modules du bas : aucune manoeuvre n'est possible puisqu'il n'y a qu'une seule solution :

Est-ce que vous maintenez votre énoncé ?

bonjour le fil,

moi aussi, je n'arrive pas à résoudre, il y a chaque fois 2 constraints qui blocquent ...

En effet, j'aurais dû remplir les deux derniers blocs directement vu qu'il n'y a qu'une seule possibilité. C'est bien ce raisonnement que j'ai fait pour remplir ma grille, mais je ne sais pas pourquoi je me suis persuadé que les lignes centrales pouvaient être échangées, ce qui est faux, car ça contredit les égalités de cellules qui ont été imposées. Du coup, c'est pour cela que j'ai laissé les lignes vides, mais désolé, j'aurais pu vous épargner cette étape...

Par contre, c'est lorsqu'on commence à remplir "à la main" les autres blocs, en remontant, qu'on est obligé de faire des "essais", comme au sudoku, et que le nombre de combinaisons devient assez gigantesque. En revanche, je ne suis pas capable de savoir si au final la solution est unique ou pas...

Mais oui, je maintiens mon énoncé. L'idée étant de trouver un moyen d'automatiser grâce à Excel, quand bien même il n'y aurait qu'une possibilité, pour ne pas justement à avoir à faire tous ces raisonnements et tous ces essais successifs. Mais comme je suis très peu expert de Excel, je ne sais pas du tout si c'est possible...

Merci encore !

@BsAlv : merci ! Comment avez-vous procédé avec Excel ? Quelles contraintes ont bloqué ?

Je vois que les chiffres qui avaient été imposés (maths et SVT sur les deux blocs du bas) ne sont plus les mêmes en revanche, donc la solution ne pourra pas convenir...

bonjour,

oui, je n'avais pas retenu ces valeurs, maintenant, oui.

C'est une macro "Trial and Error", elle n'est pas bien écrit et aussi pas vraiment flexible quand on change par exemple ces valeurs, mais c'était plaisant.

Vous écrivez : "Depuis des années on fait ça à la main, en tâtonnant, par essais successifs, mais si on peut automatiser l’affaire ce serait pas mal.".

Pouvez-vous nous prouver qu'il y a au moins une solution trouvée par tâtonnements successifs. Si vous en avez une, elle ne peut pas être unique et votre problème est relativement simple. Si vous n'en avez pas, c'est une autre paire de manche.

@Optimix : merci pour vos réponses ! En fait, depuis de très nombreuses années, cette grille était remplie à la main, et il y a toujours eu une solution. Cependant, chaque année, il y a de petites différences, les numéros fixés au départ ne sont pas les mêmes, une discipline peut différer d'une année à l'autre, etc. mais ça reste sensiblement la même chose. Celle que je vous ai postée (qui est donc celle pour la rentrée prochaine) a été résolue à la main correctement mais sans respecter les deux contraintes marquées "si possible". Avec ces deux contraintes supplémentaires, je ne peux donc pas garantir qu'elle soit résolvable mais a priori j'aurais tendance à penser que oui. Sans ces deux-là oui elle l'est, il y a au moins une solution.

J'aimerais trouver un processus (formules, macros, solveur, ou je ne sais quoi) qui puisse fonctionner et que je puisse adapter chaque année en fonction des différentes contraintes. J'ai essayé le solveur, mais ça ne respecte pas du tout les contraintes que j'ai rentrées, c'est assez curieux...j'ai pensé à des formules avec ALEA mais je ne vois pas comment conditionner les ALEA par des contraintes... sinon comme le propose BsAlv une macro, mais je ne sais pas du tout faire...

@BsAlv : merci beaucoup pour le boulot ! Par contre, j'ai l'impression que cette fois ce sont les égalités de cellules qui n'ont pas été respectées...dans la grille d'origine les cases qui marquaient un zéro contenaient en fait une formule qui les obligeait à être égales à d'autres cellules du tableau.

Merci beaucoup à tous les deux en tout cas pour l'intérêt que vous portez à mon problème.

bonjour,

en PJ 10 solutions avec les contraintes supplémentaires. Vous voyez des erreurs ?

Concernant les formules et les égalités, le but est d'avoir 0 partout et on fait la somme dans la cellule I1, cela veut dire qu'aucune contrainte a été violée. (1=violée)

Il faut penser à l'envers

#BsAlv

J'ai mis en couleur les case devant comporter des valeurs identiques. Si on clique sur la cellule E24, on voit qu'elle doit contenir la valeur de la cellule C28.
Vos 5 premières solutions ne respectent pas cette contrainte. Je n'ai pas regardé le reste. J'avais indiqué en plus qu'il n'y avait qu'une seule solution pour les modules 5 et 6 (les 2 derniers) et avais fourni cette solution. Le problème ne se pose donc que pour les 5 premier modules.

#nonoparadox
Puisque vous détenez une solution manuelle (sans les dernières contraintes), pourquoi ne la proposez-vous pas comme demandé ? Cela nous ferait gagner du temps. Surtout que rien ne dit qu'avec les contraintes optionnelles il y ait une solution.

re,

@Optimix, je n'avais pas compris votre schéma de hier à midi, à mon avis, il n'y a pas de relation entre les lignes 23-24 et 27-28. C'est vrai que le nombre de solutions est limité.

Pour 23 c'est "2143" ou "3421" et pour 24 l'autre.

Pour 27, c'est "4321" ou "1243" et pour 28 l'autre.

Mais si 23 choisit l'un, 27 n'est pas limité dans son choix, il n'y a aucun contraint dans le textbox bleu qui contient ces lignes. (si je me trompe, excusez-moi)

@nonoparadox, vous avez essayé avec solveur, est-ce que je peux voire votre solution (qui n'était pas 100%). Je me demandais comment on crée un modèle avec autant de contraintes binaires. OpenSolver est un autre outil d'optimalisation et est souvent mieux que "solveur", peut-être que "OpenSolver" sait le résoudre.

Bonjour

désolé pour mon délai de réponse, la solution que je croyais juste ne l'était pas. Entre temps, j'ai réussi à retrouver une ancienne rotation, qui colle parfaitement, à part sur l'une des deux contraintes "si possible" qui n'est respectée que lors de deux périodes sur les quatre.

La voici en PJ.

@BsAlv : j'ai essayé le solveur uniquement sur les deux blocs inférieurs (8 lignes), en ne rentrant que les contraintes "tous différents" pour les lignes et les colonnes, le fait que tout est compris entre 1 et 4, et le fait que tout soit entier. Et déjà rien qu'avec ça, il m'a mis plein de doublons sur chaque ligne et chaque colonne...La contrainte "tous différents" n'avait pas l'air de fonctionner...

Et comme le solveur semble fonctionner forcément avec un objectif, j'ai choisi une cellule au hasard extérieure au tableau dans laquelle j'ai mis =somme(C22:C29) avec pour objectif 20.

Super. Hélas il y a deux os :

C9 = C17 et
D9 = D17.

Mais avant de démarrer j'ai besoin de savoir si ce défaut est acceptable. Sinon, il faut en chercher un autre.

Mince tu as raison !! Non il faudrait vraiment que ces cellules ne soient pas égales. L’ancienne rotation que j’ai prise n’était pas totalement identique au niveau des matières et en mettant deux modules de SVT sur les 6/5 ça complique le tout, voire même (peut être) rend le problème impossible à résoudre (j’espère pas…). J’ai été trop rapide dans ma vérification…

Bonjour à vous deux,

je pense avoir trouvé une grille qui convient (j'espère ne pas m'être trompé cette fois !!), même si ça reste fait "à la main". C'est déjà ça...!

Il n'y a que deux périodes avec seulement l'une des deux contraintes facultatives non respectée.

La voici en PJ.

Merci beaucoup pour votre aide en tout cas !!

Pouvez-vous essayer ceci, on en parle après :

Oh !! Waou.... impressionnant. Bravo.

Frustrant... je n'ai aucune notion du langage macro ... du coup je n'ai pas le plaisir de comprendre le raisonnement que vous avez élaboré pour construire cette macro. J'ai compris que ça tirait au sort parmi 24 permutations (soit 4!), donc toutes les permutations d'une même ligne. Mais ceci pour laquelle des lignes ?

J'ai essayé quelques tirages, je n'ai pas vérifié minutieusement mais à première vue toutes les contraintes ont l'air d'être respectées.

Une remarque : en fait chaque année, les lignes 22, 25, 26 et 29 sont imposées. Donc j'imagine que votre programme peut s'en trouver simplifié, et sans doute moins de combinaisons finales seront possibles.

Une dernière question : pourquoi est-ce à chaque fois les deux premières périodes pour lesquelles la SVT et la musique se retrouvent en parallèle sur les modules 5/4 ? C'est quelque chose que vous avez imposé dans le programme ?

Encore bravo et un grand merci pour ce travail !