NQueens Project

Site inaccessible depuis le 12 Décembre 2009. Le tremblement de terre au mois de Février aura eu raison du projet.

N-queens

Trouver toutes les solutions au problème des N-Dames pour N=26 (record mondial)

INSCRIPTION 

Télécharger BOINC (tutorial)

URL du projet : http://nqueens.ing.udec.cl/

 Progrès du projet

 

Liens du projet
L'Alliance Francophone
Statistiques

 

 

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.

Depuis son lancement, NQueens@home a déjà trouvé tle nombre de solutions possibles au problème des N-dames de N=19 jusqu'à  N=25. Une erreur est survenue lors de la résolution du problème des N-dames pour N=24. C'est ce qui explique que jusqu'à ce jour la solution trouvée par le projet Nqueens@home (226 732 487 925 864 solutions) est différente de la solution trouvée par Kenji Kise en 2004 (227 514 171 973 736 solutions)

 

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

6-Dames
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.
Ce résultat a été confirmé par le projet Nqueens@home en Juillet 2008.

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 :

7x7
6x6
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++