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

Inhaltsverzeichnis

Zahlen, bitte!

In dieser Rubrik stellen wir immer dienstags verblüffende, beeindruckende, informative und witzige Zahlen aus den Bereichen IT, Wissenschaft, Kunst, Wirtschaft, Politik und natürlich der Mathematik vor.

• Alle Artikel zu "Zahlen, bitte!"

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.

Brute Force

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.

Symmetrien eliminieren

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.

Ein Jahr Rechenzeit

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.“

• Preußer, T.B. & Engelhardt: Putting Queens in Carry Chains, No 27, M.R. J Sign Process Syst (2016). doi:10.1007/s11265-016-1176-8
• Quelltexte des Q27-Projekts auf GitHub
  

(bo)