So funktioniert 8 Queens

Je nachdem, in welchen Kreisen Sie sich bewegen – sagen wir, Ihr bester Freund ist Computerprogrammierer und Ihre Schwester ist ein Wunderkind im Schachspiel –, sind Sie vielleicht bereits mit dem 8-Damen-Puzzle vertraut. Für den Rest von uns ist das 8-Damen-Puzzle (oder Problem oder einfach „8-Damen“) wahrscheinlich nicht etwas, worüber wir viel Zeit damit verbringen, darüber nachzudenken.

Das Rätsel ist einfach genug. Wie kann man 8 Damen so auf ein Schachbrett stellen, dass sich keine zwei angreifen? Alternativ lautet die Frage manchmal: „Wie viele Damen können maximal auf ein Schachbrett gestellt werden, damit sich keine zwei angreifen können“, aber dieses Rätsel wird viel weniger schwierig, wenn Sie das und den Begriff googeln „Das 8-Damen-Puzzle“ erscheint.

Sie fragen sich vielleicht, warum um alles in der Welt sich irgendjemand darum kümmert, wo Sie Ihre acht Königinnen aufbewahren. Und ja, oberflächlich betrachtet ist es nur ein strategisches Puzzle. Aber (und hier ist es praktisch, einen besten Freund zu haben, der Computer programmiert) Das 8-Damen-Puzzle ist eine großartige Möglichkeit, das Geschick und die Bildung eines Programmierers zu testen.

Nun, keine Angst. Sie werden nicht gezwungen, die Feinheiten der Computerprogrammierung zu verstehen, um weiterlesen zu können. Aber Sie sollten wissen, dass das Lösen des Rätsels mit einem Programmiercode erreicht werden kann – und einige sind eleganter als andere. Zum Beispiel können Sie die Lösung definitiv mit einem "Brute-Force"-Programm finden, das einfach alle möglichen Platzierungen durchgeht und eine nach der anderen ausschließt. Aber ein erfahrener Codierer wird in der Lage sein, ein Programm zu konstruieren, das Verknüpfungen mit einem verfeinerten Algorithmus enthält , um Ihnen schneller eine Lösung zu finden. In der Lage zu sein, ungewöhnliche oder originelle Wege zu finden, um eine Lösung für ein so umfassendes Problem wie 8 Queens zu codieren, kann ein großartiger Test für das Können eines Codeschreibers sein.

Wir werden Ihnen also keine Einsen und Nullen anhängen, um Ihnen zu erklären, wie 8 Damen funktionieren, aber wir werden Ihnen ein paar Lösungen für das Rätsel geben.

Nachdem wir nun die grundlegende Prämisse des Rätsels verstanden haben, sollten wir feststellen, warum das Problem so einzigartig ist. Lassen Sie uns dazu unsere Schachgrundlagen auffrischen. In einer Schachpartie ist die Dame eine Kraft, mit der man rechnen muss. Sie kann sich in einer geraden Linie vertikal, horizontal oder diagonal so viele Felder bewegen, wie sie möchte. Der einzige Haken ist, dass sie keine Figuren springen kann. Wenn ihr also ein Bauer im Weg ist, muss sie ihn schlagen und anhalten.

Das macht das 8-Damen-Puzzle interessant. Wenn Königinnen sich nach oben, unten, links, rechts und diagonal bewegen können, wie viele streitende Royals können dann das Brett besetzen, ohne dieselbe Reihe, Spalte oder Diagonale zu teilen? Jetzt denken Sie vielleicht, es wäre eine großartige Idee, einfach eine Dame auf das Brett zu stellen und verschiedene Kombinationen auszuprobieren, bevor Sie alle treffen. Und sicher, das ist möglich. Aber es gibt 4.426.165.368 mögliche Lösungen, also sollten Sie eine Abkürzung finden.

Bevor wir unsere Königinnen in 4 Milliarden verschiedene Quadrate setzen, wollen wir zunächst anerkennen, dass sich eines Tages tatsächlich jemand hinsetzte und entschied, dass dies eine gute Möglichkeit wäre, einen oder zwei Nachmittage zu verschwenden. Wie vorherzusehen war, war es nicht jemand, der Wiederholungen von „My Big Fat Gypsy Wedding“ aufholen musste – es war ein deutscher Schachmeister und Komponist aus dem 19. Jahrhundert namens Max Bezzel. (Ein Schachkomponist ist jemand, der Schachprobleme – auch bekannt als Rätsel – zum Lösen erfindet .) Es erschien erstmals 1848 in der deutschen Schachzeitschrift DieSchachzeitung.

Bezzel war nicht so sehr daran interessiert, das Rätsel zu lösen; er begnügte sich damit, einfach die Frage zu stellen. 1850 schrieb der Mathematiker Franz Nauck jedoch einen weiteren Artikel, der das Problem diskutierte. (Die ersten Lösungen des Rätsels wurden schließlich von Nauck gelöst.) Das erregte die Aufmerksamkeit von Karl Gauß, einem Mathematiker des 19. Jahrhunderts, der für die Entdeckung der grundlegenden Theorie der Algebra bekannt war. Als Gauß sich für die Lösung interessierte, folgten andere, und verschiedene Ansätze zur Lösung des Rätsels begannen sich zu entwickeln.

Es ist keine große Überraschung, dass „acht“ die Antwort auf unsere spezielle Frage ist, wie viele Damen auf einem Brett platziert werden können, ohne sich gegenseitig anzugreifen. Aber lassen Sie uns untersuchen, auf wie viele Arten acht Damen platziert werden können und wie dies festgelegt wird.

Wir haben darüber gesprochen, dass Brute-Force-Computerprogramme eine Möglichkeit sind, das Rätsel zu lösen – und das manuelle Ausprobieren von 4.426.165.368 Möglichkeiten würde sicherlich als Brute-Force gelten – aber es gibt einfachere Möglichkeiten, die Lösungen einzugrenzen. Eine vereinfachte Methode wurde bereitgestellt, als JWL Glaisher, ein anderer Mathematiker, 1874 eine Arbeit veröffentlichte, in der er seine Verwendung von Determinanten zum Finden einer Lösung beschrieb. "Determinanten" klingt ein wenig schwierig, aber alles, was Sie wirklich wissen müssen, ist, dass Glaisher im Grunde eine Matrix konstruierte und - unter Verwendung eines Systems, das er von dieser Matrix ableitete - in der Lage war, die möglichen Lösungen auf 92 einzugrenzen.

Und 92 Lösungen bleibt es. Aber lassen Sie sich nicht täuschen; Sie werden nicht in der Lage sein, 92 Schachbretter mit jeweils einem einzigartigen Satz von 8 Königinnen friedlich anzuordnen, da es tatsächlich nur 12 einzigartige Lösungen gibt.

Verwirrt? Der Unterschied zwischen 12 einzigartigen Lösungen und 92 fundamentalen Lösungen hängt buchstäblich davon ab, wie Sie es betrachten. Während Sie mit Ihren acht Damen 12 verschiedene Bretter unverwechselbar aufstellen könnten, genügt es, das Brett einfach zu drehen – oder sogar auf einen Spiegel zu spiegeln – um die Bretter technisch unterschiedlich aussehen zu lassen und somit ein „anderes“ zu haben. Lösung. (Dies nennt man Rotations- und Reflexionssymmetrieoperationen.) Sie nehmen also Ihre 12 einzigartigen Bretter, drehen sie um 90, 180 und 270 Grad und spiegeln sie dann bei jeder Drehung. Aber noch etwas – ein einzigartiges Board ist symmetrisch, also sieht es aus zwei Blickwinkeln gleich aus. Während alle anderen Boards acht Varianten haben, hat das symmetrische Board nur vier. Anstelle von 12 Boards mal 8 Variationen (96) subtrahieren wir also tatsächlich die vier, die es beim symmetrischen Board nicht gibt. Was bekommen wir? 92 grundlegende Lösungen.

Lassen Sie sich jetzt nicht von der Mathematik täuschen. Sie können sich immer ein Schachbrett suchen und versuchen, einige Platzierungen für sich selbst herauszufinden. (Eine Antwort zu finden ist natürlich viel einfacher als alle 12.) Und es gibt sogar Programme im Web , mit denen Sie verschiedene Lösungen finden können. (Warnung: Sie könnten dazu führen, dass Sie sich dumm fühlen.)

Bevor Sie Ihre Damen mischen, sehen Sie sich die nächste Seite an, um weitere Informationen zu erhalten.

Da ich mich weniger für einen Algorithmus als für ein Alphabet interessiere, hatte ich keine großen Hoffnungen, das 8-Damen-Puzzle zu verstehen. Obwohl ich sicher war, dass es irgendeine praktische Anwendung hatte, konnte ich es nicht sehen. Ironischerweise begann ich zu sehen, warum es nützlich sein könnte, als ich die Weite des Problems verstand. Das Finden einer Reihe von Lösungen aus einer riesigen Menge von Möglichkeiten ist einer der Gründe, warum Code existiert. Das 8-Damen-Problem fordert Programmierer und Mathematiker gleichermaßen heraus, neue Techniken zu entdecken, um die Suche zu vereinfachen.

verwandte Links

Quellen