Remplissage d’une grille pseudo-aléatoire sous contraintes type sudoku
Dans l'exemple que vous nous avez donné, il n'y a qu'une seule solution pour les groupes 6 et 7. Je pensais que c'était acquis.
Démo :
Hypothèse 1 : C23 = 2
Hypothèse 2 : C23 = 3
Hypothèse 1 :
C23 = 2
E23 = 4
C28 = 2 impossible puisque C26 = 2
donc C23 = 3
C24 = 2
F23 = 1
D28 = 3
D27 = 2
E27 = 4
C27 = 1
C28 = 4
D24 = 1
F27 = 3
D23 = 4
E23 = 2
Attention : dans une autre configuration pour les lignes 22, 25, 26 et 29, il peut y avoir plusieurs solutions.
Si les valeurs de ces 4 lignes sont variables, le problème n'est plus du tout le même.
@optimix : je confirme, c'est bien ce que j'ai écrit ce matin dans mon message de 10h30 : "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."
On est d'accord sur ce point, même si .
Cela dit, il y a une chose que je ne comprends pas : chaque année ces 4 lignes sont susceptibles de changer. Pourquoi en avoir fait des constantes ?
En fait, elles sont fixées d'office avant de commencer à réfléchir à la rotation, en fonction des thèmes que les élèves ont déjà fait ou pas fait (il y a ces 4 lignes pour les années paires, et d'autres valeurs pour ces 4 lignes pour les années impaires). Du coup, ces valeurs font partie des contraintes, au même titre que les contraintes d'égalité ou de non-égalité de cellules...
bonjour optimix, nonoparadox,
non, je 'arrive pas à trouver une solution
Vous avez trouvé une à la main, laquelle ?
Bonjour BsAlv. Tu en as une en page 1 (rotations-modules-resolus...xlsx).
Je vous transfère de nouveau le fichier
bon, je garde le silence
vous ne voyez pas pourquoi la macro n'a pas donné cette solution ?
re,
j'avais dit, il n'y a pas d'intelligence dans la macro, c'est avec du force brute qu'on échange une grille 4x4 par une autre et si cet échange est mieux que le précédent, on le garde. A cause de ces nouvelles égalités, cette méthode ne fonctionne plus, peut-être avec 2 grilles en même temps, mais ... .
De toute façon, la méthode d'Optimix, que je salue, vous donne une solution.
Bonjour,
Une proposition qui calcule 6 variantes à partir d'une même solution. Je pense qu'avec 6 on devrait pouvoir tenir une année. Si ce n'est pas le cas, ce sera à mettre à la poubelle.
Oh merci ça a l'air génial ! Donc si j'ai bien compris, il faut que je trouve au préalable une grille qui soit correcte (doit-elle répondre à toutes les conditions ? Car celle que j'ai trouvée a laissé de côté l'une des contraintes "non indispensable" ... ça marche quand même ?).
Je lance le bouton... par contre, est-ce une erreur de frappe en ligne 14 dans l'onglet spécimen ?
Ah j'ai l'impression que comme j'ai le même numéro en SVT et musique en périodes 1 et 2 (C17 et C20, ainsi que D17 et D20) dans ma proposition de départ, ça reste forcément comme ça dans les nouvelles propositions ? Ça ne me permettra pas de vérifier s'il y a une grille "meilleure" que celle que j'ai trouvée ?
Edit : à première vue, j'obtiens une solution 1 qui ne respecte pas la première contrainte D16<>D22<>D26 (car D16=D22)
Pouvez-vous nous donner la solution que vous avez utilisée ?
La solution que votre programme m’a donnée ?
Effectivement, iI ne vous a pas donné grand-chose
Effectivement, alors je ne vois pas de solution avec les permutations.
@ Optimix, effectivement les permutations, cela ne fonctionne pas, parce que dans quelques instants vous verrez qu'il n'y a qu'une solution pour bloc4.
Bon, ce que j'ai fait, c'est de nouveau sans intelligence et avec du force brute essayer toutes les possibilité (=576 grilles de 4x4) dans les 5 blocs, donc une sorte d'arbre avec autant de branches et des branches latérales. Pour cela, j'ai récrit les formules en colonnes W:Z (plage bleu), de telle manière qu'elles ne regardent que des cellules non-vides. Dès qu'il y a une contrainte violée, on arrête avec cette branche. J'avais commencé avec bloc3, puis 2, 1, 4 et 5, en regardant le nombre de contraintes par bloc (=éliminer aussi vite que possible des branches). Hier soir, j'avais posté la première solution et pendant la nuit, mon ordinateur avec fait le reste, je ne savais pas combien de solutions cela pouvait créer ou le temps nécessaire.
Les 576 grilles4x4 se trouvent dans la feuille "blad2", l'une à côté de l'autre, A1:D4 a index 0, E1:H4 a index 1, ... .
Les solutions se trouvent en colonnes BB:BF et le moment où le PC a trouvé cette solution en colonne BG.
Bon, le résultat ce matin, le temps nécessaire pour tout faire était 6.300 sec (1 3/4 heure) et cela a donné 40 solutions et si on regarde le temps en colonne BG, il y a 8 blocs des quelque secondes et chaque bloc donne 5 solutions, vos permutations ????
Ces 40 solutions se trouvent maintenant dans la feuille "Solutions". Remarquable, il n'y a qu'une solution pou bloc 4 !!! Pour bloc 5 = 2 solutions.
Les 2 macros pour ces solutions se trouvent dans la module2
Si quelqu'un se sent le courage de vérifier ce dernier essai : j'ai trouvé un bug dans une précédente proposition.
BsAlv : je vais regarder cette conclusion (1 seule solution pour le bloc 4 alors que j'en ai 24