Répartition uniforme de cases sur damier
Bonjour !
Nouvellement inscrit sur le forum, j'aurai voulu vous faire part d'un problème que je n'arrive pas à résoudre.
J'aurais besoin de repartir sur un damier 10 par 10, dix cases coloriés de la manière la plus uniforme possible. Le seul souci que j'ai c'est de respecter la "loi du sudoku" autrement dit ne mettre qu'une case coloriée par ligne et par colonne.
Le must aurait été d'obtenir la meilleure combinaison réduisant un maximum l’écart type de la distance entre chaque case coloriée !
Voilà, si vous avez des pistes de réflexion n'hésitez pas à répondre
Cordialement
Sooflette
Nouvellement inscrit sur le forum, j'aurai voulu vous faire part d'un problème que je n'arrive pas à résoudre.
J'aurais besoin de repartir sur un damier 10 par 10, dix cases coloriés de la manière la plus uniforme possible. Le seul souci que j'ai c'est de respecter la "loi du sudoku" autrement dit ne mettre qu'une case coloriée par ligne et par colonne.
Le must aurait été d'obtenir la meilleure combinaison réduisant un maximum l’écart type de la distance entre chaque case coloriée !
Voilà, si vous avez des pistes de réflexion n'hésitez pas à répondre
Cordialement
Sooflette
Réponses
-
s'agit-il de penser à votre place?
S -
Non pas du tout, c'est pour ca que je demande seulement des pistes de réflexion ;o)
J'ai quelques notions, j'ai fait quelques essais (en utilisant par exemple le principe des cercles inscrits) mais j'aurai voulu avoir l'avis de personnes un peu plus douées que moi dans la maitrise de la géométrie ou dans les lois de répartition. -
Bonjour et bienvenue sur le forum !
J'ai l'intuition que l'écart type sera minimal lorsque les cases coloriées sont toutes sur une même diagonale du damier.
Sinon, pour obtenir une position, tu peux raisonner colonne par colonne.
Tu places la première case coloriée n'importe où sur la premiè colonne. Puis, tu t'occupes de placer la deuxième case sur la deuxième, en évitant de la placer sur la même ligne que la première case coloriée. Et ainsi de suite. Je ne sais pas si cela t'aidera pour ton problème. -
Bonjour Sooflette.
La principale difficulté de ta question est de définir la notion de "uniforme" dans " de la manière la plus uniforme possible". de le définir de façon à pouvoir effectivement comparer deux répartitions. Quelle est ta définition (*) ?
Cordialement.
(*) Si tu n'en as pas, il n'y a pas non plus de question. Pas encore ... -
Oui toto le zero, j'ai commencé par faire comme ca ! Mais je voulais savoir si la solution optimale pouvait être obtenue à l'aide de l'informatique par exemple
Sinon gerard, j'entends par uniforme une répartition qui visuellement occuperait l'ensemble de mon damier (on aurait alors l'impression que toutes les cases sont à égales distances les unes des autres). La diagonale respecte le principe du sudoku mais laisse beaucoup "d'espaces vides" sur ma grille.
Sooflette -
Bonjour,
Avec un jeu d'échecs, il y a un problème bien connu qui constite à placer huit dames sur l'échiquier (8x8) de sorte que pour toute paire choisie parmi ces huit dames, les deux dames ne se menacent pas:
Problème des huit dames.
La contrainte est plus forte que celle du sudoku...
Les solutions présentent des dames assez joliment équiréparties. Peut-être peux-tu partir d'une telle solution et la compléter pour un 10 x10...
Pour équiréparties, on pourrait proposer la définition suivante : le min des distances doit être le plus grand possible, qu'en penses-tu?
Amicalement. jacquot -
Bonjour et bienvenue,
Pour un échiquier n x n avec n dames, il y a ici un algorithme pour les placer, mais je n'ai pas l'impression qu'il fonctionne pour l'echiquier 10 x 10: http://www.apprendre-en-ligne.net/auteur/articles/ndames.pdf
Quel est l'énoncé exact ? ou alors, est-ce un énoncé à toi ?
Amicalement. -
Comprends rien. Je mets $n$ au lieu de 10. S'agit de fabriquer une matrice $(n,n)$ de 0,1 avec un seul 1 par ligne et colonne exactement, autrement dit une matrice de permutation: si l'unique 1 de la ligne $i$ est sur la colonne $\sigma (i)$ alors $\sigma$ est une des $n!$ permutations de $\{1,\ldots,n\}.$ Mais ce que tu veux minimiser n'est pas clair du tout: si c'est la somme des carrés des distances entre toutes les paires de points, c'est \`a dire $\sum_{i,j}\|(i,\sigma(i))-(j,\sigma(j)\|^2$ j'ai bien peur que ca ne dépende pas de $\sigma.$
-
Merci jacquot et BS pour ces liens qui me renseigne un peu plus sur le problème (même beaucoup plus).
Nan BS, l'énoncé est de moi-même.
Et oui jacquot c'est une bonne définition de équiréparties.
Je vais donc essayer de programmer algorithme et vous tiens au courant !
Cordialement,
Sooflette -
Bonjour,
Avec la définition de jacquot, voilà ce que j'obtiens avec Maple, pour $n$ compris entre $1$ et $10$ :
$$\begin{pmatrix}X\end{pmatrix}$$
$$\begin{pmatrix}X&.\\.&X\end{pmatrix}$$
$$\begin{pmatrix}X&.&.\\.&X&.\\.&.&X\end{pmatrix}$$
$$\begin{pmatrix}.&.&X&.\\X&.&.&.\\.&.&.&X\\.&X&.&.\end{pmatrix}$$
$$\begin{pmatrix}X&.&.&.&.\\.&.&.&X&.\\.&X&.&.&.\\.&.&.&.&X\\.&.&X&.&.\end{pmatrix}$$
$$\begin{pmatrix}X&.&.&.&.&.\\.&.&.&X&.&.\\.&X&.&.&.&.\\.&.&.&.&X&.\\.&.&X&.&.&.\\.&.&.&.&.&X\end{pmatrix}$$
$$\begin{pmatrix}.&.&X&.&.&.&.\\.&.&.&.&.&X&.\\X&.&.&.&.&.&.\\.&.&.&X&.&.&.\\.&.&.&.&.&.&X\\.&X&.&.&.&.&.\\.&.&.&.&X&.&.\end{pmatrix}$$
$$\begin{pmatrix}X&.&.&.&.&.&.&.\\.&.&.&X&.&.&.&.\\.&.&.&.&.&.&X&.\\.&X&.&.&.&.&.&.\\.&.&.&.&X&.&.&.
\\.&.&.&.&.&.&.&X\\.&.&X&.&.&.&.&.\\.&.&.&.&.&X&.&.\end{pmatrix}$$
$$\begin{pmatrix}.&.&.&.&.&.&X&.&.\\.&.&.&X&.&.&.&.&.\\X&.&.&.&.&.&.&.&.\\.&.&.&.&.&.&.&X&.\\.&.&.&.&X&.&.&.&.\\.&X&.&.&.&.&.&.&.\\.&.&.&.&.&.&.&.&X\\.&.&.&.&.&X&.&.&.\\.&.&X&.&.&.&.&.&.\end{pmatrix}$$
$$\begin{pmatrix}X&.&.&.&.&.&.&.&.&.\\.&.&.&.&.&.&.&X&.&.\\.&.&.&.&X&.&.&.&.&.\\.&X&.&.&.&.&.&.&.&.\\.&.&.&.&.&.&.&.&X&.\\.&.&.&.&.&X&.&.&.&.\\.&.&X&.&.&.&.&.&.&.\\.&.&.&.&.&.&.&.&.&X\\.&.&.&.&.&.&X&.&.&.\\.&.&.&X&.&.&.&.&.&.\end{pmatrix}$$ -
Bonjour,
Ce qui est recherché, c'est un carré latin.
Routines disponibles en R et Matlab par exemple.
Rajouter une contrainte d'uniformité sans trop la définir complique un peu les choses.
En pratique pour les plans d'expériences, on recherche des carrés latins avec une bonne distance maximin entre les points.
Une solution : générer un gros paquet de carrés latins aléatoirement, et choisir celui qui a la meilleure distance.
C'est ce qui est fait dans la routine Matlab (lhsdesign) que je mentionnais, avec l'option 'maximin'.
Amicalement,
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 23
+14 Invités