Archiv der Kategorie: Uncategorized

Doppelter Durchbruch – 17 Vorgaben-Sudoku


Warning: count(): Parameter must be an array or an object that implements Countable in /homepages/20/d200271062/htdocs/app536726920/wp-content/plugins/q-and-a/inc/functions.php on line 252

Am Neujahrstag 2012 veröffentlichte der irische Informatiker Gary McGuire einen Beweis dafür, womit alle seit 2006 gerechnet hatten: Jedes eindeutig lösbare Sudoku benötigt 17 Vorgaben. Die Sudokuwelt war verblüfft. Sie war weniger davon überrascht, dass der Beweis geglückt war, als davon, dass es McGuire war, der den Beweis erbrachte.

Am 05.09.13 endete das unglücklich verlaufene Projekt Vtaiwan der Taiwanesen Huang-Hsuan Lin und I-ChenWu mit dem gleichen Beweis. War dies Duplizität der Ereignisse oder ein tragischer zweiter Platz?

Von G.F. – Bewerbung an der Freien Journalistenschule Berlin

Es gibt 4,5 Milliarden unterschiedliche Sudokulösungen. Das Programm Checker, das 2006 von McGuire programmiert wurde, prüft alle gelösten Sudoku darauf, ob es zur Lösung ein gültiges sechszehn Vorgaben Sudoku geben kann. Dieses Problem ist gut auf parallele Rechner verteilbar. In den Algorithmus von Checker flossen überwiegend Erkenntnisse ein, die Sudoku Amateuren zu verdanken sind.

Checker benötigte nach einer Untersuchung von Lin/Wu 2010 für die Lösung des Gesamtproblems 311.000 Prozessorjahre. Dies entspricht 30 Minuten Rechenzeit je Lösung. Berechenbar werden Probleme ab etwa von 2.500 Prozessorjahren.

Moorsche-Gesetz besagt, dass sich die Leistungsfähigkeit von Computern alle 18 Monate verdoppelt. Aus Sicht des Jahres 2010 bedeutete dies, dass das Problem mit der Technik des Jahres 2022 vermutlich mit einem Aufwand von 2.500 Prozessor Jahren gelöst werden konnte. Es bestand daher vor 2010 kein Grund zur Eile.

Lin und Wu stellten auf einem Informatiker Kongress (2010) eine Verbesserung des Programms vor, die die Rechenzeit auf 2417 Prozessorjahre reduzierte, und starteten das BIONIC Projekt Vtaiwan. Dabei wurden nicht genutzte Computerkapazitäten von Firmen und Privatpersonen zur Verfügung gestellt.

Das taiwanesische, nationale Zentrum für Hochgeschwindigkeitsrechnen wurde Hauptsponsor. Das prognostizierte Projektende war 2014. Ende 2010 erzwang ein Computer Crash einen Neustart des Projektes.

Als McGuire sein Projekt Anfang 2011 ohne Medienrummel startete, stand der Sieger fest. Er wusste, dass sein nochmals verbessertes Programm nur noch 800 Prozessorjahre für die Lösung benötigte. Er war sicher, dass Vtaiwan eher beschäftigt war, den Rückschlag aufzuholen, als Ihr eigenes Programm weiter zu verbessern.

In der Zusammenfassung des Projektes 2013 beschreibt McGuire seine Verbesserungen. Sie wurden 2010 vermutlich deshalb noch nicht umgesetzt, weil der Gesamtaufwand weit über 100.000 Prozessorjahre gewesen wäre und einen Projektstart nicht gerechtfertigt hätte.

Wie bei den Taiwanesen basierte die entscheidende Verbesserung auch bei McGuire auf der Beschleunigung eines Teilalgorithmus (Hitting-Set). Es gab keine Veröffentlichung von ihm zum Thema Hitting-Set vor der Projektzusammenfassung 2013. Es kann daher gut sein, dass er Veröffentlichung der Taiwanesen profitiert hat. Nur der zeitliche Ablauf und leichte Unterschiede bei der Umsetzung sprechen dafür, dass es sich um eine parallele Entwicklung handelte.

Entscheidend für den Ausgang des Rennens war schließlich, dass es McGuire gelang, sich 10 % der Kapazitäten des irischen Zentrums für Hochgeschwindigkeitsrechnen zu sichern. Während der Vorbereitung des europäischen Rechnerverbundes PRACE waren dort Übungsaufgaben gefragt. Vermutlich stand in seinem Antrag auf Rechenzeit als Forschungsziel: „Test zum Vergleich der Performance von Höchstleistungsrechnern“. Danach fällt es am am Neujahrtag 11 leicht, den Ausgang vorherzusagen.

Wird heute das Stichwort Minimumsudoku googelt, taucht nur noch der Name McGuire auf. In der Welt des Sudoku ist er ein Rockstar. Am 05.09.2013 endete das Projekt Vtaiwan und bestätigte seine Ergebnisse. Lin und Wu sind, was Sudoku angeht, fast vergessen. Ohne Ihre Verbesserung wäre eine Lösung des Problems nicht möglich gewesen. Es bleiben Zweifel daran, ob es sich um eine parallele Entwicklung handelte. Aufgrund der Gesamtleistung ist es nicht unverdient, dass der Lorbeerkranz nach Irland ging.