Inscription / Connexion Nouveau Sujet
Niveau énigmes
Partager :

Détente chez les Dames

Posté par
Imod
10-05-20 à 11:32

Bonjour à tous .

Un problème facile ( blankage obligatoire ) .  

Tout le monde connait le problèmes des huit dames qu'il faut poser sur un échiquier de façon à ce qu'aucune d'entre elles en attaque une autre ( il y a pas mal de solutions ) .

Détente chez les Dames

Une petite variante : On considère des dames noires et blanches en nombre égal . On veut les disposer sur l'échiquier de façon à ce que deux dames ne s'attaquent jamais ( nous savons tous qu'il n'y a jamais d'animosité entre deux dames de la même famille ) .

Peut-on placer huit dames de chaque couleur sur l'échiquier ? Plus ?

Amusez-vous bien .

Imod

Posté par
matheuxmatou
re : Détente chez les Dames 10-05-20 à 12:04

bonjour

 Cliquez pour afficher

Posté par
Imod
re : Détente chez les Dames 10-05-20 à 12:25

Il faudrait joindre une image car là c'est un peu flou  

Imod

Posté par
ty59847
re : Détente chez les Dames 10-05-20 à 12:58

Précsion sur l'énoncé  :  de façon à ce que deux dames de la même couleur ne s'attaquent jamais.
Je pense qu'il faut ajouter 'de la même couleur', sinon c'est une copie du problème classique.
Et pour compléter : S'il y a 2 dames blanches sur les cases A1 et A8, avec une dame noire en A4 par exemple, alors c'est valide, les 2 dames blanches ne se voient pas.

Matheuxmatou : je pense que ta solution n'est pas bonne du tout.

 Cliquez pour afficher

Posté par
Imod
re : Détente chez les Dames 10-05-20 à 15:44

Je précise car je ne suis pas sûr que la consigne soit claire . Il n'y a pas d'animosité entre dames de la même couleur , c'est à dire qu'elles peuvent être en prise sans que cela pose  problème .

Imod

Posté par
littleguy
re : Détente chez les Dames 10-05-20 à 17:17

Bonjour

 Cliquez pour afficher

Posté par
matheuxmatou
re : Détente chez les Dames 10-05-20 à 17:38

Imod @ 10-05-2020 à 12:25

Il faudrait joindre une image car là c'est un peu flou  

Imod


je ne vois pas ce qui est flou dans ma proposition... je précise la couleur des dames, les lignes où je les mets et les couleurs des cases où je les mets ...

si j'ai le temps je ferai un crobard

Posté par
Imod
re : Détente chez les Dames 10-05-20 à 17:46

C'est une possibilité Littleguy , tu es définitivement très fort dans les jeux de grilles

Imod

Posté par
matheuxmatou
re : Détente chez les Dames 10-05-20 à 17:47

voilà

 Cliquez pour afficher

Posté par
matheuxmatou
re : Détente chez les Dames 10-05-20 à 17:53

ty59847 @ 10-05-2020 à 12:58


Matheuxmatou : je pense que ta solution n'est pas bonne du tout.


ah bon ?

Posté par
matheuxmatou
re : Détente chez les Dames 10-05-20 à 17:57

ty59847
je crois que tu n'as pas saisi le même problème que moi (le vrai ?) ... dans ta proposition, les dames blanches sont en prise avec une noire... donc cela ne convient pas pour moi... si j'ai bien compris le problème de Imod

Posté par
littleguy
re : Détente chez les Dames 10-05-20 à 18:10

C'est vrai que c'était un tantinet ambigu : lorsque j'ai trouvé ma disposition (un peu tordue) j'ai décidé de la soumettre, et au moment de la proposer j'ai vu que ty59847 avait écrit quelque chose.

J'ai lu le blanké (pour ne pas faire double emploi), et quand j'ai lu sa proposition  je me suis dit : "heureusement que je n'ai pas posté ma disposition, je n'ai rien compris au problème !".

Posté par
matheuxmatou
re : Détente chez les Dames 10-05-20 à 18:12

moi j'ai compris comme toi littleguy ... ta solution me semble bonne. La mienne est moins recherchée ...

Posté par
Imod
re : Détente chez les Dames 10-05-20 à 18:14

La solution de Matheuxmatou me convient .

Il est si peu clair mon problème ?

Imod

Posté par
matheuxmatou
re : Détente chez les Dames 10-05-20 à 18:14

ben non, il me semblait clair ... Imod

Posté par
Imod
re : Détente chez les Dames 10-05-20 à 18:16

Moi j'avais mis un cluster dans le coin en haut à droite ,  peut-être parce que c'est dans l'air du temps

Imod

Posté par
Imod
re : Détente chez les Dames 10-05-20 à 18:25

Pas le courage de dessiner ce soir :

 Cliquez pour afficher

On voit qu'il reste de la place pour les dames blanches

Imod

Posté par
matheuxmatou
re : Détente chez les Dames 10-05-20 à 18:34

moi je suis direct parti sur des cases de couleurs différentes pour les blanches et les noires... ça met à l'abri des attaques en diagonale

Posté par
Imod
re : Détente chez les Dames 10-05-20 à 18:42

Les attaques en diagonales , celles auxquelles on ne s'attend jamais . Mais se planquer dans un coin pour ne faire ch... personne , c'est pas mal aussi .
Imod  

Posté par
ty59847
re : Détente chez les Dames 10-05-20 à 19:18

J'avais compris autre chose dans mon premier message, et j'avais mal visualisé la proposition de matheuxmatou...

ma proposition :

 Cliquez pour afficher

Posté par
weierstrass
re : Détente chez les Dames 11-05-20 à 15:28

Après avoir trouvé beacoup de solutions (8,10), j'ai fini par ramener la parité :

 Cliquez pour afficher


Très joli problème, ce serait intéressant de trouver des bornes dans le cas général (pour n maximal avec un couple (n,n), voire toute la frontière de Pareto

Posté par
Imod
re : Détente chez les Dames 11-05-20 à 16:38

Et oui , 18 dames sur un échiquier sans prise de bec , si j'étais misogyne je dirais que ça tient du miracle

La généralisation ne doit pas être évidente .

Imod

Posté par
weierstrass
re : Détente chez les Dames 11-05-20 à 17:01

En généralisant la proposition de Matheuxmathou, on trouve facilement une borne inférieure de Ent(n^2/8) (pour le plus grand n tel qu'il existe une solution (n,n))

Trouver une bonne borne supérieure est plus coriace, mais je pense qu'il doit être possible d'obtenir un équivalent asymptotique

Trouver la valeur exacte est je pense très dur (je doute même que l'on trouve une formule close, mais après tout, pourquoi pas....)

Posté par
LittleFox
re : Détente chez les Dames 12-05-20 à 11:46


Ça a pris quelques temps avant que ce programme ne sorte une solution avec 9 reines blanches et 9 reines noires sur un échiquier 8x8 mais il a finit par trouver plusieurs solutions (438 pour l'instant mais les solutions symétriques sont comptées).

Par exemple:

 Cliquez pour afficher


 Cliquez pour afficher


Première fois que j'utilise l'expression "yield from" et première fois que j'entends parler des coroutines en python. Ça a l'air sympa et pourtant obscur

Question: comment éliminer les solutions symétriques efficacement? Par exemple une symétrie est qu'on peut inverser les couleurs sans changer la solution. Une manière efficace est par exemple d'imposer que la première reine dans le sens de lecture soit blanche. Quid des autres symétries?

Posté par
weierstrass
re : Détente chez les Dames 12-05-20 à 13:39

Bravo LittleFox!
As tu cherché des solutions (10,9) voire (10,10)?
J'ai pas encore regardé le code, mais plutôt que de placer dames noires et blanches je chercherais juste à placer les dames blanches en comptant le nombres de cases restantes libres pour des dames noires.
En combinant avec un backtracking quand le nombre de places disponibles est insuffisant. Ça a l'avantage de ne pas prendre en paramètre le nombre de dames que l'on souhaite placer, et je pense que c'est beaucoup mieux en terme de performance.

Pour briser les symétries du groupe dihédral (engendré par les symétries du carré), on peut imposer que l'ordre lexicographique du placement des dames soit supérieur ou égal à celui lu dans les 7 autres orientations possibles. Pour émonder le plus rapidement possible il faudrait remplir le carré en faisant une sorte de spirale, jusqu'à temps que l'on ait définitivement l'ordre lexicographique le plus grand dans le sens naturel.
Je ne sais pas si c'est très clair, je peux essayer de faire un schéma.
Pour briser les symétries liées au dames noires, il suffit de retirer du compte des cases libres celle qui sont situées avant la première dame blanche. (donc à partir du moment ou on place la première dame blanche, et que l'on sait qu'il y en aura pas d'autre après, on peut considérer toutes les cases avant comme attaquées par des dames blanches (même si ce n'est pas le cas).

Perso, je testerai bien tout ça, et aussi des techniques classiques d'optimisation, comme la programmation par contrainte ou la programmation linéaire, mais je ne sais pas quand j'aurais le temps de faire ça...

Posté par
LittleFox
re : Détente chez les Dames 12-05-20 à 15:12


Après un peu plus de deux heures de calcul, j'ai trouvé 1136 façons de placer 9 reines de chaque couleur sur un échiquier standard sans que l'une n'attaque l'autre. En tenant compte des 16 symétries (2 couleurs, 4 rotations et une symétrie axiale) je compte 71 solutions:

 Cliquez pour afficher


Les positions sont numérotées de 0 à 63 dans le sens de lecture et une solution est représentée par la position des 18 dames ordonnées blanche,  noire, blanche, noire, ...

Pour générer les différentes symétries et comparer les solutions j'ai utilisé le code suivant:

 Cliquez pour afficher


@weierstrass
Je n'ai pas encore cherché les solutions pour (10, 9) et la suite. D'ailleurs, pourquoi ne pas commencer par (9,10) ? Je voudrais d'abord montrer qu'il n'y a pas de (8, 10) mais ça va prendre du temps.
Pour l'instant le nombre de reines maximal tel qu'il y ait une solution sur un échiquier nxn est:
n       0   1   2   3   4   5   6   7   8
reines  0   0   0   1   2   4   5   7   9?


Il me semblait qu'en plaçant blanche-noire-blanche-noire, j'avais plus vite des contraintes qui me permettent de détecter lse impasses plus vite et de backtracker. Mais je me trompe peut-être.
Il me semble aussi que ça demande moins de calcul de connaitre les lignes, colonnes et diagonales attaquées que de maintenir toutes les cases non-attaquées.

L'idée de spirale est pas mal, il va falloir que j'y réfléchisse

Posté par
weierstrass
re : Détente chez les Dames 12-05-20 à 16:36

On sait déjà qu'il y a des solutions (8,10) (voir le dernier message de ty59847)
Je pense même qu'il y en a plus que des (9,9)....

Certes, avec blanches-noires, tu vas avoir des impasses plus vite, mais ton espace de recherche est beaucoup beaucoup plus grand.
Je pense clairement qu'on gagne beaucoup à tirer partie de la propriété que les noires sont placées sur toutes les cases non attaquées par des blanches.
Après, il y a peut-être moyen de tirer aussi partie de ton idée, en essayant de voir si le placement d'une noire aboutit à une impossibilité (et dans ce cas, on peut retirer cette case du compte des dames noires) mais je doute que ça élague beaucoup l'arbre de branchement...


Pour la spirale, à voir, l'idée importante est surtout l'ordre lexicographique, après réflexion, je ne suis pas absolument sûr que commencer à placer en spirale soit beaucoup plus efficace, mais après, le seul moyen d'être vraiment sûr est de tester...

Posté par
LittleFox
re : Détente chez les Dames 12-05-20 à 16:37


Pour ce qui est des échiquiers plus grand que 8x8 j'ai obtenu des solutions pour un nombre de reine:

n       8   9   10  11  12  13  14  15  16
reines  9?  12? 12? 16? 18? 21? 22? 29? 32?


Ce qui n'empêche pas qu'il y ait des solutions avec plus de reines, simplement mon programme n'en a pas trouvé en quelques minutes.

Le programme aime bien trouver des solutions du type :

B---B---B---B---
--N---N---N---N-
B---B---B---B---
--N---N---N---N-
B---B---B---B---
--N---N---N---N-
B---B---B---B---
--N---N---N---N-

Posté par
Imod
re : Détente chez les Dames 12-05-20 à 17:44

En tout cas la série ne figure pas dans OEIS , ce n'est pas complètement surprenant .

Imod

Posté par
weierstrass
re : Détente chez les Dames 12-05-20 à 18:09

Ca m'étonne qu'elle ne soit pas dans OEIS, le problème est particulièrement élégant et OEIS m'a souvent surpris. Je pense que l'on a pas encore trouvé toutes les valeurs optimales pour celles données par LittleFox, à suivre...

Posté par
littleguy
re : Détente chez les Dames 12-05-20 à 22:12

Vu ceci dans OEIS  pour un échiquier 12x12 et 21 dames pour chaque couleur !  

Détente chez les Dames

Posté par
weierstrass
re : Détente chez les Dames 12-05-20 à 23:24

J'ai écrit un programme linéaire, qui m'a prouvé en 450s qu'il n'y a pas de solutions (10,10)
J'ai pas la réponse pour (10,9), ma modélisation ne force à maximiser qu'une seule des deux couleurs, la seconde devant juste posséder plus de pions que la première.
Après, je fait mes calculs sur un vieil ordi portable (> 6ans), et qui à l'époque n'était déjà pas fulgurant. Je vais essayer sur un meilleur ordi, mais il me faudra un peu de temps pour mettre un solveur dessus.
Je vous dit demain ce que j'arrive à prouver...

littleguy, tu as un lien?

Posté par
weierstrass
re : Détente chez les Dames 12-05-20 à 23:33

Ah, j'ai trouvé :

Posté par
LittleFox
re : Détente chez les Dames 13-05-20 à 11:01


Ah voilà, ça m'aurait étonné aussi qu'il n'y ait pas ce résultat sur l'oeis

Par contre weierstrass, il y a bien des solutions pour (n,q)=(10,10). D'après l'oeis, il y a 380 solutions pour (10,14). Il suffit donc de retirer 4 reines de chaque couleur de d'une de ces solutions pour avoir une solution (10,10).

Mon programme trouve très rapidement des milliers de solutions pour (10,10).
En voici une :

 Cliquez pour afficher

Posté par
weierstrass
re : Détente chez les Dames 13-05-20 à 11:07

Euh, j'ai fait le calcul sur un 8x8, et là il n'y a pas de solutions (10,10) d'après l'OEIS...

Posté par
weierstrass
re : Détente chez les Dames 13-05-20 à 11:08

Pour moi, (10,10) veut dire 10 dans chaque couleur, je pense que l'on n'est juste pas sur les mêmes notations...

Posté par
Imod
re : Détente chez les Dames 13-05-20 à 11:09

Je vous laisse faire joujou avec vos ordinateurs

La généralisation est vraiment complexe . J'aime beaucoup la disposition des dames dans le damier 12X12 de Littleguy .

Imod

Posté par
LittleFox
re : Détente chez les Dames 13-05-20 à 11:18

weierstrass @ 13-05-2020 à 11:08

Pour moi, (10,10) veut dire 10 dans chaque couleur, je pense que l'on n'est juste pas sur les mêmes notations...


Ah, effectivement. Autant pour moi

Posté par
Imod
re : Détente chez les Dames 13-05-20 à 11:38

"Au temps pour moi" , j'ai aussi du mal à m'y faire

Imod

Posté par
LittleFox
re : Détente chez les Dames 15-05-20 à 09:25


Pourquoi s'y faire si la graphie "Autant pour moi" est devenue courante?
Dans le sens: "Je reconnais mes erreurs et j'en prends autant pour moi."

Je ne suis pas soldat après tout

Posté par
Imod
re : Détente chez les Dames 15-05-20 à 11:22

Je rappelais la règle , après tu en fais ce que tu veux

Moi j'adore mettre une espace avant une chaque virgule parce que je trouve ça joli , je reçois régulièrement de sympathiques messages me rappelant que ce n'est pas bien mais je continue sans aucun complexe

Subséquemment , je ne suis pas le caporal Casse-Pompon .

Imod

Posté par
littleguy
re : Détente chez les Dames 15-05-20 à 19:00

Perso je préfère "sans complexe aucun" à "sans aucun complexe"

Mais bon c'était juste pour dire bonjour.



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 !