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)

4 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
  3. Plus, find out tips about the way to|tips on how to} play totally different versions of the game from live to European roulette. Games with this online roulette wheel include a home edge of seven.69%. By comparison, the single zero and double zero titles out there in} at 2.70% and 5.27%, respectively. As such, bet365 knowledgeable players avoid this version since the that} odds of hitting a successful quantity are additional reduced. Forget going to a on line casino, put poker chips on the enjoying in} mat that shows the chances for each roulette combo, then turn the roulette wheel.

    RépondreSupprimer
  4. The following diagram demonstrates the different bets out there. If may have} questions, the Roulette sellers or floor personnel will be pleased to help. From Texas Hold ‘Em to Omaha High-Low, Hollywood Casino Toledo is shuffling to deal out the best stakes around. Join the celebration 온라인 카지노 of recent slots at Hollywood Casino Toledo. You’ll find extra titles, extra bonus rounds and extra reasons to cheer! Try your luck on 30 new video games like Ocean Magic Grand or Dancing Foo.

    RépondreSupprimer