Layer 1

mercredi 20 juin 2012

Problème des huit dames


Le problème des huit dames consiste à placer les huit pions d'un jeu d'échec, représentants huit dames, sans qu'elles se menacent mutuellement.
Je vous propose de résoudre ce problème avec Python.
Trois versions de codes permettront de jouer avec plusieurs concepts de programmation mais aussi l'utilisation de différents modules Python.

1) La version dite "optimisée" est la transcription d'une solution au problème que l'on peut trouver ici.

2) La version "récursive" est une utilisation de la récursivité Python: On considère que les premières colonnes de l'échiquier répondent au problème posé.

3) La version dite random est une solution totalement aléatoire: On mets une dame au hasard sur l'échiquier, puis une autre aux endroits encore disponibles et ainsi de suite. Dès que l'on a pu mettre les 8 reines, on vérifie que la solution n'a pas encore été trouvée: méthode hypo-optimisée mais qui marche ! Le seul problème, mis à part le temps de traitement c'est que l'on ne sais pas si la solution trouvée est la dernière...

Etude du nombre de solutions: 

Pour un échiquier classique d'échecs 8x8, on trouve 92 solutions.


Avec le script 'dame.py) Python ci-dessous, les différents algorithmes proposés sont regroupés dans une 'classe' Python qui a comme argument le taille de l'échiquier. 
Ainsi on peut découvrir le nombre de solution pour chaque type échiquier:


2x2 = 0 solution (évidemment...)
3x3 = 0 solution
4x4 = 2 solutions
5x5 = 10 solutions
6x6 = 4 solutions (va comprendre...)
7x7 = 40 solutions
8x8 = 92 solutions
9x9 = 352 solutions
10x10 = 724 solutions
11x11 = 2680 solutions
12x12 = 14200 solutions
13x13 = 73712 solutions
14x14 = 365596 solutions

Il est à noter que le nombre de solutions pour un échiquier 5x5 comporte plus de solutions qu'un échiquier 6x6, ce qui est très surprenant... Il serait intéressant de connaître la formule "F(n)" où n est le type d'échiquier: appel aux mathématiciens!


modif-20120628 => A ce jour aucune formule (ou conjoncture probante) n'a été trouvée. Les derniers algorithmes sur ordinateur ont permis d'accéder au résultat F(n:26)=22317699616364044


0 ...
Script python dame.py (python 2.7/windows)

2 commentaires:

  1. début de réponse pour le cas général :
    http://oeis.org/A000170

    RépondreSupprimer
  2. il y a un pb a l'affichage on dirait : il affiche les solutions pour (n+2) x (n+2) au lieu de (n x n)

    RépondreSupprimer