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.
J'ai écris ce petit programme en ECLiPSe :
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
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
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
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)
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)n²) 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).
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!!!???
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.
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.
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.
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).
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).
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :