Inscription / Connexion Nouveau Sujet
Niveau énigmes
Partager :

Carré pas magique

Posté par
jarod128
23-01-20 à 13:05

Bonjour,
je vous demande de trouver un algorithme qui prend en entrée un entier n (on pourra se limiter au cas n pair ...) et qui retourne une matrice nxn vérifiant:
pour tout i, la ième ligne et la ième colonne contient tous les entiers de 1 à 2n-1
On peut également commencer par donner de telles matrices.

 Cliquez pour afficher

Posté par
mathafou Moderateur
re : Carré pas magique 24-01-20 à 02:00

Bonjour,

bref, un carré latin ...

Posté par
mathafou Moderateur
re : Carré pas magique 24-01-20 à 02:29


ah bein non ...



Posté par
jarod128
re : Carré pas magique 30-01-20 à 19:46

Personne ?

Posté par
LittleFox
re : Carré pas magique 31-01-20 à 11:52


J'ai écris ce petit programme en ECLiPSe :

 Cliquez pour afficher


Il trouve :
n=1 : 1 solution
n=2 : 6 solutions
n=3 : 0 solutions
n=4 : 282240 solutions
n=5 : aucune solution trouvée
n=6 : beaucoup de solutions


Par exemple pour n =6 une solution est:
  1  2  3  4  5  6
  7  1  4  3  6  5
  8  9  1  5  2  7
 10 11  6  1  7  2
  9 10 11  8  1  3
 11  8 10  9  4  1


Et pour n=8:
  1  2  3  4  5  6  7  8
  9  1  4  3  6  5  8  7
 10 11  1  2  7  8  5  6
 11 10  9  1  8  7  6  5
 12 13 14 15  1  2  3  4
 13 12 15 14  9  1  4  3
 14 15 12 13 10 11  1  2
 15 14 13 12 11 10  9  1


Bizarrement pour n > 8, il ne trouve pas de solutions dans un temps raisonnable alors que pour n = 8, c'est direct. N'y aurait-il pas de solution pour n > 8?

Posté par
jarod128
re : Carré pas magique 31-01-20 à 18:42

Bonjour LittleFox
Je ne comprends pas ton programme.
Peux tu l'expliquer brièvement ?
Que donne t il pour n=16?
J'ai un programme qui fonctionne uniquement pour les puissances de 2.
Je ne sais pas pourquoi. Il est en O(n3)

Posté par
LittleFox
re : Carré pas magique 01-02-20 à 02:17


C'est de la programmation par contrainte, difficile de te donne un O de quelque chose.
On cherche une solution dans un espace O((2n+1)) en essayant de couper au plus vite les cas impossibles.  Au mieux on a un algorithme en O(n²log(n)).

Effectivement pour n=16 et n=32 il trouve vite une solution (0.14 et 2.17s).

 Cliquez pour afficher


 Cliquez pour afficher


L'algorithme peut être expliqué en français comme ceci:
Un carré de taille N est défini comme :-
   N21 est 2*N-1,
   Les dimensions du carré sont (N, N),
   Les valeurs dans le carré sont des entiers entre 1 et N21,
   Pour chaque I entre 1 et N :
      L0 est la liste des valeurs de la ligne I du carré,
      L1 est L0 plus la liste des valeurs de la colonne I du carré au dessus de la ligne I,
      L2 est L1 plus la liste des valeurs de la colonne I du carré en dessous de la ligne I,
      Les valeurs de L2 sont toutes différentes.

En gros, c'est juste la définition dans le langage EclipseCLP du carré pas magique.
Pour chaque I, L2 contient toutes les cases de la ligne I et de la colonne I.

Ensuite on utilise une commande du genre "labeling(Square)" pour trouver une solution en remplissant le carré dans l'ordre avec les nombres les plus petits d'abord. Ou bien findall(Square, labeling(Square), List) pour trouver la liste de toutes les solutions.

Posté par
jarod128
re : Carré pas magique 01-02-20 à 13:05

Merci LittleFox pour tes réponses.
J'utilise pour ma part un algo pas du tout optimisé :
Je remplis la première ligne et la première colonne.
Ensuite je complète toutes les cases manquantes dans l'ordre : ligne par ligne et dans chaque ligne colonne par colonne en procédant ainsi:
Pour remplir une case d'indice i,j je liste tout ce qui est déjà utilisé pour les lignes et colonnes indice i et j. Je prends le complément et j'ai donc une liste de possibilités. Et c'est là que ça m'impressionne : je choisis arbitrairement dans cette liste le plus petit élément a chaque fois et ça marche pour les puissances de 2. Si j'avais choisis le plus grand ça marche pas du tout!!!???

Posté par
ty59847
re : Carré pas magique 01-02-20 à 13:23

Si je comprens bien , tu dis que pour une case (i,j), tu places dans cette case le plus petit nombre compatible.  Si plus tard, ça conduit à une impasse, tu n'essayes pas de revenir sur cette case (i,j), en y mettant un autre nombre.
Et en faisant comme ça, tu trouves des solutions quand n est une puissance de 2 !
C'est presque miraculeux, mais effectivement, on voit sur le carré 32x32 pleins de carrés.
Si on regarde les éléments au dessus de la diagonale, on a plein de petits triangles avec (2,3,4) , des carrés (5,6,7,8) ... Et donc des triangles (2,3,4,5,6,7,8). Etc..

En regardant le carré de taille 8x8 en haut à droite, on voit assez bien le motif qui se dessine, et on se dit que pour toutes les puissances de 2, c'est sûr, on va trouver une solution avec le même motif.

La méthode que tu utilises n'est pas une recherche exhaustive, loin de là, mais elle va produire une solution pour toutes les valeurs de n qui sont des puissances de 2.

Par contre, pour un carré 6x6, il y a une solution, mais cette méthode ne la trouvera pas.

Posté par
jarod128
re : Carré pas magique 01-02-20 à 13:40

Je suis d'accord pour le miraculeux.
Ce que je ne comprends pas c'est pourquoi en prenant le plus grand nombre possible, il ne trouve pratiquement jamais de solutions.

Posté par
jarod128
re : Carré pas magique 01-02-20 à 13:40

J'aimerais également trouvé un algo pour n pair non puissance de 2.

Posté par
ty59847
re : Carré pas magique 01-02-20 à 14:15

On va fair la démarche avec un papier et un crayon, pour un carré 40x40 par exemple.
Il nous faut en fait un carnet avec une bonne centaines de feuilles.
On écrit la 1ère ligne ( les nombres de 1 à 40) et la 1ère colonne ( les nombres de 41 à 79)
Dans la case (2,2), on a en fait 2 possibilités. On peut écrire 1, ou 3.
On peut aussi écrire tous les autres nombres de 4 à 79, sauf 41, mais en réfléchissant un peu, on se rend comte que c'est du travail inutile. Si on met un 40 dans cette case (2, 2), ça nous emmène aux mêmes développement qu'avec un 3 dans cette case, mais en permutant les colonnes 3 et 40.
On a donc 2 feuilles quasiment identiques, avec la même chose en 1ère ligne et en 1ère colonne, et sur une des feuilles on a 1 en case (2,2) et sur l'autre feuille, on a 3 dans cette case.
On prend une de ces 2 feuilles, et on regarde quelle est la 1ère case vide. Imaginons qu'on prenne la feuille avec un 1 en case (2,2).La 1ère case disponible est en ligne 2, colonne 3, et on regarde quelles sont toutes les valeurs possibles pour cette case. On peut mettre dans cette case tous les nombres de 4 à 79, sauf 41.
La encore, pour des raisons de symétries, il y a plein de nombres qu'on pourrrait éliminer, mais on va envisager tous les nombres.
On va donc photocopier la grille actuelle  74 fois, (1 original et 74 copies) et on va mettre dans cette case (3,2) les 75 valeurs possibles.
Et on continue, on prend une des feuilles en attende, on regarde la 1ère case vide, et on fait autant de photocopies que nécessaire, pour explorer tous les scénarios.

Chaque feuille correspond en fait à un scénario.
Ici, j'ai gardé le scénario avec un 3 en case (2,2) en attente ... mais je ne l'ai pas totalement éliminé. On explorera ce scénario plus tard, si tous les autres scénarios mènent à une impasse, ou si on veut recenser toutes les solutions, et pas uniquement trouver une grille.

A la main, avec une grille 40x40, ça va etre insupportable. Mais cette démarche doit permettre de trouver toutes les solutions pour une grille 6x6.

Informatiquement, il faut procéder de la même façon : garder en mémoire chacun des scénarios. Mais selon les langages, ça peut être très différent comme implémentation.

Et il faut se débrouiller à chaque étape pour explorer les scénarios les plus avancés.

Posté par
derny
re : Carré pas magique 01-02-20 à 14:27

Bonjour. En ce moment je n'ai pas le temps d'examiner tous ces problèmes intéressants. Cependant, en voyant vos solutions, 1) pour n on a 2n-1 nombres différents, 2) il y a n nombres 1 et n/2 autres nombres. Avec ces 2 conditions, il me semble qu'on ne peut pas avoir de n impair (nxn nombres en tout).

Posté par
derny
re : Carré pas magique 01-02-20 à 14:31

Et aussi, parmi toutes les solutions, ôter les solutions symétriques ou décalées (c'est-à-dire où un nombre se substitue à un autre).

Posté par
jarod128
re : Carré pas magique 02-02-20 à 11:53

derny, j'avais bien écrit dès le départ que l'on pourra se limiter au cas n pair...

Posté par
jarod128
re : Carré pas magique 02-02-20 à 11:58

ty59847 oui cet algo est trivial mais inutilisable en pratique. J'aimerais quelque chose de bien plus optimisé.



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 !