NQueens Project

Trouver toutes les solutions au problème des N-Dames de N=18 jusqu'à N=26 (record mondial)

INSCRIPTION

Télécharger BOINC (tutorial)

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

Système d'exploitation : Linux, Windows

• 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 :

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 8x8 : Problème des huit dames

Les buts du projet NQueens

Ce projet a pour but de trouver toutes les solutions au problème des N dames, en partant de N=19. Placer 19 dames sur un échiquier 19x19 cases, sans qu'aucune des dames du jeu ne puisse prendre une autre dame, autrement dit sans qu'aucune des 19 dames ne soit sur la même ligne, la même colonne ou sur la même diagonale que l'une des 18 dames restantes.

Les responsables du projet espèrent battre le record mondial qui est actuellement de N=25. Le projet est actuellement dans une étape de développement et les résultats seront publics.

A partir de N=23, le projet devrait être assez mûr pour le considérer comme stable.

Contexte

Le problème des huit dames

Le problème des huit dames consiste à placer huit dames sur un échiquier de tel sorte qu'aucune des 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 tel sorte qu'aucun d'entre eux ne partage une même ligne, colonne ou diagonale.

On sait depuis longtemps qu'il existe 92 solutions au problème. Sur ces 92 solutions, on compte 12 modèles distincts. La totalité des 92 solutions peuvent être transformées en l'un des ces 12 modèles uniques par l'utilisation de la rotation ou de la réflection.

Extension du problème à N dames et un échiquier NxN

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 existantes pour chacune des valeurs de N. Par exemple, si N=10, il y aura 724 solutions dont 92 distinctes.

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 :

Je ne connais aucun projet qui tente de résoudre le problème N=26

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

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.

Calcul

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++

Vos commentaires (0)