Sudoku@vtaiwan

Aus BC-Wiki
Version vom 19. Mai 2018, 09:58 Uhr von DoctorNow (Diskussion | Beiträge) (Code-Korrektur)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Zur Navigation springen Zur Suche springen
Für sudoku@vtaiwan haben wir neue Techniken entwickelt und genutzt um das Programm namens CHECKER (geschrieben von Gary McGuire) zu modifizieren. Wir konnte die insgesamt zu erwartene Rechenzeit erfolgreich von 300000 Jahre per CPU-Kern auf 2417 Jahre per CPU-Kern reduzieren. Das macht es durchführbar und angemessen BOINC zu nutzen das Sudoku Problem zu lösen.

Das offene Sudoku 16-Hinweis Problem in 2417 Jahren pro CPU-Kern lösen

Sudoku ist eines der populärsten Spiele heutzutage. Eine wichtige Frage die Forscher fesselt ist, welches ist die kleinste Anzahl von Hinweisen in Sudoku-Puzzlen mit einzigartigen Lösungen. Als im Oktober 2009, Gordon Royle 49151 17-Hinweis Puzzles sammelte, darunter keines von gleicher Form mit einem anderen (darunter verstehen wir das Puzzle zu übersetzen wie einfaches Drehen, Spiegeln oder Zahlentausch). Dennoch, bislang wurde kein 16-Hinweis Puzzle gefunden oder der Beweis angetreten, das kein 16-Hinweis Puzzle existiert, was die meisten Menschen glauben.

Gary McGuire, Professor der National University of Ireland, präsentierte eine Suche die das Ziel hatte, 16-Hinweis Puzzle zu lösen. Er entwickelte ein Programm, genannt CHECKER, um zu versuchen es zu lösen. In Übereinstimmung mit unseren Analysen benötigt das Programm über 300000 Jahre auf einem ein-Kern Computer ausgestattet mit einer Intel(R) Xeon(R) E5520 @ 2.27GHz CPU. (Wir nutzen diesen Kern um die Rechenzeit anzugeben.) Seine endgültige Aussage war "Wir benötigen einen Durchbruch in unserem Verständnis um die ganze Suche durchführbar zu machen. Außerdem müssen wir den Suchraum verkleinern oder einen viel besseren Algorithmus zum Suchen finden." (Scientific American, 2006)

In unseren bisherigen Forschungen fanden wir einen neuen Algorithmus und optimierten auch den Code um so die Suche um den Faktor 128 zu beschleunigen. Auf diese Weise, in Übereinstimmung mit unseren Experimenten, kann unser neues Programm das Problem in etwa 2417 Jahren auf einem CPU-Kern lösen. Daher wird es durchführbar, das offene Problem zu lösen. Als Beispiel, wenn 2417 Kerne via BOINC genutzt werden kann das Problem innerhalb eines Jahres gelöst werden. Und wenn 24170 Kerne genutzt werden, könnte es in 36 Tagen gelöst werden.

Hiermit danken wir alle die Ihre Rechenzeit sudoku@vtaiwan zur Verfügung stellen. Deine Teilnahme wird uns sehr helfen, das Problem zu lösen und Geschichte zu schreiben.

Voraussetzung Windows: Microsoft Visual C++ 2008 Redistributable Package

sudoku@vtaiwan
Beginn 2010
Ende 2013
Status hier
Admin
Institut National Chiao Tung University
Land Taiwan
Bereich Spiele
Anwendungen
Win sudoku@home 4.01
Linux sudoku@home 4.02
Mac sudoku@home 4.00
64bit sudoku@home 4.05 [linux]
sudoku@home 4.02 [win]
PS3
ATI
CUDA
Intel
Android
RPi
NCI
Systemspezifikationen
VRAM SP DP
RAM 6-21MB
Laufzeit min-7h
HDD 0,89MB
Traffic dl/ul kb / kb
Deadline 7 Tage
Checkpoints