NQueens@Home (beendet)
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
 NQueens
| |
|---|---|
| Name | NQueens |
| Kategorie | Schach |
| Ziel | Lösen des nxn Damenproblems für n>25 |
| Kommerziell | nein |
| Homepage | nqueens.ing.udec.cl |
| Dieses Projekt wird in Chile durchgeführt. |
|
Fakultät für Ingenieurwissenschaften Universität Concepción, Chile |
Projektstatus
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
| Windows | ||
| Linux | ||
| Linux 64bit | ||
| DOS |
| |
| BSD | ||
| Solaris | ||
| Java (betriebssystemunabhängig) |
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
- 16.11.2007: 5.20 (Windows, Linux, Linux 64bit)
- 07.09.2007: 5.10 (Windows)
Work unit-Namen
Die Namen der work units sind folgendermaßen aufgebaut:
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
