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 ) .
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
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.
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
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
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 !".
moi j'ai compris comme toi littleguy ... ta solution me semble bonne. La mienne est moins recherchée ...
Moi j'avais mis un cluster dans le coin en haut à droite , peut-être parce que c'est dans l'air du temps
Imod
Pas le courage de dessiner ce soir :
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
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
J'avais compris autre chose dans mon premier message, et j'avais mal visualisé la proposition de matheuxmatou...
ma proposition :
Après avoir trouvé beacoup de solutions (8,10), j'ai fini par ramener la parité :
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
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....)
Ç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:
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...
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:
n 0 1 2 3 4 5 6 7 8
reines 0 0 0 1 2 4 5 7 9?
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...
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?
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-
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...
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?
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 :
Pour moi, (10,10) veut dire 10 dans chaque couleur, je pense que l'on n'est juste pas sur les mêmes notations...
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
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
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
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :