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

@Optimix, les 4 lignes fixes des 2 derniers blocs ne sont pas respecté, je crois.

solution parfait

Quelques explications sur l'algorithme appliqué, mais uniquement dans ses grandes lignes.

- "cbad" est une permutation de la ligne "abcd". Effectivement, le nombre de permutations d'un ensemble de 4 éléments est bien égal = 4!, soit 24.

- chacune de ces permutations est une clé de codage. Le programme tire au sort une des 24 clés de façon aléatoire. Admettons que ce soit 2341. Cela signifie que les "1" de la grille "Specimen" (votre solution) seront remplacés par des "2", les "2" par des "3", les "3" par des "4" et les "4" par des "1".

- les inégalités (vos contraintes) sont toujours respectées. Exemple : les lignes 16/22 et 26 de votre solution valent 1243/4312/2134. Avec la clé 2341 cela donne 2314/1423/3241.

- les défauts aussi : les cellules C17 et D17 de votre solution comparées aux cellules C20 et D20 ont malheureusement la même valeur. C'est ce qui explique que quelle que soit la clé appliquée ces égalités seront respectées au même titre que les inégalités. Je les ai mises en évidence dans les feuilles "Specimen" et "Planning" avec un fond gris. Si un jour vous tombez sur une solution parfaite, vous pourrez virer cette couleur indésirable.

Si les lignes 22,25,26 et 27 sont changées tous les ans cela change tout (le détail qui tue). Vous allez devoir tâtonner à nouveau pour trouver un "Specimen" acceptable. Si vous devez modifier votre planning une seule fois par an, vous pouvez tout mettre à la poubelle, cet algo ne vous sert plus a à rien. C'est un programme en IA qu'il vous faut. La solution proposée ne vous fera gagner du temps que si la périodicité des plannings n'est pas annuelle (par exemple hebdomadaire, mensuelle ou trimestrielle).

Tu as raison, BsAlv. Il faut tout revoir. Mais pas avant qu'on ne connaisse la périodicité des plannings. Autre question qui me turlupine et non des moindres. Elle concerne la présentation des contraintes. Un exemple à partir du système suivant :
C16<>C22<>C26
C6<>C10<>C16

Peut-on dire que C16<>C22<>C26<>C6<>C10 ?

@Optimix,

Bien expliqué et cette récursivité, j'ai toujours des problèmes pour l'appliquer, mais c'est un outil fantastique

Ma méthode est un peu plus désordonné, plutôt comme des coups de chance. Moi, je crée aussi ces 24 permutations "ABCD" (méthode moins élégante) et puis je crée les 576 grilles 4x4 valables, de manière qu'un chiffre ne se répète pas dans la même colonne.

Puis on a la plage verte, où on met les chiffres "fixe", les lignes 22, 25, 26 et 29. Comme plaisanterie, j'ai ajouté D6:E6.

Puis, tous ces inégalités, je les ai transformé en "égalités à éviter". Voir les formules I2:L15. Je fais la somme de ces inégalités en H1 et le but est de réduire cette somme à 0. Ces formules sont comme =N(OU(C16=C22;C16=C26;C22=C26)), donc si on a plusieurs égalités, cela ne compte qu'un fois. C'était peut-être mieux de transformer cela en une somme comme =(C16=C22)+(C16=C26)+(C22=C26), petit détail. Seulement pour tester une solution, j'ai copié et collé une solution de votre planning dans ma plage C2:F29 et les MFCs oranges montrent directement les défauts, 2 contraintes moins importants et ces 4 lignes fixes.

Pour un nouveau planning, on doit vérifier si tous ces contraintes sont encore à jour + les chiffres fixe dans la plage verte.

Puis ma macro regarde pour chaque des 7 blocs, combien des 576 grilles sont valables (par exemple, seulement 2 pour les blocs 6&7) et remplace aléatoire 25.000 fois une des 7 grilles4x4 par un autre grille4x4. Si la somme des défauts en H1 est <=, alors cette solution reste, autrement on rejette ce grille4x4. Comme ce truc est aléatoire, on peut trouver une solution presque immédiatement ou on ne la trouve pas mais si on relance la macro une deuxième fois, ... .

La feuille "solutions", quand on commence un nouveau planning, on supprime toutes les colonnes à partir de C. Si la macro a trouvé une solution, elle sera copié et collé ici, donc après plusieurs fois, vous aurez plusieurs solutions ici.

Donc, au niveau des formules et au niveau "récursivité" de ma macro, il y a encore des possibilités ... . Autre détail, le poids d'un contrainte pour ceux qui sont moins importants, on peut changer cela dans la somme de H1

Un grand merci à tous les deux !

J'avoue que je commence à me sentir perdu dans vos explications du dernier post...

"Peut-on dire que C16<>C22<>C26<>C6<>C10 ?" => Je pense que ça voudrait dire qu'il y a 5 chiffres différents dans ces 5 cellules, non ?

@Optimix : En effet, c'est bien une rotation annuelle...

Mais cela ne veut pas forcément dire que votre programme ne sert à rien. Par exemple pour l'année suivante (2024-2025), si les matières restent associées de la même façon, je sais forcément quelles seront les lignes 22-25-26-29, du coup je peux avoir une rotation toute faite. Cependant, si j'ai bien compris votre raisonnement, il me suffirait, même à la main, de faire une permutation de ma grille de cette année, même si cela conserverait le "mini-bug" du SVT / musique sur deux périodes.

Là où ça va coincer, c'est que certaines années les lignes 16 et 21 s'inversent, ce qui change du coup les contraintes telles qu'elles sont référencées pour le moment. C'est pour cela qu'à la base j'avais envisagé un programme (macro, formule ou solveur) qui faisait apparaître directement les contraintes, que je pourrais modifier suivant les années.

Par exemple, cette année, une nouvelle contrainte a été mise (même matière sur les lignes 9 et 13, ce qui n'était pas le cas avant), ce qui a donc ajouté une contrainte...

@BsAlv : je n'arrive pas à utiliser votre programme, Excel me renvoie une message me disant que je n'ai pas la bonne version pour utiliser certaines choses de votre fichier...

re,

un Active-X, alors c'est le bouton qui cause ce problème ???

Nouveau essai ...

Merci beaucoup ! Votre programme, comme celui de Optimix, a également l'air génial ! Je suis très impressionné...Bravo !

Je n'ai plus le message d'erreur à l'ouverture, mais lorsque je clique sur le bouton planning, j'ai un message d'erreur qui me dit "un composant Active-X ne peut pas créer d'objet".

Cependant, il apparait plein de grilles dans l'onglet "solutions"....

Pourriez-vous m'expliquer le principe de votre programme ? Toutes les grilles qui apparaissent sont toutes les solutions possibles à partir des lignes fixées ? Et également avec toutes les contraintes respectées ? Que signifient les différentes couleurs ? Ai-je la possibilité de changer les contraintes dans votre programme ?

Encore merci ...!!!

re,

j'ai supprimé ce bouton, parce que je ne comprend pas l'origine du message et je l'ai remplacé par un raccoursi CTRL+SHIFT(=Maj)+N.

L'explication, je l'ai déjà fait hier à 9:03, mais en résumé, avec 4 chiffres, on sait faire 24 permutations (1234,2341,3412,4123,....) et avec celles, on sait faire 576 grilles valables de 4x4 dans lesquelles chaque chiffre est unique par ligne et colonne (système sudoku). C'est avec ces 576 grilles qu'on continue à travailler.

On a la plage verte pour des données fixe (cages en jaunes) et pour les autres contraintes, j'ai crée des égalités, par exemple I2 contient la formule "=(C16=C22)+(C16=C26)+(C22=C26)", donc si une condition entre ses parenthèses est vrai, cela vaut 1, faux = 0. On fait cela pour tous vos contraintes. Ceux en ligne 14-15, je les &i mais en gris, parce que ce sont des conditions moins importantes. Dans la cage H1, on fait la somme de tous les contraintes violés, ceux en noir comptent pour 1, ceux en gris ont un poids de 0,1 (parce qu'ils sont moins importants). Le but, c'est que tous les contraintes sont respecté, donc H1=0 !!!

L'année prochain, vous changez, si nécessaire, les chiffres dans la plage verte et vous modifiez (=ajouter/supprimer) les formules en colonnes I:L et la formule de H1 (somme des contraintes importants avec poids 1 + somme des contraintes supplémentaires avec poids 0,1)

Puis on exécute la macro, mais cela ne se voit pas tout le temps sur l'écran. On commence avec la plage C2:F29 vide et on ajoute aléatoire 7 des 576 grilles4x4 et puis aléatoire on remplace un des 7 blocs 4x4 avec un nouvelle grille4x4. Le nombre de contraintes violés se voit en cage H1 et le numéro du boucle en G1, les violations sont en oranges. Le but est donc H1=0 et je prevois au maximum 25.000 boucles (= 1 minute sur mon ordinateur). Si la solution est valable (=0), elle sera copié et collé vers la feuille "solutions". Donc, plus tard, vous aurez le luxe du choix entre plusieurs solutions.

Comme on ne connait pas d'avance vos contraintes, on ne sait pas anticiper, donc le choix de la prochaine grille dans chaque boucle est complètement aléatoire. Le nombre de boucles et le temps est donc aussi complètement aléatoire.

C'est claire ?

Merci beaucoup !

C'est relativement clair, sauf le paragraphe où vous écrivez "Puis on exécute la macro, mais cela ne se voit pas tout le temps sur l'écran. On commence avec la plage C2:F29 vide et on ajoute aléatoire 7 des 576 grilles4x4 et puis aléatoire on remplace un des 7 blocs 4x4 avec un nouvelle grille4x4. Le nombre de contraintes violés se voit en cage H1 et le numéro du boucle en G1, les violations sont en oranges. Le but est donc H1=0 et je prevois au maximum 25.000 boucles (= 1 minute sur mon ordinateur). Si la solution est valable (=0), elle sera copié et collé vers la feuille "solutions". Donc, plus tard, vous aurez le luxe du choix entre plusieurs solutions.".

Quelques questions / remarques :

- J'ai essayé le raccourci ctrl+shift+N, mais ça me répond encore la même chose... J'ai l'impression que les grilles de l'onglet solutions restent les mêmes quand j'exécute la macro, et la case H1 reste toujours à 0,0. Lorsque je clique sur "déboguer", la ligne surlignée en jaune dans la macro est "Set Dict = CreateObject("scripting.dictionary")".

- j'ai l'impression que vous n'avez pas mis dans les contraintes les égalités de cellules qui devaient être imposées. Comment puis-je les rajouter ? J'ai compris comment vous avez réussi à imposer que des cellules soient non-égales (avec le fait que les formules doivent renvoyer 0), mais comment puis-je ajouter que des cellules doivent être égales ?

J'imagine qu'en rajoutant ces égalités, le nombre de solutions va sensiblement diminuer...

- Pour votre programme, doit-on, comme pour celui de Optimix, avoir déjà une grille de départ qui fonctionne ?

- A quoi sert la grille A1:F29 dans l'onglet Feuille1 ?

- Que signifie la grille verte dans les colonnes Q:T ?

- Pourquoi les cellules D6 et E6 sont-elles toujours égales à 3 et 1 ? Ces valeurs n'étaient pas censées être fixées. Comment puis-je faire pour "dé-fixer" des cellules dont la valeur a été fixée ? Et à l'inverse, comment avez-vous fait pour fixer les cellules en vert ?

- En I6 vous avez écrit "=(C7=C11)+(C7=C21)+(C11=C24)" , au lieu de (je pense) : "=(C7=C11)+(C7=C21)+(C11=C21)". (idem sur les colonnes J,K,L)

- En I7 vous avez écrit "=(C6=C10)+(C6=C16)". Pourquoi pas, comme sur les autres : "=(C6=C10)+(C6=C16)+(C10=C16)" ?

Merci pour ce super boulot !

re,

maintenant, la macro attend chaque boucle une seconde pour que vous savez mieux suivre, mais comme je lis vos remarques, je pense que la macro n'a jamais été exécuté. Est-ce que vous voyez maintenant des changement sur l'écran ?

pour des égalité, je compte les violations, donc la formule doit montrer des inégalités, voir ligne 17, =N(C2<>C6) (ce N sert ici pour traduire un Vrai/Faux en 1/0)

Le grille de départ est toujours vide. La plage C2:F29 est la plage où on travaille , la plage Q:T sont pour les données fixe, comme vous voulez les lignes 22, 25, 26 & 29. j'avais aussi ajouter les cellules R6:S6 avec les valeurs 3&1, de manière que D6:E6 ont obligatoirement les valeurs 3&1, mais je pense que vous n'aviez pas compris mon explication, ici dessus.

Les formules en I6:M7, c'est vrai, la ligne 6 est 7 doivent s'échanger et la ligne 7 manque la 3ième inegalité.

Bon, vous voyez des mouvement sur l'écran quand vous lancez la macro ou cela reste bloqué sur cette ligne du "dictionairy"

Si cela est le cas, voulez-vous retourner le fichier (donc le mien que vous avez ouvrié et après sauvegardé) que vous utilisez, parce que je ne comprend pas la blocage.

G1, c'est le numéro du boucle, une sorte de pédomètre.

edit : nouveau fichier à 18:00

Bonsoir

je viens de comprendre : le problème vient du fait que je faisais tourner la macro sur un mac. J'ai essayé sur mon pc portable et ça marche !

Par contre, c'est vraiment lent, j'en suis à 1000 et ça tourne depuis 10 minutes... mais bon, c'est déjà super satisfaisant comme solution !! Je suis très impressionné, vraiment bravo.

Je vais retoucher les contraintes pour rajouter toutes les égalités qu'il faut, je pense avoir compris comment faire.

Petite question : puis-je écrire dans les cases de la grille A1:F29 des formules ? Par exemple : dans E28 écrire "=C24" afin que ces deux cellules soient tout le temps égales, ou bien suis-je obligé de passer par l'écriture des contraintes dans les colonnes I:L sous la forme =N(E28<>C24) ou encore =(E28<>C24)+(F28<>D24) ?

Et deuxième petite question : je n'ai pas bien compris si je dois supprimer manuellement le contenu de la feuille "Solutions" à chaque fois que je relance la macro ... ?

re,

comme je n'étais pas sûr que cela fonctionnait chez vous, j'avais ajouté des pauses de 0.5 sec. Maintenant, ils sont enlevés. Mais 1.000 boucles en 10 minutes ? Mon PC fait 50.000 boucles en 2 minutes, espérons que c'est beaucoup mieux maintenant.

J'ai peur des égalités, cela risque de ne pas trouver une solution, c'est peut-être mieux si 2 cellules sont égales, de les fixer avec le même valeur dans la plage verte.

En VBA, comme première ligne en module 1, vous voyez "Const Max_Boucles = 50000", vous pouvez modifier cela en 100000 par exemple, pour augmenter le nombre de boucles avant de rompre la série avec une solution invalide.

La plage C2:F29 est la plage où la macro écrit ses grilles, donc vos formules sont supprimées, dès que la macro se lance, donc c'est option 2 avec les formules en colonnes I:L.

Ces solutions de la feuille "Solutions", vous les effacez quand vous avez modifiez quelque chose à vos contraintes, donc par exemple l'année prochaine. Le but est d'avoir là, plusieurs solutions valides et de vous donner le choix ... . Si vous n'utilisez pas cette feuille, ce n'est pas grave.

PS. en dessous votre écran, on a le "statusbar" d'Excel dans lequel vous pouvez voir le progrès de la macro (le pédomètre.avec intervalle de 1.000)

PS2. Quand vous résolvez ce puzzle manuellement, comment faites-vous, la logique ? Ma solution est avec "force brute", mais vos égalités nécessitent peut-être une approche plus intelligente

PS3. Le problème du Active_X, c'était aussi du à votre MAC. Je n'ai pas d'éxperience avec.

Re,

"J'ai peur des égalités, cela risque de ne pas trouver une solution, c'est peut-être mieux si 2 cellules sont égales, de les fixer avec le même valeur dans la plage verte." => Je ne connais pas d'avance la valeur des cellules qui doivent être égales, mais je sais qu'elles doivent être égales. En toute logique, vu que j'ai trouvé une solution à la main, la macro devrait trouver une solution, non ?

"En VBA, comme première ligne en module 1, vous voyez "Const Max_Boucles = 50000", vous pouvez modifier cela en 100000 par exemple, pour augmenter le nombre de boucles avant de rompre la série avec une solution invalide." => Je suis désolé, je crois que je n'ai pas vraiment compris ce que vous appelez une "boucle" ...

"Ces solutions de la feuille "Solutions", vous les effacez quand vous avez modifiez quelque chose à vos contraintes, donc par exemple l'année prochaine. Le but est d'avoir là, plusieurs solutions valides et de vous donner le choix ... . Si vous n'utilisez pas cette feuille, ce n'est pas grave." => Là je dois justement modifier les contraintes, puisque je dois ajouter les égalités de cellules. Mais comment j'efface ? Avec la touche suppr, afin de laisser les grilles mais d'effacer juste les valeurs ou alors je supprime carrément les grilles car la macro va en créer de nouvelles ?

Je n'ai pas encore essayé le dernier fichier, je l'essaye et je vous dis.

Manuellement, j'ai procédé comme suit :

Mes lignes 22,25,26,29 étant fixées, je démarre avec les lignes 24 et 28. Comme C24=E28 alors c'est forcément la valeur 2. Etc. Normalement sur les 2 blocs inférieurs nous n'avons qu'une solution.

Puis je pars sur les modules 5/4 (lignes 14 à 21). Je m'intéresse aux cellules (C16 ; D16) et (C17 ; D17) car maths et SVT sont les plus contraignants. J'ai 16 possibilités. Je me rends vite compte que les combinaisons du genre (1 ; 2) (2 ; 1) ou (1 ; 4) (4 ; 1) amènent à un blocage. J'ai aussi essayé (1 ; 2) (2 ; 3) et (1 ; 2) (4 ; 1) qui bloquent rapidement. Puis j'ai essayé (1 ; 2) (4 ; 3) qui m'a permis d'avancer. (Je ne sais pas si d'autres possibilités m'auraient aussi permis de finaliser la grille, ou si j'ai eu de la chance ...). A ce stade, je peux donc facilement finir entièrement les lignes 16 et 17.

Je ne finis pas les modules 5/4, je passe aux 6/5 pour le moment. Je regarde les maths (lignes 6 et 10) en n'oubliant pas que E10=C6, F10=D6, E6=C10 et F6=D10. Deux possibilités : soit (2431 ; 3124) , soit (2134 ; 3421). J'ai choisi la première (pareil, je ne sais pas si avec l'autre possibilité, j'aurais abouti à quelque chose...).

On n'a plus le choix pour les lignes 9 et 13, on peut les remplir.

Ensuite, il faut remplir C7 et C8. J'ai choisi C7=1 et C8=4. Idem, je ne sais pas à quoi le contraire m'aurait mené...

A ce stade, les lignes 6 à 13 peuvent être entièrement remplies.

Je reviens sur les modules 5/4, sur les cellules C14 et D14. Il y a 4 possibilités (21 ; 24 ; 31 ; 34). J'ai choisi C14=2 et D14=1. Encore une fois, je ne sais pas ce qu'auraient donné les autres possibilités...Je remplis donc les lignes 14 et 18.

Ensuite, j'ai dû choisir de sacrifier l'une des contraintes peu importante : soit j'avais deux fois SVT avec musique, soit deux fois photo avec école, soit une fois l'un une fois l'autre. J'ai choisi de garder SVT/musique sur deux périodes.

Il ne reste plus qu'à remplir les lignes 2 à 5. Je remplis (C2 ; D2) (C3 ; D3). A nouveau j'ai 16 possibilités. J'ai choisi (1 ; 2) (2 ; 1). La suite en découle et m'a permis de finir.

re,

bloc 6&7 ont chaqu'un 2 solutions, donc 4 possibilités !

effacer les colonnes en feuilles "solutions", le plus facile & rapide, c'est de sélectionner les colonnes et de les effacer complètement. Je vous prepare une macro, la prochaine version !

Il y a zéro % d'intelligence dans ma façon de résoudre le problème, c'est "force brute", toujours changer une grille de 4x4 est vérifier si le résultat est mieux que la version précédente. Si la macro a de la chance, on a une solution après 20 éssais/boucles, mais cela peut aussi prendre plus de temps. Pour qu'excel ne calcule pas pour l'éternité, cela s'arrête après par exemple 50.000 ou 100.000 essais/boucles. Avec cela, on a un outil pour anticiper.

Votre façon de résoudre, c'est bien pour cette année, mais l'année prochaine, elle peut être différent, non ?

Non cette façon de résoudre fonctionne toujours, c’est comme cela qu’on procède tous les ans. Et ça fonctionne même si ça demande un gros boulot d’essais/erreurs (d’où mon envie d’automatiser le processus).

Pour les blocs 6 et 7 non il n’y a bien qu’une seule solution car vous n’avez pas tenu compte des égalités de cellules (C24=E28, D24=F28, E24=C28 et F24=D28).

Toutes ces égalités sont dans mon fichier de départ que je vous avais envoyé, sous forme de formules dans les cellules (toutes celles qui affichent 0).

re,

alors, dès le début ces inégalités étaient des égalités ??? + ligne 8

Non non, pas du tout. Ces contraintes que j'ai écrites sont bien des interdictions d'égalité !

Ce sont d'autres cellules qui doivent être égales. Regardez dans mon premier fichier, dans les cellules elles-mêmes qui affichent un 0.

Je vais essayer d'écrire les bonnes formules pour compléter votre fichier et de vous le renvoyer.

Voilà votre fichier que j'ai modifié avec les contraintes d'égalité.

Par contre j'ai effacé les colonnes dans l'onglet "solutions" mais aucune nouvelle grille n'y est apparu...

Je fais tourner la macro (plus rapide en effet !!!), il y a quelques moments de "blocage", mais ça tourne bel et bien, c'est top ! Mais au final je ne sais où recueillir les grilles qui donnent 0 dans la grosse cellule jaune ...? Elles sont censées apparaitre dans l'onglet solutions ?

La macro s'est finie, en un temps tout à fait raisonnable (environ 200 s), par contre, elle n'a trouvé aucune solution... J'ai même essayé en enlevant les contraintes non obligatoires et il ne trouve toujours aucune solution. Or, il en existe bien, puisque j'en ai trouvé une. C'est bizarre...

Peut-être les formules que j'ai rajoutées sont-elles mal écrites ?