Menü

Zahlen, bitte! Das 27-Damen-Problem ist gelöst

Ein Jahr lang hat das Q27-Projekt massiv parallel gerechnet, um der Welt eine neue Zahl zu präsentieren. Hier ist sie: 234.907.967.154.122.528.

Zahlen, bitte! Das 27-Damen-Problem ist gelöst

Es ist ein altbekanntes Puzzle und wird gern als Beispiel hergenommen, um im Informatik-Studium Backtracking-Algorithmen zu erklären: Man platziere acht Damen so auf einem Schachbrett, dass sie sich nicht gegenseitig schlagen können. Eine Lösung zu finden, ist selbst von Hand nicht allzu schwer; alle abzuzählen, schon eher: 92 Möglichkeiten gibt es insgesamt.

Das Problem lässt sich naheliegenderweise auf ein n×n-Brett mit n Damen verallgemeinern – und explodiert kombinatorisch förmlich, wenn n größer wird. 2009 gelang die Berechnung von Q26, der Anzahl der Lösungsmöglichkeiten für das 26-Damen-Problem, und erst 2015 hat sich eine Forschergruppe um Thomas Preußer von der TU Dresden an Q27 herangetraut. Und nach etwas über einem Jahr massiv parallelen Rechnens auf FPGAs steht nun seit einigen Tagen das Ergebnis fest: 234.907.967.154.122.528 Lösungen hat das 27-Damen-Problem.

Backtracking-Suche beim 8-Damen-Problem

Faszinierend an diesem Problem ist, dass es sich bisher allen Versuchen widersetzt hat, es mathematisch zu knacken. Man kann durch Symmetrieüberlegungen den Suchraum um den Faktor acht reduzieren, aber ansonsten bleibt nur rohe Gewalt: Eine Brute-Force-Suche. Das heißt man platziert eine Dame in der ersten Spalte, die nächste in der zweiten Spalte und so weiter, bis keine mehr passt. Dann geht man eine Spalte zurück und probiert die nächste Möglichkeit; wenn alle erschöpft sind, wieder eine Spalte zurück und so weiter, bis der ganze Suchraum abgegrast ist.

Zum Glück ist diese Aufgabe auf einfache Weise parallelisierbar, und darin liegt der Schlüssel zu der jetzt gefunden Lösung: Nur durch massiv paralleles Rechnen auf einem Äquivalent von Tausenden von Kernen war es möglich, die Zahl in „nur“ einem Jahr zu ermitteln. Wenn man eine gewisse Anzahl von Damen vorplatziert, dann ist das Problem, die restlichen Damen zu platzieren, komplett unabhängig von allen anderen möglichen Vorplatzierungen.

Für Q27 wählte Preußer als Vorplatzierungen einen Ring aus den jeweils äußeren beiden Zeilen und Spalten an jeder Seite des Schachbretts. Dort passen – je nachdem, wie sie sich in die Quere kommen – vier bis acht Damen hinein und es gibt insgesamt 2.024.110.796 Möglichkeiten dieser Vorplatzierungen. In so viele parallel berechenbare Unterprobleme zerfällt das Problem also: Ein ideales Forschungsfeld für massiv paralleles Rechnen.

Bei der oben genannten Zahl der Vorplatzierungen sind die Symmetrien schon eliminiert: Aus einer Platzierung gewinnt man durch Drehen beziehungsweise Spiegeln entlang einer von vier Achsen insgesamt acht Platzierungen, die jeweils dieselbe Anzahl von Lösungen liefern, alle eben entsprechend gedreht oder gespiegelt. Wenn eine Vorplatzierung komplett asymmetrisch ist, braucht man also nur für eine dieser acht die Zahl möglicher Vervollständigungen zu zählen und darf diese dann mit acht multiplizieren.

Nur einige wenige, nämlich 30.543 Vorplatzierungen, waren symmetrisch bezüglich einer Drehung um 180 Grad; bei ihnen wurde also jede Lösung im Prinzip doppelt gefunden, weswegen man die Anzahl mit vier multiplizieren darf. Und bei den nur 181 Vorplatzierungen, die gegenüber einer 90-Grad-Drehung symmetrisch waren, multipliziert sich die Lösungszahl entsprechend mit zwei.

n Anzahl Lösungen Echt verschiedene Lösungen
(symmetrische nur einfach gezählt)
1 1 1
2 0 0
3 0 0
4 2 1
5 10 2
6 4 1
7 40 6
8 92 12
9 352 46
10 724 92
11 2.680 341
12 14.200 1.787
13 73.712 9.233
14 365.596 45.752
15 2.279.184 285.053
16 14.772.512 1.846.955
17 95.815.104 11.977.939
18 666.090.624 83.263.591
19 4.968.057.848 621.012.754
20 39.029.188.884 4.878.666.808
21 314.666.222.712 39.333.324.973
22 2.691.008.701.644 336.376.244.042
23 24.233.937.684.440 3.029.242.658.210
24 227.514.171.973.736 28.439.272.956.934
25 2.207.893.435.808.352 275.986.683.743.434
26 22.317.699.616.364.044 2.789.712.466.510.289
27 234.907.967.154.122.528 29.363.495.934.315.694

Das war auch schon alles, was sich mathematisch an der Sache optimieren ließ. Der Rest war eine Implementierung eines Backtracking-Lösers auf FPGAs. Ein Field Programmable Gate Array ist im Prinzip ein großer Haufen Logikgatter, deren Verschaltung man per Software verändern kann. Eine solche „programmierte Schaltung“ lässt sich dann zwar nicht mit ganz so hohen Taktfrequenzen betreiben wie ein gewöhnlicher Prozessor, platziert aber pro Taktzyklus eine Dame. Eine Software-Implementierung auf einem Intel Core i3-4130 ist ungefähr so schnell wie ein Hardware-Löser bei 100 MHz.

Auf ein einzelnes High-End-FPGA passen mehrere hundert solcher Hardware-Löser und moderne Chips erreichen auch höhere Taktfrequenzen, sodass die Performance an die von 1000 normalen CPU-Kernen heranreicht.

So hat das Projekt dann am 5. September 2015 auf einem schon etwas betagten Virtex-5-FPGA die Arbeit aufgenommen, zu dem sich später weitere und leistungsfähigere FPGAs gesellten, die meisten aus den Laboren der TU Dresden, wo sie ansonsten ungenutzte Rechenzeit für das Projekt nutzten.

Gesteuert wurde das Ganze von einem zentralen Server, der die Teilaufgaben aus der Datenbank der 2.024.110.796 Vorplatzierungen austeilte, die Ergebnisse einsammelte und auf Plausibilität prüfte. Am 19. September 2016 war es schließlich so weit und die Gesamtsumme stand fest.

Und wie siehts für Q28 aus? Wenn man genauso vorgeht, sind das mit 3.034.595.565 nur moderat mehr Teilprobleme, die allerdings einen Zacken härter sind. Thomas Preußer meint dazu: „Mit einem vernarrten Hardwaresponsor, am besten mit einem Wettlauf zwischen FPGA und GPU im Rücken, lässt sich das machen. Eine weitere elegante mathematische Abkürzung wäre mir aber noch lieber.“

(bo)
Anzeige
Anzeige