Zum Weltrekord: Q27
Hier finden sie ein paar zusätzliche Informationen zur Suche und Zählung der normalen Lösungen des Damen-Problems auf einem 27 mal 27 Brett.
Eine Esels-Brücke, mit der man sich die Zahl merken kann.
Für Leute, die sich die ersten tausend Stellen von Pi merken können, sind die 18 Ziffern der Ziffern von Q27 = 234.907.967.154.122.528 natürlich kein Problem. Allen anderen empfehle ich, die Ziffern in 6 Dreier-Gruppen einzuteilen, und gebe die folgenden Tips:
- Grob ist die Zahl "eine knappe Viertel-Trillion"; weiter sind die Ziffen der ersten Dreier-Gruppe aufsteigend. Damit ergibt sich 234.000.000.000.000.000 (234 Billiarden) als Näherungs-Wert. (Eigentlich muss man auf 235 Billiarden runden, aber dann sind die Ziffern nicht mehr einfach aufsteigend).
- Die zweite und dritte Gruppe haben die erste und dritte Ziffer gemeinsam, also 9x7; das x ist zuerst 0 und dann 6.
- Die letzten drei Dreier-Gruppen unterscheiden sich jeweils nur in einer Ziffer und mit Differenz 1 von einer Quadrat-Zahl:
Gruppe 4: 154 = 144 + 10, die Zehner-Ziffer ist gegenüber dem Quadrat von 12 um 1 erhöht.
Gruppe 5 (vorletzte Gruppe): 122 = 121 + 1, die Einer-Ziffer ist gegenüber dem Quadrat von 11 um 1 erhöht.
Gruppe 6 (letzte Gruppe): 528 = 529 - 1, die Einer-Ziffer ist gegenüber dem Quadrat von 23 um 1 vermindert.
Man kann sich natürlich auch die Primzahl-Zerlegung merken: 234.907.967.154.122.528 = 32 * 7 * 17 * 83 * 277 * 397 * 6.785.533. Also keine Primzahl-Potenzen, außer beim ersten Faktor 32 = 2 hoch 5. Allerdings bekommt man die Zahl dann mit einem alten 8- oder 10-stelligen Taschenrechner und auch mit einem im Smartphone vorhanden Rechner, der auch nicht mehr Stellen unterstützt, nicht mehr zusammen.
Kann man das Ergbnis überprüfen?
Das Ergebnis ist natürlich nicht so leicht zu überprüfen. Man müsste die Lösungen unabhängig von der jetzigen Lösung erneut suchen und zählen. Mit immer schnelleren Computern wird dies in Zukunft wohl möglich, aber bis jetzt (August 2020) habe ich davon nichts gehört.
Es ist natürlich möglich, Teil-Aspekte und Teil-Ergebnisse unabhängig zu überprüfen. Als erstes kann man die Theorie, die hinter dem Ansatz steht, kritisch durchdenken. Sie ist in Grundzügen hier dargestellt. Dort geht es um die Frage: wie kann man die Symmetrie überhaupt nutzen? Wie man dies praktisch tut, ist im Artikel Die Lösung des 27-Damen-Problems in der Zeitschrift "Spektrum der Wissenschaft" beschrieben, und auch noch etwas allgemeiner und abstrakter im Artikel An easy counting lemma im Journal "Discrete applied mathematics".
Eine weitere Validierung ergibt sich, wenn man denselben Algorithmus auf kleineren Brettern anwendet. Das haben wir für n = 17 bis n=22 getan und damit die bereits bekannten Werte bekommen.
Weiter kann man Teil-Ergebnisse überprüfen. Das Gesamt-Problem ist ja in 2.024.110.796 (gut zwei Milliarden) Teil-Probleme mit je eine Vorbelegung zerlegt. Einzelne dieser Vorbelegungen kann man mit unabhängigen Programmen überprüfen. Das haben wir für etliche getan und alle diese Werte verifiziert. Darunter waren insbesondere die beiden "großen" Vorbelegungen mit nur vier Damen und einige mit acht Damen, die gar keine Lösung erlauben.
Wenn jemand weiter an einer Verifizierung arbeiten möchte, dann stellen wir die Datenbank (ca 30 GB) oder Einträge daraus gerne zur Verfügung.
Vergleich mit früheren Ergebnissen
Bei früheren Suchen hat es ähnliche Tabellen oder Datenbanken gegeben. Als Vorbelegung waren dort Damen auf den ersten vier bis sechs Spalten eingetragen, und dazu die Anzahl der gefundenen (Roh-)Lösungen. Für das 26-mal-26-Brett gibt es eine solche Tabelle; auch diese stellen wir bei Bedarf gerne zur Verfügung. Bedingt durch den anderen Ansatz gibt es eine solche Tabelle bei n=27 nicht. Es gibt jedoch eine Vergröberung auf zwei Spalten; diese können sie hier für Q27 herunterladen, und ebenso die Vergröberung für Q26. Ein wenig aufbereitet auch in einer LibreOffice-Datei, wobei die Summe am Ende ungenau ist - was zum nächsten Abschnitt überleitet.
Welches Problem haben Excel oder OpenOffice / LibreOffice mit der Anzahl?
Oben stand schon, dass Taschenrechner für die Darstellung der Anzahl ungeeignet sind. Aber auch die in der Überschrift genannten Tabellen-Kalkulations-Programme stellen die Zahl nicht richtig dar. Woher kommt das? Die Anzahl ist groß, aber zunächst nicht zu groß für ein long in Java oder in C; solche Zahlen sind mit 64 Bit dargestellt, von denen ein Bit für das Vorzeichen verwendet wird. Die Zahl hat "nur" 58 Bits, sie passt also in dieses Format hinein.
Aber die Programme für Tabellen-Kalkulation verwenden nicht die Integer- oder Long-Integer-Darstellung; sie verwenden das Format eines "double" in Java. Diese hat auch 64 Bits, aber davon 12 für Vorzeichen und einen Exponenten und nur die verbleibenden 52 Bits für die sog. Mantisse. Für eine genaue Darstellung der Q27-Zahl fehlen daher 6 Bits! Dieses Problem tritt übrigens auch bei der Anzahl der Lösungen für das 26-mal-26-Brett auf, bei 25-mal-25 reichen die 52 Bits gerade noch.
Grafiken zur Verteilung der Lösungen.
Grafiken zur Verteilung der Lösungen gibt es hier.