Inscription / Connexion Nouveau Sujet
Niveau exercices
Partager :

Un carré magique assez compliqué ...

Posté par
vham
09-06-20 à 17:54

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 !

Posté par
dpi
re : Un carré magique assez compliqué ... 10-06-20 à 17:54

Bonjour wham

L'astuce s'est de faire attention aux lignes vertes et de compléter tranquilement
sur les autres.

Une de mes solutions:

 Cliquez pour afficher

Posté par
derny
re : Un carré magique assez compliqué ... 10-06-20 à 18:14

Bonjour
Quel est le lien de ce site ? Où son adresse exacte ou complète ?

Posté par
carpediem
re : Un carré magique assez compliqué ... 10-06-20 à 18:21

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]

Posté par
derny
re : Un carré magique assez compliqué ... 10-06-20 à 18:35

Oui j'avais pas vu "jeux" sur ce site.

Posté par
dpi
re : Un carré magique assez compliqué ... 10-06-20 à 18:50

Je m'en tenais aux flèches verticales visibles.
C'est moins évident avec les sournoises

Posté par
dpi
re : Un carré magique assez compliqué ... 10-06-20 à 18:57

Bonne surprise en donnant la réponse qui  ne convient pas à derny,
la grille d'origine me dit "félicitations !"

Posté par
carpediem
re : Un carré magique assez compliqué ... 10-06-20 à 19:07

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é !!!

Posté par
littleguy
re : Un carré magique assez compliqué ... 10-06-20 à 20:38

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 :

Un carré magique assez compliqué ...

Il m'a été répondu :

Un carré magique assez compliqué ...

Et quand on lui de mande sa solution il donne :

Un carré magique assez compliqué ...

Ce qui est beaucoup plus sérieux !

Posté par
derny
re : Un carré magique assez compliqué ... 10-06-20 à 23:21

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.

Posté par
dpi
re : Un carré magique assez compliqué ... 11-06-20 à 07:55

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 .

Un carré magique assez compliqué ...

Posté par
vham
re : Un carré magique assez compliqué ... 11-06-20 à 09:36

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....

Posté par
vham
re : Un carré magique assez compliqué ... 11-06-20 à 09:39

Que ce soit     Au lieu de ce " que ce choit " imposé par ce malencontreux correcteur automatique

Posté par
vham
re : Un carré magique assez compliqué ... 11-06-20 à 09:45

Avec de nouvelles idées de comparaisons je vais essayer de persévérer...

Posté par
weierstrass
re : Un carré magique assez compliqué ... 11-06-20 à 11:38

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

Posté par
weierstrass
re : Un carré magique assez compliqué ... 11-06-20 à 15:17

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 │
└——┴——┴——┴——┴——┴——┴——┘

Posté par
vham
re : Un carré magique assez compliqué ... 11-06-20 à 16:58

Bonjour,

Bravo, pouvez-vous exposer votre méthode en quelques lignes.... ?

Posté par
weierstrass
re : Un carré magique assez compliqué ... 11-06-20 à 17:46

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...

Posté par
derny
re : Un carré magique assez compliqué ... 11-06-20 à 18:26

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 ?

Posté par
weierstrass
re : Un carré magique assez compliqué ... 11-06-20 à 18:44

Citation :
D'abord, comment détermines-tu que la somme des 4 cases au milieu des bords fait 22 ?

Ah mais je ne vais pas vous l'offrir sur un plateau, il faut trouver
Un indice :
 Cliquez pour afficher


En vrai, la combinatoire est pas énorme, un simple backtracking avec les bonnes contraintes doit en venir à bout rapidement...

Posté par
dpi
re : Un carré magique assez compliqué ... 12-06-20 à 07:46

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

Posté par
vham
re : Un carré magique assez compliqué ... 15-06-20 à 16:57

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) :

Un carré magique assez compliqué ...

Posté par
derny
re : Un carré magique assez compliqué ... 19-06-20 à 09:50

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 ?

Posté par
vham
re : Un carré magique assez compliqué ... 20-06-20 à 12:54

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.

Posté par
vham
re : Un carré magique assez compliqué ... 21-06-20 à 14:03

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

Posté par
dpi
re : Un carré magique assez compliqué ... 22-06-20 à 07:51

Pour rester dans le sens de l'histoire ,l'ordi a validé ma première (inexacte ) réponse

Posté par
derny
re : Un carré magique assez compliqué ... 22-06-20 à 08:48

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 ?

Posté par
vham
re : Un carré magique assez compliqué ... 22-06-20 à 10:31

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

Posté par
derny
re : Un carré magique assez compliqué ... 22-06-20 à 12:27

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é.

Posté par
vham
re : Un carré magique assez compliqué ... 22-06-20 à 14:28

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.

Posté par
derny
re : Un carré magique assez compliqué ... 22-06-20 à 18:08

Encore merci
Etonnant qu'il y ait encore 7 solutions avec 45.

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !