[Jeu d'échecs] Le problème des huit dames

[jo_le_coco]

Bonjour à tous :we:

Je suis en lycée mais je pense que ma question va porter sur des notions post-bac.

C'est en fait pour un TPE sur les échecs, j'ai voulu démontrer que le problème des huit dames admettait 92 solutions.

Le problème des huit dames consiste à placer huit dames sur un échiquier de 64 cases de telle sorte qu'aucune ne menace l'autre.


Mais je me suis vite perdu, et je ne sais pas du tout où m'orienter.

A tout hasard, j'ai trouvé une petite formule qui donnait le nombre de cases contrôlées pour une dame placée sur la ligne i et la colonne j (pour i et j inférieurs ou égaux à 4) :

(Si i supérieur à 4, on le remplace par 9-i, et de même pour j.)

J'ai aussi mis sous forme mathématique les contraintes du problème. Si x et y sont deux dames distinctes, alors :







Est-ce que quelqu'un connaîtrait une démonstration ou aurait une idée ?


Merci de vos réponses :happy3:

[fahr451]

ça doit être trivial si Gauss y a travaillé des années...

[jo_le_coco]

Si dûr que ça ? :hein: :triste:

[fahr451]

ben Gauss on a bien dit Gauss ...( cependant merci pour cette question que je ne connaissais pas )

[yos]

Je crois que c'est 92 aux symétries et quart de tours près.
Tu peux chercher le problème avec huit tours déjà. Ca te donnera 40320 possibilités au total. Tu peux en enlever beaucoup par symétrie et rotation. Mais pour finir, il faut un programme informatique (banal d'ailleurs mais compte pas sur moi pour l'écrire). Ou un raisonnement qui dépassera presque à coup sûr le niveau lycée.

[fahr451]

ça revient à chercher les permutations f de [1,8] telles que f-id et f+id soient injectives.

[jo_le_coco]

Je crois que c'est 92 aux symétries et quart de tours près.
Tu peux chercher le problème avec huit tours déjà. Ca te donnera 40320 possibilités au total. Tu peux en enlever beaucoup par symétrie et rotation. Mais pour finir, il faut un programme informatique (banal d'ailleurs mais compte pas sur moi pour l'écrire). Ou un raisonnement qui dépassera presque à coup sûr le niveau lycée.

En fait c'est 12 solutions "uniques" desquelles peuvent se déduire 92 en tout (grâce aux isométries du carré).

Pour les tours c'est plus simple, puisqu'il y a si je ne m'abuse 8! possibilités.

J'ai aussi pensé à faire un programme informatique pour créer une telle position, mais c'est loin d'être un grand défi, il suffit d'y aller à la "brute force".

ça revient à chercher les permutations f de [1,8] telles que f-id et f+id soient injectives.

Euh c'est-à-dire ? :doh:

Sinon où est-ce qu'on pourrait trouver cette démonstration de Gauss ??


Merci encore.

[jo_le_coco]

Bon finalement, je me suis tourné vers le problème des huit tours, c'est plus simple. J'ai donc 8! différentes solutions à ce problème.

Mais comment peut-on calculer le nombre de solutions uniques ?

Je suppose que diviser par 8 (c'est-à-dire par le nombre d'isométries du carré, si j'ai bien compris) ne suffit pas, puisque par exemple si toutes les tours sont alignées sur la grande diagonale, la symétrie centrale n'y changera rien, et donc à partir d'une solution unique on n'a pas forcément 8 solutions.

Voilà, quelqu'un pourrait-il m'aiguiller ? :help:

[jo_le_coco]

:hein: Personne ? :triste:

[yos]

Essaie avec des échiquiers plus petits 1X1, 2X2, 3X3, ... nXn.
En plus ça te définit une suite.

[jo_le_coco]

Merci, je vais essayer et vous tiendrai au courant :we:

[B_J]

salut
programme maple
http://perso.orange.fr/virgile.prevosto/2000-2001/TP7/exo4.html