Site inaccessible depuis le 12 Décembre 2009. Le tremblement de terre au mois de Février aura eu raison du projet.
Trouver toutes les solutions au problème des N-Dames pour N=26 (record mondial)
URL du projet : http://nqueens.ing.udec.cl/
|
Liens du projet
|
L'Alliance Francophone
|
Statistiques |
|
- Projet de la section informatique de la Faculté d´Ingénierie de l'Université de Concepción au Chili
Le problème des N-Dames
Le problème des N-Dames consiste à placer N dames sur un échiquier NxN sans que l'une d'elles puisse en prendre une autre (avec les règles des échecs : une dame peut prendre toute pièce située sur sa ligne, sa colonne ou sur l'une de ses deux diagonales).
Le problème peut être représenté avec N variables (V i ∈ [1..N], i=1 .. N), représentant la position en colonne de la dame de la ligne i. En effet, comme deux dames ne peuvent pas être sur la même ligne, et qu'il y a autant de dames que de lignes, il y a exactement une et une seule dame par ligne.
Les contraintes imposées sur les variables V i sont :
pour tout i ≠ j :
- V i ≠ V j (ne pas mettre deux dames sur la même colonne).
- V i - i ≠ V j - j (ne pas mettre deux dames sur la même diagonale NO-SE)
- V i + i ≠ V j + j (ne pas mettre deux dame sur la même diagonale NE-SO)
Pour plus d'information voir l'article Wikipédia qui expose le cas du problème des huit dames, placer 8 dames dans un échiquier de 8x8 cases : Problème des huit dames
Les buts du projet NQueens@home
Ce projet a pour but de trouver toutes les solutions au problème des N dames pour N=26. Ce problème consiste à placer 26 dames sur un échiquier de 26x26 cases, sans qu'aucune des dames du jeu ne puisse prendre une autre dame, autrement dit sans qu'aucune des 26 dames ne soit placée sur la même ligne, la même colonne ou sur la même diagonale que l'une des 25 autres dames placées sur le plateau du jeu.
Contexte
Le problème des huit dames
Le problème des huit dames consiste à placer huit dames sur un échiquier de telle sorte qu'aucune des 8 dames du jeu ne puisse en attaquer une autre. Une méthode alternative pour représenter ce problème consiste à placer huit pions sur une grille huit par huit de telle sorte qu'aucun d'entre eux ne partage une même ligne, colonne ou diagonale.
On sait depuis longtemps qu'il existe 92 solutions à ce problème des huit dames. Sur ces 92 solutions, on compte 12 solutions uniques. La totalité des 92 solutions peuvent être transformées en l'un des ces 12 solutions uniques par rotation ou par réflexion
Extension du problème à N dames placées sur un échiquier de NxN cases
Si nous augmentons la taille de l'échiquier au delà des 8 lignes/colonnes, il est intéressant de connaître le nombre de solutions possibles pour chacune des valeurs de N. Par exemple, si N=10, il y aura 724 solutions dont 92 uniques
 |
|
Solutions du problème des 6 dames : 4 solutions, 1 distincte
|
Connaissances actuelles
A ce jour, nous savons que pour N=25, il existe 2.207.893.435.808.352 solutions [1]. Ce résultat a été obtenu par 2 groupes de recherche indépendants :
- Par l'équipe Objectweb ProActive INRIA (proactive(AT)objectweb.org), 11 Juin 2005 [Contact :Alexandre Di Costanzo (Alexandre.Di_Costanzo(AT)sophia.inria.fr)]. Ce calcul a nécessité 53 années de calcul cumulées.
- Résultat confirmé par le projet NTU 25Queen de l'Université National de Taiwan et l'Université Ming Chuan, dirigé par Yuh-Pyng (Arping) Shieh, 26 Juillet 2005. Ce calcul a nécessité 26.613 jours de calcul cumulés.
Jusqu'à aujourd'hui, aucun autre projet n'a tenté de résoudre le problème N=26.
Les résultats du projet Nqueens@home :
|
Echiquier
|
Solutions
|
Temps
|
Echiquier
|
Solutions
|
Temps
|
|
1x1
|
1
|
14x14
|
365 596
|
1 seconde
|
|
|
2x2
|
0
|
< 0 s |
15x15
|
2 279 184
|
4 secondes
|
|
3x3
|
0
|
< 0 s |
16x16
|
14 772 512
|
23 secondes
|
|
4x4
|
2
|
< 0 s
|
17x17
|
95 815 104
|
2 minutes et 38 secondes
|
|
5x5
|
10
|
< 0 s
|
18x18
|
666 090 624
|
19 minutes et 26 secondes
|
|
6x6
|
4
|
< 0 s |
19x19
|
4 968 057 848
|
1 heure 30 minutes et 57 secondes
|
|
7x7
|
40
|
< 0 s |
20x20
|
39 029 188 884
|
11 heures 36 minutes et 10 secondes
|
|
8x8
|
92
|
< 0 s
|
21x21
|
314 666 222 712
|
4 jours 23 heures 6 minutes et 29 secondes
|
|
9x9
|
352
|
< 0 s
|
22x22
|
2 691 008 701 644
|
34 jours 16 heures 57 minutes et 20 secondes
|
|
10x10
|
724
|
< 0 s |
23x23
|
24 233 937 684 440
|
296 jours 11 heures 50 minutes et 57 secondes
|
|
11x11
|
2680
|
< 0 s |
24x24
|
226 732 487 925 864 (*)
|
9 années 261 jours 12 heures 5 minutes et 47 secondes
|
|
12x12
|
14200
|
< 0 s
|
25x25
|
2 207 893 435 808 352
|
72 années 12 heures 22 minutes et 2 secondes
|
|
13x13
|
73712
|
< 0 s
|
26x26
|
en cours de calcul
|
?
|
|
Les solutions du problème des N dames et les temps pour sa résolution sur un PC 800 Mhz et avec l'utilisation du Code J Somers [2]
|
|||||
(*) ll a été démontré que ce résultat était erroné suite à un problème dans l'application du projet
Le projet
Ce projet est une tentative pour trouver les résultats au problème des N dames par l'utilisation du cadriciel BOINC pour différentes tailles d'échiquier en débutant par N=19
Comment ?
Pour le problème des N dames, le nombre de solutions et le temps requis pour résoudre la totalité du problème augmente d'un facteur n! . Ainsi vouloir résoudre ce problème sur un PC seul révèle quasiment du marathon à partir de N=19 (voir tableau ci-dessus)
Mais, du fait de la nature du problème, c'est un candidat parfait pour la parallélisation. Ceci peut être effectué en plaçant les dames dans toutes les positions possibles de la première Colonne/ligne de l'échiquier, et alors de résoudre les problèmes. La solution du problème est la somme de toutes les solutions des sous-problèmes.
Par exemple, pour le problème des 8 dames, nous avons :
 |
 |
|
Premier sous problème après une subdivision (7x7 sous-échiquier)
|
Premier sous-problème après deux subdivisions (6x6 sous-échiquier)
|
De cette façon, on peut résoudre le problème pour un échiquier de taille N comme pour un échiquier N N-1 (Un échiquier N avec une dame déjà placée sur la première ligne/colonne). En faisant cela, le problème est assez réduit pour être calculé par un PC dans un lapse de temps raisonnable.
Les Calculs
Pour chaque échiquier, le projet envoit des unités de travail pour les premières n/2 positions de la première dame, puis le nombre de solutions doit être doublé pour obtenir la solution réelle du problème. Dans un échiquier avec un nombre n impair, le processus est similaire, calculer (n-1)/2 et pour les (n+1)/2 solutions, la seconde dame est placée uniquement dans la première moitié de l'échiquier.
Actuellement, le code utilisé sur le projet se base sur le code de Jeff Somers [2], qui a été modifié pour intégrer les sous-échiquiers, les points de sauvegarde (checkpoint), et le cadriciel BOINC.
[1] Solutions actuellement connues dans Sloane's On-Line Encyclopedia of Integer Sequences
[2] Jeff Somers, Programmeur C/C++