Discussion :

[Neitsa]

Bonjour à tous,

Je suis un peu ennuyé, je n'arrive pas à trouver un moyen de résoudre un carré d'un type un peu spécial (non magique) sans bruteforcer chaque nombre.

voilà le type du carré (en sachant q'un nombre est forcément compris entre 1 et 10) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
+-Grille------+-lignes----------------+-Colonnes------------+-Diagonales---+
|  a b c d e  |  ligne 0 = a+b+c+d+e  |  Col 0 = a+f+k+p+u  |  Diagonale1  |
|  f g h i j  |  ligne 1 = f+g+h+i+j  |  Col 1 = b+g+l+q+v  |  = a+g+m+s+y |
|  k l m n o  |  ligne 2 = k+l+m+n+o  |  Col 2 = c+h+m+r+w  |              |
|  p q r s t  |  ligne 3 = p+q+r+s+t  |  Col 3 = d+i+n+s+x  |  Diagonale2  |
|  u v w x y  |  ligne 4 = u+v+w+x+y  |  Col 4 = e+j+o+t+y  |  = u+q+m+i+e |
+-------------+-----------------------+---------------------+--------------+

je ne dispose que de ces sommes :

somme ligne 0 = 32
somme ligne 1 = 27
somme ligne 2 = 26
somme ligne 3 = 17
somme ligne 4 = 43
--------------
somme colonne 0 = 24
somme colonne 1 = 27
somme colonne 2 = 25
somme colonne 3 = 32
somme colonne 4 = 37
--------------
somme diagonale 1 = 28
--------------
somme diagonale 2 = 29
--------------

Est il possible de résoudre ce type de carré sans la méthode du "trial and error" (essai et erreur) ?

la méthode du pivot de gauss est elle applicable ?

Merci à vous.

Neitsa.

[khayyam90]

bien le bonsoir,

à priori, la méthode du pivot de gauss est applicable.
mais avec des restrictions:

tu as 25 inconnues pour seulement 12 équations. Les solutions trouvées seraient donc exprimées en fonction de 13 autres inconnues secondaires, qu'il te faudra ensuite trouver pour obtenir les valeurs fixes de tes a...y

Dois-tu résoudre ce problème en nombres entiers ? auquel cas le pivot de gauss ne s'avèrerait pas réellement efficace.

Ce problème a l'air suffisamment complexe pour qu'il soit intéressant de ne pas tenter de le résoudre que par des méthodes exactes. Les méthodes approchées ont aussi leurs avantages ...

[Neitsa]

Bonsoir,

Merci pour ta réponse khayyam90.

Dois-tu résoudre ce problème en nombres entiers ?

Je dois effectivement donner une réponse numérique correspondant à chaque lettre. Jusqu'à maintenant j'ai réussi mais en "bruteforcant" chaque possibilité (bruteforce relativement court puisque chaque nombre ne va que de 1 à 10).

Il faudrait que j'arrive à trouver un moyen plus "élégant" (ou plus "mathématique") d'arriver à mes fins.

De plus j'ignore si un tel carré à de multiples réponses possibles. Et vu que c'est dans l'optique d'un jeu sur un internet, le carré est généré aléatoirement et je ne dispose que de 3 secondes pour prendre les résultats des sommes des colonnes, lignes et diagonales et envoyer la réponse au serveur...

Mon niveau en matématiques étant relativement bas je n'entrevois aucune solution possible autre que celle évoquée...(essayer toute les possibilités afin d'en trouver une bonne).

Merci à vous.

[Matthieu Brucher]

Peut-être en essayant avec les moindres carrées ? Tu essaies de minimiser la somme des carrés des erreurs des équations. En revanche, je ne suis pas sûr que ça t'apporte la solution entière que tu recherches

[Charlemagne]

Je vois pas de solution mathématique, mais une recherche systématique complete peut être evitée en élagant l'arbre des essais. Tu as peut-être déjà utilisé cette idée dans ton implémentation actuelle?

Je crois pas qu'il soit possible de résoudre de tels problèmes mathématiquement, j'avais lu un article sur un cube magique (5x5x5 je crois) dont la solution venait tout juste d'être trouvée par des mathématiciens à coup d'ordinateur et d'algorithmes très sofistiqués.

C'est un peu comme ça que fonctionne l'algorithme pour résoudre le problème des 8 dames sur un échiquier (trouver toutes les possibilités de placer 8 dames sans qu'aucune ne se menace). Tester toutes les combinaisons demanderait 2^64=1.84E19 essais. Donc on élague.

Quelque petites idées dans ton cas:
- le 5eme chiffre d'une ligne/colonne/diagonale est fixé par les quatres autres, ce qui réduit le nombre de combinaisons à (4x4)^10 plutôt que (5x5)^10
-Après avoir choisi une première ligne potentielle, choisir la première colonne. Ca permet de réutiliser une valeur de la première ligne et de gagner ainsi un facteur 10 pour le nombre d'essais.
-Après avoir choisi une 1ere ligne et une première colonne potentielles, essayer de transférer le problème sur un carré 4x4. Les tests de validité seront ainsi plus rapides à calculer.
-si la somme des 3 chiffres d'une ligne/colonne/diagonale est éloignée de plus de 20 de la somme totale, pas la peine de continuer sur cette voie.
-si comme pour les carrés magiques tu dois utiliser chaque nombre de 1 à 25 une fois seulement, on peut rayer d'une liste les éléments déjà utilisés.
...

[Neitsa]

Bonsoir,

Merci à tous.

Effectivement j'ai implémenté une fonction de force brute en C++ qui me donne le bon résultat (enfin le premier qui tombe juste) mais pour l'instant cela prend encore trop de temps.


Il faut que je continu en utilisant les idées évoquées par Charlemagne concernant la réduction du champs des possibilités, moins j'en aurais à tester, plus ca ira vite.

Miles : je ne connais pas cette possibilité, je vais y jeter un oeil pour voir si cela peut m'aider. Merci pour cette proposition.

Je vous dis un grand merci à tous, je crois que tout le reste n'est plus que "codage" et optimisation. Un problème relativement simple comme celui ci est un vrai casse tête à coder

Merci beaucoup pour vos réponses

Amicalement Neitsa.

[phlip]

Les dix premières équations ( sommes sur les lignes et sur les colonnes ) constituent un problème de flux maximal entre une source et un puits, qui est efficacement résolu par beaucoup d'algorithmes (le plus simple et le plus connu est Ford-Fulkerson).

On associe un noeud à chaque ligne, notés H1 à H5, et un noeud à chaque colonne, noté V1 à V5.

ainsi a est le flux allant de H1 à V1.

On a deux noeuds supplémentaires dans le graphe, notés S (la source) et T (le puits).

les capacités max de Hi à Vj sont très grands (infinis), mettons 1000.
les capacités max de S à Hi et de Vj à T sont donnés par l'énoncé.
la capacité max de S à H1, par exemple, est 32.
la capacitéux max de V1 à T, par exemple, est 24.

La résolution de ce pb de flux max donne, par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
       V1     V2     V3     V4     V5
H1     24     8
H2            19     8
H3                   17     9
H4                          17
H5                          6      37

Il est alors possible de modifier cette solution par des transformations qui gardent invariantes les sommes sur les lignes et sur les colonnes, mais changent les sommes sur les deux diagonnales qui nous intéressent.

ces transformations sont de trois ordres:

-1- les tranferts inter diagonale, qui ajoutent à une diagonale une valeur V et otent cette même valeur à l'autre diagonale.

-2- les transferts intra diagonale, qui ajoutent à une diagonale une valeur V extraite hors des deux diagonales.

-3- les transferts extra diagonale, qui otent à une diagonale une valeur V ajoutée hors des deux diagonales.

on obtient ainsi, après un transfert inter-diagonales:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
       V1     V2     V3     V4     V5
H1     12     8                    12
H2            19     8                          
H3                   17     9             
H4                          17          
H5     12                   6      25

et après quelques transferts supplémentaires, on a une solution:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
       V1     V2     V3     V4     V5
H1     10     10                   12
H2     2      5      20                         
H3            12     5      9             
H4                                 17  
H5     12                   23     8

Je ne pense pas les douzes équations puissent être modélisées par un problème de flux, mais si quelqu'un peut me montrer le contraire, c'est avec plaisir que je le lirais.

[Neitsa]

Merci beaucoup Phlip pour cet présentation d'algo de flux

Je ne connaissais ni d'ève ni d'Adam et c'est vraiment très intéressant.

Je suis tout de même un peu bloqué au moment des échanges entre diagonales sur mon code (car la limite de chaque nombre est entre 1 et 10) et la redistribution de l'excédent d'une diagonale sur d'autres n'est pas chose aisée.

C'est même assez problèmatique puisque certaines redistributions entrainent des effets de cascades sur d'autres diagonales qui changeront d'autres diagonales etc. => effet boule de neige.

Il faudrait que j'arrive à "amortir" la redistribution entre diagonales pour que l'effet se "tasse" ou se stabilise au plus vite.

Mais je vais persévérer, je ne désèpère pas !

Merci beaucoup pour cette aide

[cboun94]

salut tout le monde,

Je me demandais si la PPC (Programmation Par Contrainte) ne serai pas plus simple qu'un algo complexe.

L'avantage c'est que l'adaptation du probleme au modèle d'entrée d'un moteur de PPC est assez facile a exprimer dans la mesure où ici, c'est tout simplement l'ennoncé.

http://gprolog.inria.fr