Bonjour,
Par curiosité je suis allé voir dans la rubrique "jeux" du site
"Le carré magique assez compliqué ..." me parait peu accessible
même en écrivant un programme sur un PC "maison"
Y-a-t'il plusieurs solutions ? qui a déjà essayé ? quel en est l'auteur ?
peut-être ne suis-je pas assez courageux pour aboutir !
Bonjour wham
L'astuce s'est de faire attention aux lignes vertes et de compléter tranquilement
sur les autres.
Une de mes solutions:
salut
dpi :sauf que c'est faux car si tu regardes bien les lignes et les colonnes ne contenant aucun nombre au départ ne doivent contenir qu'une seule fois la suite 1234567 : les flèches sur les lignes sont à peine lisibles ... mais lisibles !!!
derny : [lien]
Bonne surprise en donnant la réponse qui ne convient pas à derny,
la grille d'origine me dit "félicitations !"
ha bon !!! pourtant si tu regardes bien les lignes vierges la première et dernière mini-cellule contient un "caca" vert
et si tu regardes une solution c'est bien vérifié !!!
Bonjour,
J'ai l'impression qu'on peut faire un peu n'importe quoi...
J'ai mis des chiffres complètement au hasard, et j'ai soumis mon résultat : il m'a été répondu "Non, 2+4+5+4+7+3+2+7 vaut 34 et non pas 26". J'ai fait en sorte que ça donne 26. et j'ai soumis ma réponse. Sans doute satisfait il est passé au suivant et Il m'a été répondu : "Non, 5+3+3+1+3+5+4+3 vaut 27 et non pas 35". Et de proche en proche j'ai rectifié, et en moins d'une minute j'ai proposé ma réponse :
Il m'a été répondu :
Et quand on lui de mande sa solution il donne :
Ce qui est beaucoup plus sérieux !
Voir qu'une réponse est fausse est facile. Je ne comprends pas "le correcteur" qui ne vérifie que les 9 chiffres grisés.
Trouver une autre bonne solution est moins facile.
Mon avis:
Les flèches vertes horizontales ont été volontairement masquées par le poseur,
je ne suis pas donc plus royaliste que le roi .
Bonjour,
Je vois bien 4 flèches vertes horizontales comme les 4 verticales...
Un programme de recherche, que ce choit case après case ou en utilisant les 5040 permutations mémorisées, ou en mémorisant un ou des résultats intermédiaires me conduit à des temps d'exécution ou à des fichiers ultra conséquents.
Je n'ai pas réussi à avancer....
Bon, je crois qu'effectivement il va falloir utiliser l'informatique pour trouver l'ensemble des solutions (type backtracking, programmation par contrainte ou programmation linéaire.)
J'ai quand même trouvé une contrainte assez forte (mais bien insuffisante) :
La somme des 4 cases au milieu des bords fait 22
Par programmation linéaire, j'obtiens d'autres solutions, par exemple :
┌——┬——┬——┬——┬——┬——┬——┐
│1 │6 │2 │7 │3 │4 │5 │
├——┼——┼——┼——┼——┼——┼——┤
│7 │26│1 │35│7 │37│4 │
├——┼——┼——┼——┼——┼——┼——┤
│2 │3 │4 │5 │6 │7 │1 │
├——┼——┼——┼——┼——┼——┼——┤
│6 │31│3 │36│5 │39│7 │
├——┼——┼——┼——┼——┼——┼——┤
│5 │1 │7 │2 │4 │3 │6 │
├——┼——┼——┼——┼——┼——┼——┤
│3 │38│5 │29│2 │26│2 │
├——┼——┼——┼——┼——┼——┼——┤
│4 │7 │6 │2 │1 │5 │3 │
└——┴——┴——┴——┴——┴——┴——┘
La programmation linéaire est un cas particulier de programmation par contrainte. On modélise le problème à l'aide de variables et de contraintes, et les solutions sont cherchées par des méthodes arborescentes très poussées. Dans le cas de la programmation linéaire, les contraintes doivent être linéaire. Dans ce cas, on peut utiliser l'algorithme du simplexe pour trouver une approximation (au lieu que les variables soient imposées entières, elles peuvent être réelles). A partir de cette approximation, il est généralement plus facile de trouver des solutions réalisables. De plus cette approximation permet de gagner du temps dans la partie arborescence en réduisant de beaucoup l'espace de recherche.
Ici, j'ai introduit des variables binaires x[i,j,k] valant 0 si la valeur aux coordonnées (i,j) vaut k, et 1 sinon.
Ensuite, je modélise de manière assez classique, par exemple :
une case ne peut contenir qu'une seule valeur : x[1,1,1] + x[1,1,2] + ... + x[1,17] <= 1
Une ligne contient toujours un 1 :
x[1,1,1] + x[2,1,1] + x[3,1,1] + ... + x[7,1,1] = 1
Les égalités autour des cellules :
1*x[1,1,1] + 2*x[1,1,2] + ... + 7*x[1,1,7]
+ 1*x[1,2,1] + 2*x[1,2,2] + ... + 7*x[1,2,7]
+ ...
+ 1*x[2,1,1] + 2*x[2,1,2] + ... + 7*x[2,1,7] = 26
Je peux ensuite rentrer cette modélisation dans un solveur (CPLEX, Gurobi pour les plus connus ... ) qui recherche des solutions. Ces solveurs ont bénéficié pendant des années de nombreuses optimisations et sont très efficaces pour résoudre ce genre de problèmes... C'est assez difficile de décrire en deux mots comment ça fonctionne, pour en savoir plus, voir algorithme du simplexe et branch and cut.
Ce n'est cependant pas forcément le meilleur choix de techniques, je soupçonne la programmation par contrainte classique d'être plus efficace dans ce cas, mais je connais un peu moins...
Bien Weierstrass. Je n'ai pas essayé de résoudre mais je ne comprends pas grand chose à tes explications (c'est loin de mon Basic). D'abord, comment détermines-tu que la somme des 4 cases au milieu des bords fait 22 ?
La seule explication de l'acceptation par l'ordi de me réponse (injuste) est que pour
faciliter le jeu ,le poseur ait masqué le flèches vertes horizontales
Bonjour,
d'abord Merci à weierstrass de m'avoir ouvert le domaine de la programmation par contraintes que je ne connaissais pas.
Je me suis décidé à aboutir et j'ai finalement développé un programme en VB.net assez simple (mais assez long )
qui me donne des milliers de solutions : plus de 2500 en 4 secondes
et avec la possibilité de choisir une ou plusieurs des permutations horizontalement ou Verticalement.
Pour exemple, obtenu quasi instantanément (Voir la dernière ligne des grilles 7x7) :
Bonjour
Je reviens sur ce problème. Cela démontre encore une fois que l'ordinateur est "irremplaçable" pour certaines tâches. Trouver une solution "à la main" est quasi impossible alors qu'il en existe des milliers.
Bien sûr j'ai trouvé pourquoi les 4 cases au milieu des bords font 22. Mais, malgré les contraintes imposées mon programme Basic a mis plusieurs heures avant de sortir les premières solutions. Je suis donc en "admiration" d'un programme qui les sort en 4 secondes. vham peux-tu afficher ton programme ?
Bonjour,
---> derny. C'est un programme en VisualBasic.net assez long en 3 parties, chacune dédiée à 1/3 horizontal du carré et exécutées successivement.
Il commence par construire une table des permutations des 7 chiffres (5040 rangées par ordre numérique). Ce qui permet de limiter les domaines de comparaisons itérées.
Pour chaque partie on choisit (ou on reporte) une des permutations et on itèrera pour la seconde permutation en vérifiant les exclusions verticalement puis les sommes.
C'est du code adapté à cette recherche systématique qui ne fait aucun appel de procédure autre que les 3 entrées dans chaque 1/3 du carré : d'où la rapidité de ce code spécifique.
Il n'y a donc pas de modélisation des contraintes qui seraient soumises à un Solveur existant.
bonjour,
"
il y a 182610 solutions pour ce "carré magique assez compliqué"
Quantité obtenue par un programme en VB.net (compilé) en moins de 20 minutes
Bonjour
vham, puisque tu as un logiciel performant pour résoudre ce carré pourrais-tu changer 39 en 40 et voir s'il y a des solutions ?
Bonjour,
Quasi instantanément
3 6 2 7 5 1 4
4 26 1 35 7 37 6
2 5 3 4 6 7 1
5 31 7 36 3 40 7
1 2 6 3 4 7 5
7 38 4 29 2 26 2
6 7 5 4 1 2 3
3 4 2 7 6 5 1
4 26 4 35 4 37 6
2 6 1 4 7 5 3
5 31 7 36 5 41 7
1 3 6 4 2 7 5
7 38 5 29 3 26 2
6 7 3 5 1 2 4
Merci vham
J'imagine qu'avec 40 on a moins de solutions qu'avec 39 et qu'avec 41 encore moins. 42 me parait inatteignable. Il faudrait alors augmenter une des autres valeurs pour que le nombre de solutions tende vers l'unité et donc vers la difficulté.
Bonjour,
Si 39 est remplacé
par 40 78620 solutions obtenues en 13 minutes
par 45 7 solutions obtenues en 7 minutes
par 46 0 solution obtenu en 6 minutes
Le temps pour explorer la totalité diminue car il y a plus de rejets très tôt
Mon programme utilise intensivement des AndAlso : quand il y a beaucoup de contraintes à tester successivement dans if... AND ....AND.....then, le AndAlso dégage dès qu'une des conditions testée est fausse. Cela contribue bien à diminuer les temps d'exécution du programme.
Si vous programmez en Basic , pensez à Visual Basic gratuit, je l'utilise beaucoup en mode console.
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :