NQueens@Home (beendet)

Aus Rechenkraft
(Weitergeleitet von Nqueens)
Wechseln zu: Navigation, Suche
Logo

Das Projekt rechnet per BOINC am Damenproblem. Es geht darum n Damen auf einem nxn-Schachbrett so zu positionieren, dass sich die Damen gegenseitig nicht bedrohen. Die genaue Anzahl der Lösungen zu jedem n wird in diesem Projekt bestimmt. Viele Lösungen entstehen auch durch Drehen und Spiegeln einer anderen Lösung, auch diese werden jedoch hier voll mitgezählt.

Das Problem ist sehr gut parallelisierbar, da man für größere n einfach kleinere Unterprobleme betrachten kann.

Werte bis n=25 waren vor Beginn des Projekts bekannt. Das Projekt startete jedoch noch einmal bei n=19 und überprüft somit nochmal die bekannten Ergebnisse. Für n=24 gab es eine kleine Diskrepanz, siehe Ergebnisse unten. Der Grund für diese wurde nach gut einem Jahr gefunden.

Wird das Brett um ein Feld erweitert, erhöht sich der Rechenaufwand grob um das Neunfache.

Es wird durchgeführt von der Universidad de Concepción in Chile.

Die Projekthomepage ist momentan nicht mehr erreichbar. Möglicherweise wurde das Projekt eingestellt. Einem deutschen Team war es im Vorhinein gelungen die Lösung für 26 Damen effizienter zu berechnen (siehe Meldungen).


Inhalt

Projektübersicht

InfoIcon.png NQueens
Name NQueens
Kategorie Schach
Ziel Lösen des nxn Damenproblems für n>25
Kommerziell   nein
Homepage nqueens.ing.udec.cl


 
Chile01.gif    Dieses Projekt wird in Chile durchgeführt.
Uni.jpg Fakultät für Ingenieurwissenschaften
Universität Concepción, Chile


Projektstatus

InfoIcon.png Projektstatus
Status   beendet
Beginn 07. Oktober 2007
Ende beendet

Projektlinks

Statistiken

Wo Übersicht Top Teams Top User
Projekt Home Page Top Teams Top User
BOINCstats.com Übersicht Top Teams Top User
BOINCsynergy.com: Der Service wurde eingestellt.
stats.free-dc.org Übersicht Top Teams Top User
allprojectstats.com: Der Service wurde eingestellt.

Clientprogramm

Betriebssysteme

Icon windows 16.png   Windows Checkbox 1.gif  
Icon linux 16.png   Linux Checkbox 1.gif  
Icon linux 16.png   Linux 64bit Checkbox 1.gif  
Icon dos 16.png   DOS Checkbox 0.gif  


Icon freebsd 16.png   BSD Checkbox 0.gif  
Icon solaris 16.png   Solaris Checkbox 0.gif  
Icon java 16.png   Java (betriebssystemunabhängig)  Checkbox 0.gif  

WU-Informationen

Aktuelle und genaue Details für BOINC-Projekte gibt es bei WUProp.

Name RAM Dauer Deadline Speicherplatz Download Upload Mindestanforderung
Nqueen@home Project 5.20  1,5 MB  bis 5 h (AMDX2 32bit 3,0 GHz)  2 Tage  MB MB MB {{{mindestanforderung}}} oder besser


Die Dauer ist die durchschnittliche Rechenzeit, die auf entsprechender CPU (Taktung in der Klammer) gebraucht wird.
Die Deadline ist die Zeitspanne, in der die Work unit berechnet sein muss.

Installation

NQueens@Home (beendet) benutzt die BOINC-Infrastruktur. Die Anmeldung, Installation und Konfiguration sind auf der allgemeinen BOINC-Seite beschrieben.


Veröffentlichte Versionen

Work unit-Namen

Die Namen der work units sind folgendermaßen aufgebaut:

Nq26_01_25_16_05_09

Hier steht Nq natürlich für NQueens. Die 26 gibt die aktuell zu berechnende Brettgröße an. Die darauffolgenden Zahlen sind die Positionen der Damen auf den ersten Spalten des Bretts. In obiger work unit steht also in der ersten Spalte ganz oben die erste Dame, in der zweiten Spalte auf dem 25. Feld von oben, in der dritten auf dem 16. Feld von oben usw. Durch die 5 festgelegten Damen berechnet man nur alle Lösungen auf dem verbleibenden 21x21-Brett.

Ergebnisse

Die berechneten Lösungen des Projekts für n=19 bis 23 stimmten mit den bisher errechneten Ergebnissen überein. Für n=24 wurde der bisher errechnete Wert nicht bestätigt, es kam eine andere Anzahl Lösungen heraus. Hierauf hin wurde das 24er Brett nocheinmal komplett berechnet und wieder derselbe Wert errechnet. Das Projekt wurde dann im Dezember 2007 für 2 Wochen ausgesetzt und der Code überprüft. Nachdem kein Fehler gefunden werden konnte, wurde ein drittes mal der eigene Wert bestätigt und man ging zur Brettgröße 25 über. Es wurde vermutet, dass der bisherige Wert falsch war (Threads im Projektforum: 1, 2), was sich allerdings später als falsch herausstellte.

Lösungen insgesamt (n=24) 227.514.171.973.736
NQueens Lösungen 226.732.487.925.864
Differenz 781.684.047.872

Am 4. Juli 2008 wurde der Wert für Brettgröße 25 errechnet. Er stimmt mit dem bisher bekannten überein. Man geht nun zu n=26 über.

Anfang November 2008 meldete ein User im Forum, dass er einen Unterwert für n=26 für sehr klein hielt. Darauf wurde festgestellt, dass es sich bei den Abweichungen um einen longint-Überlauf handelte. Eine Variable war auf 2^32 begrenzt und sprang dann wieder auf Null. Obige Differenz ist genau 182*2^32. Damit sollte sich das obige Ergebnis doch noch bestätigen lassen und man wird auch in Zukunft wieder richtige Ergebnisse erhalten.

Meldungen



Eigene Werkzeuge