One Billion Queens Problem Solution oder "Untersuchung der Gesetze in der Liste der Lösungen des n-Queens-Verteilungsproblems"

Zusammenfassung


Es wird eine Beschreibung der Gesetze gegeben, die in einer sequentiellen Liste aller Lösungen für das Problem der Verteilung von n-Fernets aufgestellt wurden. Es wird festgestellt, dass:


  • Der Anteil der Komplettlösungen in der allgemeinen Liste aller Lösungen nimmt mit zunehmendem Wert von n ab.
  • Komplettlösungen werden in einer sequentiellen Liste aller Lösungen so verteilt, dass am wahrscheinlichsten Komplettlösungen in einer Liste nebeneinander auftreten.
  • In der allgemeinen Liste aller Lösungen gibt es eine Symmetrie in Bezug auf die Anordnung der vollständigen Lösungen. Wenn die Lösung an der i-ten Position vom Anfang der Liste abgeschlossen ist, ist auch die symmetrische Lösung vom Ende der Liste, die sich an der Position n-i + 1 befindet, vollständig (die Symmetrieregel der Lösungen).
  • Alle Lösungspaare, sowohl kurze als auch vollständige, symmetrisch in der Liste aller Lösungen angeordnet, sind komplementär - die Summe der Indizes der Positionen der entsprechenden Linien ist konstant und entspricht n + 1 (Regel der Komplementarität der Lösungen). Dies legt nahe, dass nur die erste Hälfte der Liste aller Komplettlösungen "einzigartig" ist, jede vollständige Lösung aus der zweiten Hälfte der Liste kann auf der Grundlage der Komplementaritätsregel erhalten werden. Die Folge dieser Regel ist die Tatsache, dass für jeden Wert von n die Anzahl der Komplettlösungen immer eine gerade Zahl ist.
  • Die Aktivität der Zellen der Reihen der Lösungsmatrix ist symmetrisch um die horizontale Achse, die durch die Mitte dieser Matrix verläuft. Dies bedeutet, dass die Aktivität der Zellen der i-ten Zeile immer mit der Aktivität der Zellen der Zeile n-i + 1 zusammenfällt. Unter Aktivität ist die Häufigkeit zu verstehen, mit der der Zellindex in der entsprechenden Zeile der vollständigen Lösungsliste auftritt. In ähnlicher Weise ist die Aktivität der Zellen der Spalten der Matrix der Lösung um die vertikale Achse symmetrisch, wodurch die Matrix in zwei gleiche Teile geteilt wird
  • Unabhängig von n erscheint bei der sequentiellen Suche nach allen Lösungen die erste vollständige Lösung erst nach einer kurzen Abfolge von kurzen Lösungen. Die Größe der Anfangssequenz kurzer Lösungen nimmt mit zunehmendem n zu. Die Länge der Liste der kurzen Lösungen vor dem Auftreten der ersten vollständigen Lösung für gerade Werte von n ist viel länger als für die nächsten ungeraden Werte.
  • Die Zeile in der Entscheidungsmatrix, in der die Schwierigkeiten beim Vorwärtsgehen beginnen, und die erste kurze Entscheidung wird gebildet, teilt die Matrix nach der Regel des Goldenen Schnitts. Für kleine Werte von n ist eine solche Schlussfolgerung ungefähr, jedoch steigt mit zunehmendem Wert von n die Genauigkeit einer solchen Schlussfolgerung asymptotisch auf das Niveau der Standardregel.

Diese Veröffentlichung präsentiert die wichtigsten Ergebnisse des Artikels [1] , der in der Zeitschrift "Modelling of Artificial Intelligence, 2018, 5 (1)" veröffentlicht wurde. Auf Habré gab es Arbeiten zum n-Queens-Problem: [2] , [3] ,
Das Problem der Verteilung von n Damen auf einem Nxn-Schachbrett hat eine lange Geschichte. Es wurde ursprünglich 1848 von M. Bezzel [4] als intellektuelle Herausforderung für ein gewöhnliches Schachbrett formuliert. Im Laufe der Zeit wurde die Problemstellung um F.Nauck [5] erweitert, und die Größe des Schachbretts könnte beliebig sein.


Einleitung


Die Formulierung des Problems ist ziemlich einfach: Sie müssen n Damen auf einem Schachbrett der Größe Nxn verteilen, so dass jede Zeile, jede Spalte sowie die linke und rechte Diagonale, die durch die Zelle, in der sich die Königin befindet, verlaufen, nicht mehr als eine Königin hat. Diese Aufgabe ist für jemanden leicht zu verstehen oder zu erklären, aber es ist ziemlich schwierig, sie zu lösen. Tatsache ist, dass es keine Regeln gibt, nach denen Königinnen in jede Linie gesetzt werden können, um eine Lösung zu erhalten. Die Lösung kann nur auf der Grundlage der Aufzählung verschiedener Optionen für den Ort von Königinnen in diesen oder anderen Linien erhalten werden. Die Komplexität dieser Lösung besteht jedoch darin, dass die Anzahl aller Varianten der Damenposition exponentiell mit steigendem n ansteigt. Die Ausführung eines Schrittes nach vorne für die Position der Königin in der freien Position einer bestimmten Zeichenfolge


Es gibt eine Vielzahl von Publikationen, die sich auf verschiedene Aspekte der Lösung des Problems von n-Queens beziehen. Sie lassen sich auf mehrere Forschungsbereiche zurückführen: die Suche nach Komplettlösungen für einen gegebenen Wert der Größe eines Schachbretts (n), die Entwicklung eines schnellen Algorithmus, um eine Lösung für verschiedene Werte von n zu finden, die Lösung des gesamten Satzproblems zu einer Komplettlösung, für eine beliebige Zusammensetzung von k Damen rechnerische Komplexität algorithmischer Berechnungen sowie verschiedene Modifikationen der ursprünglichen Problemformulierung. Um sich mit diesen Bereichen vertraut zu machen, würde ich interessante Publikationen von B. Jordan, S. Brett [6] und IP Gent, C. Jefferson, P. Nighting [7] empfehlen, die einen recht detaillierten Überblick über die verschiedenen Forschungsrichtungen bieten. Besonders hervorzuheben ist die Online-Veröffentlichung [8]unterstützt von Walter Costers, das von einem Team der Universiteit Leiden vorbereitet wurde und Links zu 342 Publikationen enthält, die sich auf das Problem der N-Queens beziehen (Stand Dezember 2018).


Obwohl das Problem von n-Queens seit mehr als 150 Jahren bestehen bleibt und in dieser Zeit eine Vielzahl von Publikationen erschienen ist, konnte ich keinen Job finden, der für das Auffinden von Mustern in den Ergebnissen der Lösung dieses Problems relevant wäre. Bei den meisten Projekten ging es um die Suche nach allen Lösungen, höchstwahrscheinlich retteten sie nicht die gefundenen Lösungen und schauten nicht auf das, was dort drinnen war. Bei der Formulierung des Problems gab es andere dominante Ziele, und unsere geschätzten Kollegen erreichten sie. Aus der Ferne schien mir jedoch die Situation ähnlich zu sein, wenn eine Person Eier zum Frühstück kocht, sie jedoch nicht isst, sondern herauswirft und nur die Anzahl der gekochten Eier im Gedächtnis belässt. Ich war immer davon überzeugt, dass, wenn die Daten nicht zufällig sind, eine gewisse Regelmäßigkeit vorhanden sein muss, selbst wenn wir diese Regelmäßigkeit nicht finden können.


Neben dem Wunsch, den Mitgliedern der Habra-Gemeinschaft nützliche Informationen zum Nachdenken zu geben, möchte ich talentierte Programmierer, deren Mehrheit bei Habré einer solchen Entwicklungsrichtung mehr Aufmerksamkeit widmen würde als der Computermodellierung (Computational Simulation). Als "Forschungsmethode" wird eine solche "Algorithmische Mathematik" an der "Spitze" vieler Bereiche verwendet: Künstliche Intelligenz, Software-Wissenschaft, Data Science, ... und ich bin sicher, dass sehr komplexe und wichtige Probleme für die praktische Anwendung auf der Grundlage algorithmischer Mathematik gelöst werden und in keiner Weise ansonsten


Definitionen


Im Folgenden wird die Größe des Schachbretts mit dem Symbol n bezeichnet. Wir bezeichnen eine Lösung als abgeschlossen, wenn alle n Damen auf dem Schachbrett konsistent platziert sind. Bei allen anderen Lösungen, wenn die Anzahl der korrekt platzierten Damen weniger als n beträgt, werden kurze Lösungen genannt. Mit der Länge der Lösung meinen wir die Anzahl (k) der korrekt platzierten Damen. Die Anzahl aller Lösungen für einen gegebenen Wert von n wird mit dem Symbol m bezeichnet. Als Analogon eines "Schachbretts" der Größe nx n. Betrachten wir eine "Lösungsmatrix" der Größe nx n.


Start


Für die Forschung wurde ein Algorithmus entwickelt, um alle Lösungen für einen beliebigen Wert n zu suchen. Wir haben keine Standardrekursion oder das übliche verschachtelte Schleifensystem verwendet. Für große Werte von n wäre ein solcher Ansatz ziemlich problematisch. Der Algorithmus wurde auf der Grundlage einer Reihe interagierender Ereignisse aufgebaut, in denen jeweils ein bestimmtes System von Aktionen, die miteinander verbunden sind, stattfindet. Dadurch ist es möglich, den Mechanismus zum Ändern des Zustandsraums einfach zu implementieren, wenn der nächste Knoten im Zweig der Aufgabenlösung ausgewählt wird (Vorwärtsverfolgung), oder Spuren vorher durchgeführter Aktionen gelöscht werden, wenn ein oder mehrere Schritte zurück ausgeführt werden (Rückverfolgung). Der Algorithmus stellt keine besonderen Anforderungen an die Speicher- oder Prozessorgeschwindigkeit.


Basierend auf diesem Algorithmus wurden alle aufeinanderfolgenden Lösungen (sowohl kurze als auch vollständige) für verschiedene Werte der Lösungsmatrix n = (7, ..., 16) gefunden. Da die Größe der Liste der Komplettlösungen die benannte Sequenz von On-Line Encyclopedya of Integer Sequences ist (Sequenz A000170 [9]) und in vielen Veröffentlichungen angegeben ist, erscheint es mir interessant, die Größe der Liste aller Lösungen (kurz + voll) für die betrachteten n Werte anzugeben: 7 (194), 8 (736), 9 (2 936), 10 (12 774), 11 (61 076), 12 (314 730), 13 (1 716 652), 14 (10 030 692), 15 ( 62 518 772),16 (415 515 376).


Unter Verwendung der gefundenen Lösungen werden die Formulierungen einiger Probleme, Methoden zu deren Lösung und eine Beschreibung der erzielten Ergebnisse vorgestellt.


1. Auf dem Zustandsraum, in dem nach Lösungen gesucht wird


Die Aufzählung verschiedener Varianten der Anordnung der Damen in der einen oder anderen Reihe der Matrix der Lösung der Größe n führt zur Bildung des Zustandsraums. Wenn es keine Beschränkungen hinsichtlich der Position von Königinnen in bestimmten Zellen der Matrix gibt, dann wäre die Größe des Zustandsraums gleich n n. Wenn wir nur die Regel berücksichtigen, die den Standort von mehr als einer Dame in jeder Zeile und jeder Spalte verbietet, erhalten wir eine Untermenge des Zustandsraums, dessen Größe gleich n ist! Diese Teilmenge des Zustandsraums entspricht dem Problem der Verteilung von n durch den Turm. Wenn wir dabei auch die Regel berücksichtigen, die das Platzieren von mehr als einer Königin in der linken und rechten Diagonale durch die Zelle, in der sich die Königin befindet, untersagen, erhalten wir etwas Suchraum, dessen Größe weniger als n! Ist. Wir nennen diese Teilmenge des Zustandsraums - produktiver Suchraum, basierend auf der Tatsache, dass nur in diesem Teilraum alle möglichen Lösungen vorhanden sind. Alle vervollständigten Zweige im produktiven Suchraum sind Lösungen mit einer Anzahl korrekt platzierter Königinnen.


Abbildung 1 zeigt die grafischen Darstellungen des natürlichen Logarithmus von drei Indikatoren: a) die Faktorwerte (n!) Der Größe der Lösungsmatrix; b) die Anzahl aller Lösungen (sowohl kurz als auch voll); c) die Anzahl der Komplettlösungen - abhängig von der Größe der Matrix der Lösung (n). Wie erwartet zeigen alle Kurven ein exponentielles Wachstum mit zunehmendem Wert von n. Die Wachstumsraten der Anzahl aller Lösungen und die Anzahl der Komplettlösungen unterscheiden sich, obwohl dies in der Grafik aufgrund der geringen Größe der Stichprobe der Werte von n nicht so wahrnehmbar ist. Bei n = 13 beträgt die Differenz zwischen den Logarithmen dieser Indikatoren beispielsweise 3,148, und bei n = 16 erhöht sich diese Differenz um 0,190 und beträgt 3,333. Offensichtlich wird diese Diskrepanz mit einer weiteren Erhöhung des Wertes von n größer sein.



Abb.1: Die Abhängigkeit des Logarithmus von der Größe des Zustandsraums vom Wert von n

2. Wie sieht der Anteil der Komplettlösungen in der allgemeinen Liste aller Entscheidungen aus?


Es ist offensichtlich, dass, wenn die Wachstumsrate der Anzahl der Komplettlösungen hinter der Wachstumsrate der Anzahl aller Lösungen zurückbleibt, die Wahrscheinlichkeit, eine vollständige Lösung in der allgemeinen Liste aller Lösungen zu finden, mit zunehmendem n abnimmt. Abbildung 2 zeigt eine grafische Darstellung des Anteils der Komplettlösungen in der allgemeinen Liste aller Lösungen mit dem Wert von n. Es ist ersichtlich, dass mit zunehmender Größe der Lösungsmatrix der Anteil aller Komplettlösungen in der allgemeinen Liste abnimmt. Für die Anfangswerte von n = (7, ..., 14) verringert sich dieser Wert um das 5,66-fache von 0,262 auf 0,0364, und dann setzt sich die allmähliche asymptotische Abnahme dieses Wertes fort. Hier kommt es zu einem formalen Widerspruch zwischen zwei Aussagen: Zum einen wächst die Anzahl der Komplettlösungen mit steigendem Wert von n exponentiell. Auf der anderen Seite nimmt die Wahrscheinlichkeit, eine vollständige Lösung in einer sequentiellen Liste aller Entscheidungen zu erhalten, ständig ab. Dieses scheinbare Paradoxon wird sehr einfach erklärt: Die Größe des Produktionsraums und die damit verbundene Listengröße aller Lösungen wachsen mit zunehmendem n schneller als die Anzahl der Komplettlösungen. Dies ist, als würde man versuchen, eine Nadel im Heuhaufen zu finden - die Menge an Heu „mit einer Erhöhung des Wertes von n“ wächst schneller als die Anzahl der Nadeln, die dort verloren wurden. Wir können daher davon ausgehen, dass für n = 27 die Anzahl der Komplettlösungen ungefähr 2.346 * 10 beträgt Dies ist, als würde man versuchen, eine Nadel im Heuhaufen zu finden - die Menge an Heu „steigt mit dem Wert von n“ schneller an als die Anzahl der Nadeln, die dort verloren wurden. Wir können daher davon ausgehen, dass für n = 27 die Anzahl der Komplettlösungen ungefähr 2.346 * 10 beträgt Dies ist, als würde man versuchen, eine Nadel im Heuhaufen zu finden - die Menge an Heu „steigt mit dem Wert von n“ schneller an als die Anzahl der Nadeln, die dort verloren wurden. Wir können daher davon ausgehen, dass für n = 27 die Anzahl der Komplettlösungen ungefähr 2.346 * 10 beträgt17 , dann wird der entsprechende Wert der Anzahl aller Lösungen höchstwahrscheinlich 3-4 Größenordnungen größer als ~ 10 20 sein



Abb.2 Verringerung des Anteils von Komplettlösungen in der allgemeinen Liste aller Lösungen mit einer Erhöhung des Werts von n

3. Wie ist die Häufigkeit von Entscheidungen unterschiedlicher Länge in der Liste aller Entscheidungen?


Wie bereits erwähnt, handelt es sich bei allen abgeschlossenen Verzweigungen im produktiven Suchraum um Lösungen mit einer unterschiedlichen Anzahl korrekt platzierter Königinnen.
Wir sind an der Häufigkeit interessiert, mit der in der allgemeinen Liste aller Lösungen Lösungen unterschiedlicher Länge gefunden werden.


Tabelle 1 für die Werte von n = (7, ..., 12) zeigt die entsprechenden Werte der relativen Häufigkeiten für Lösungen mit unterschiedlichen Längen. Die entsprechende visuelle Darstellung dieser Daten ist in Abbildung 3 dargestellt.


Die Analyse der Tabelle führt zu folgenden Schlussfolgerungen:


a) Für jede Matrix der Größe n gibt es eine bestimmte Länge der Lösung, die eine maximale Frequenz (Fettdruck) hat.


Tabelle 1. Relative Häufigkeit (%) von Lösungen unterschiedlicher Länge (k) für eine Matrix der Größe n = (7, ..., 12)
n \ k 4 5 6 7 8 9 10 11 12
7 10.31 31.23 27,84 20,62
8 2,45 20.38 34,78 29.89 12,50
9 0,34 5,79 21,73 35,83 34.32 11,99
10 0,05 1,35 8.41 25.62 32,94 25,96 5,67
11 0,15 2.12 11,80 26,71 34.47 20.36 4.39
12 0,01 0,29 3.28 13.56 29,88 31.29 17.18 4,51

b) Mit steigendem Wert von n nimmt die Anzahl der Lösungen mit unterschiedlichen Längen zu. Dementsprechend verringert sich die relative Häufigkeit aller Entscheidungen.



Abb.3: Die Häufigkeit von Lösungen unterschiedlicher Länge in Abhängigkeit von der Größe der Lösungsmatrix, n = 7, ..., 16

c) Für jede Matrix der Größe n gibt es eine bestimmte Mindestgröße der Länge der Lösung, unterhalb derer keine kurzen Lösungen auftreten. Mit zunehmendem Wert von n nimmt der Wert dieser Schwelle zu. Für n = 8 ist beispielsweise der Schwellenwert 4, bei n = 16 ist der Schwellenwert 7.


4. Wie ist der relative Ort kompletter Lösungen in einer sequentiellen Liste aller Lösungen?


Bei der Formulierung des Problems „Über die Verteilung von n Damen“ gibt es keine Gründe, die Annahmen über die Reihenfolge der vollständigen Lösungen in der allgemeinen Liste aller Lösungen geben könnten. Wir fragten uns, ob die Komplettlösungen zufällig gleichmäßig in der allgemeinen Liste verteilt waren oder ob sie einige Besonderheiten hatten. Um dies herauszufinden, wurde eine Analyse der Abstände zwischen den nächstgelegenen Komplettlösungen in einer sequentiellen Liste aller Lösungen durchgeführt. Wie aus Fig. 4 ersichtlich ist, wo für n = 12 ein Diagramm der Änderungen der entsprechenden Frequenzen vorliegt,



Abb.4: Frequenz gegenüber Entfernung zwischen den nächstgelegenen Komplettlösungen in einer sequentiellen Liste aller Komplettlösungen (n = 12)

am häufigsten gibt es Komplettlösungen, die in der allgemeinen sequentiellen Liste aller Entscheidungen unmittelbar aufeinander folgen. Dies sind die Fälle der Bildung des Suchzweigs, bei denen Sie durch die Beziehung der freien Positionen in den letzten Zeilen zwei oder mehr aufeinanderfolgende vollständige Lösungen bilden können. Außerdem haben diese Komplettlösungen die maximale Häufigkeit, zwischen der es eine kurze Lösung, zwei kurze Lösungen usw. gibt.


5. Gibt es in der allgemeinen Liste aller Lösungen ein Muster für die Position der Komplettlösungen?


Um diese Frage zu beantworten, haben wir fortlaufende Listen aller Lösungen für die Werte n = (7, ..., 16) analysiert. Um die erhaltenen Ergebnisse klar zu veranschaulichen, wird in 5 für den Wert n = 8 ein Diagramm dargestellt, in dem die Länge jeder Lösung in der Liste aller 736-Lösungen nacheinander angegeben ist. Hier sind nur 92 Lösungen vollständig und sie sind rot hervorgehoben, die restlichen 644 Lösungen sind kurz und blau hervorgehoben. Es ist ersichtlich, dass die Komplettlösungen in der Liste aller Lösungen nicht gleichmäßig verteilt sind. Es gibt Bereiche, in denen Komplettlösungen häufiger sind, und es gibt Orte, an denen Komplettlösungen selten oder gar nicht gefunden werden.



Abb. 5: Die Länge jeder Entscheidung in einer sequentiellen Liste aller Entscheidungen für eine Matrix der Größe 8 x 8 (rot - volle Lösungen, blau - kurze Lösungen). Die Gesamtzahl aller Lösungen beträgt 736

Ein anderes ist hier jedoch wichtig. Wenn Sie sich das Bild genau ansehen, das einem blau-roten Barcode ähnelt, können Sie ein sehr wichtiges Merkmal sehen: Alle roten Linien sind symmetrisch um eine bestimmte, bedingte vertikale Linie, die durch die Mitte der Lösungsliste verläuft. Wie die Überprüfung zeigt, wird, wenn beim i-ten Schritt vom Beginn der allgemeinen Liste eine vollständige Lösung vorliegt, die vollständige Lösung dementsprechend notwendigerweise im Schritt m-i + 1 erkannt. Wenn zum Beispiel für n = 8 die erste vollständige Lösung in der sequentiellen Suche für alle Lösungen im 43. Schritt erscheint, wird dementsprechend die letzte vollständige Lösung in der Liste in Schritt 736-43 + 1 = 694 erkannt. Wenn die 17. Lösung für eine 10 × 10-Matrix in der Liste beim 368. Schritt erscheint, erscheint die vollständige Lösung, die dazu symmetrisch ist, in der Liste aller Lösungen in Schritt 12774-17 + 1 = 12407. Diese Regel gilt für eine Matrix von Lösungen beliebiger Größe. Daher können wir eine Regel formulieren.Wenn für jeden Wert von n in einer sequentiellen Liste aller Entscheidungen an der i-ten Position vom Anfang der Liste die Lösung vollständig ist, dann ist auch eine symmetrische Lösung vom Ende der Liste, die sich in der Position m-i + 1 befindet, vollständig (die Symmetrie der Entscheidungen). Hier bedeutet m, wie oben erwähnt, die Anzahl aller Lösungen. Die Folge dieser Regel ist die Tatsache, dass für jeden Wert von n die Anzahl der Komplettlösungen immer eine gerade Zahl ist . (Alle Größen der Liste der bisher gefundenen Komplettlösungen sind gerade Zahlen).


Wenn wir die Indizes zweier symmetrischer Lösungen vergleichen, können wir ein grundlegendes wichtiges Merkmal finden - symmetrische Lösungspaare ergänzen sich. Die Summe der entsprechenden Werte der Indizes der Königinnen symmetrischer Lösungen ist gleich n + 1 . Zum Beispiel befindet sich die 17. Lösung für n = 10 in der Liste aller Lösungen im 368. Schritt vom Anfang der Liste und die Queen-Positionsindizes in diesem Schritt sind (1, 5, 7, 10, 4, 2, 9, 3, 6, 8).


Die entsprechende symmetrische Lösung befindet sich in Schritt 12407 und weist Indizes der Königinpositionen (10, 6, 4, 1, 7, 9, 2, 8, 5, 3) auf. Wenn wir die entsprechenden Werte der Indizes jedes Paares addieren, erhalten wir (11, 11, ..., 11). Diese Regel gilt für jeden Wert von n und darüber hinaus sowohl für vollständige symmetrische Lösungen als auch für kurze symmetrische Lösungen. Dies erlaubt uns, die zweite Regel zu formulieren. Für eine Lösungsmatrix beliebiger Größe n sind alle Lösungspaare (sowohl kurz als auch vollständig), die symmetrisch in der sequentiellen Liste aller Entscheidungen angeordnet sind, komplementär - die Summe der Indizes der Positionen der entsprechenden Zeilen ist konstant und entspricht n + 1 (die Entscheidungskomplementaritätsregel). Wenn mit Q (i) und Q1 (i) bezeichnet - Reihen von Indizes komplementärer Lösungen, dann gilt die Regel


           <b>`Q ( i ) + Q1 ( i ) = n + 1,    i = (1, n) `</b>

Dies bedeutet im Allgemeinen , dass , wenn eine vollständige Lösung auf dem i - ten Schritt wird das auf diese Weise symmetrische Komplettlösung in Schritt bekannt m - i +1. Bei der Suche nach Komplettlösungen genügt es daher, nur die erste Hälfte aller Komplettlösungen zu finden. Die zweite Hälfte der Liste der Komplettlösungen kann aus den bereits erhaltenen Lösungen auf der Grundlage der Komplementaritätsregel bestimmt werden. Das Kriterium, dass die Hälfte der Liste der Komplettlösungen erreicht wurde, ist die Erfüllung der Komplementaritätsregel zwischen der vorherigen Gesamtlösung Q (i-1) und dem nachfolgenden Q (i) . dh es ist notwendig, dass die Summe jedes Paares entsprechender Werte der Indizes von zwei aufeinander folgenden Lösungen gleich n + 1 ist. Da jede Komplettlösung aus der Liste aller Komplettlösungen einzigartig ist, werden sich nur die aufeinanderfolgenden Komplettlösungen ergänzen, die sich auf beiden Seiten der Grenze befinden und die Liste in zwei Hälften teilen.


Wenn in der Zukunft nach allen Komplettlösungen für jeden nächsten Wert von n gesucht wird, werden diese beiden Regeln die Berechnungsmenge und entsprechend die Zählzeit um den Faktor zwei reduzieren.


6. Visualisierung der Reihenfolge der Schritte, um die erste vollständige Lösung zu finden.


Wie erfolgt die Durchführung der Schritte vorwärts (Vorwärtsverfolgung) und vorwärts (Rückwärtsverfolgung), wenn der Entscheidungssuchzweig gebildet wird? Um diese Frage zu beantworten, haben wir für eine 10 x 10-Matrix die Reihenfolge der anfänglichen 194-Übergänge zwischen Zeilen vor dem Auftreten der ersten vollständigen Lösung bestimmt. Die entsprechende Grafik ist in Abbildung 6 dargestellt. Die blauen Linien zeigen die Bewegung nach vorne und die roten Linien - kehren zurück. Während dieser 194 Schritte wurden 35 kurze Lösungen erstellt. Aus der Figur ist ersichtlich, dass die meisten Übergänge (84,5%) zwischen den Linien (5, 6, 7, 8) auftreten. Es ist eine Art „Engpass“ auf dem Weg zum „Ziel“. Wie aus der Figur hervorgeht, gibt es nur sieben Übergänge zur vierten Reihe und einen Übergang zur dritten Reihe. Es gibt auch 13 Übergänge zur 9. Reihe. Drei Versuche, in die 10. Zeile zu gelangen, waren erfolglos, da in diesen Suchzweigen in der 10. Zeile keine freie Position vorhanden war. Dieses Beispiel zeigt deutlich alle Zweige der Kurzbildung



Abb.6 Visualisierung von Backtracking (rot) und Forwardtracking (blau) Ereignissen für die ersten 194 Suchschritte (n = 10)

Entscheidungen treffen, bevor Sie die erste vollständige Lösung erhalten. Jeder Algorithmus zur Lösung eines solchen Problems ist wirksam, wenn er einen Mechanismus enthält, mit dem Sie alle (oder Teile) der Zweige ausschließen können, die zu kurzen Lösungen führen.


7. Nach wie vielen kurzen Lösungen erscheint die erste Komplettlösung?


In Anbetracht der Tatsache, dass Komplettlösungen an verschiedenen Stellen der Liste aller Lösungen ungleich erscheinen, erscheint es wichtig, herauszufinden, wie viele Kurzlösungen als erste Komplettlösung erscheinen, wenn Sie nacheinander nach allen Lösungen suchen. Zu diesem Zweck wurden für die Werte n = (7, ..., 35) alle kurzen Lösungen vor dem Auftreten der ersten vollständigen Lösung sequentiell berechnet. Wie aus Fig. 7 ersichtlich ist, die ein Diagramm der Abhängigkeit von n zeigt, dem natürlichen Logarithmus der Schrittzahl, als die erste vollständige Lösung erschien, erscheint für gerade Werte von n die erste vollständige Lösung viel später als für die nächsten ungeraden Werte von n. Beispielsweise erscheint für einen ungeraden Wert n = 21 die erste vollständige Lösung bei Schritt 3138, und für den nächsten, geraden Wert n = 22 erscheint die erste vollständige Lösung bei Schritt 628169. Dementsprechend wird für Folgendes



Abb. 7. Die Anzahl der kurzen Entscheidungen vor dem Auftreten der ersten vollständigen Lösung für verschiedene Werte von n

Die Anzahl der Iterationsschritte für gerade n = 22 beträgt das 200,2- bzw. 68,6-fache der nächsten ungeraden Werte. Besonders visuell zur Zählzeit äußert sich dies für n = 34. Hier erscheint die erste vollständige Lösung bei 826.337.184. Schritt und für die nächsten ungeraden Zahlen (33, 35) bei 50.704.900. Und 84.888.759. Schritten. Es sollte auch über die Verletzung der Monotonie des Wachstums der Anzahl kurzer Lösungen vor dem Erscheinen der ersten vollständigen Lösung mit zunehmendem n gesprochen werden. Bei geraden Werten von n geschieht dies, wenn n = 19 ist, bei ungeraden, wenn n = 24 und n = 26.


8. Ist die Häufigkeit der Zellen jeder Zeile in der Liste aller Komplettlösungen gleich?


Die Entscheidungsmatrix der Größe nxn, die als Analogon eines Schachbretts dient, ist wie eine Szene, in der alle Ereignisse auftreten. Jede in dieser Szene gebildete Komplettlösung besteht aus Zellindizes unterschiedlicher Reihen Jede dieser Zellen ist ein Knoten im Lösungssuchzweig. Die Frage, die uns interessieren wird, ist folgende: Ist die Belastung jeder Zeile für verschiedene Zellen gleich, wenn eine Liste aller Komplettlösungen erstellt wird? Je höher die Frequenz ist, desto höher ist die Aktivität einer gegebenen Zelle bei der Bildung einer Liste vollständiger Lösungen. Um dies festzustellen, definieren wir für jede Zeile basierend auf der Liste aller Komplettlösungen die relative Häufigkeit der verschiedenen Indizes. Zuerst analysieren wir für eine Lösungsmatrix der Größe n = 8. Betrachten Sie nacheinander jede Zeile des Speicherarrays der Komplettlösungen und bestimmen Sie die Häufigkeit der verschiedenen Indexwerte. In den Tabellen 2 sind die entsprechenden Werte der absoluten Aktivitätshäufigkeiten verschiedener Zellen in jeder der acht Reihen dargestellt. 8


Tabelle 2. Die absolute Aktivitätshäufigkeit der Zellen in jeder der acht Reihen der 8x8-Lösungsmatrix, erhalten aus der Analyse der Liste aller vollständigen Lösungen

Zeile \ col 1 2 3 4 5 6 7 8
1 4 8 16 18 18 16 8 4
2 8 16 14 8 8 14 16 8
3 16 14 4 12 12 4 14 16
4 18 8 12 8 8 12 8 18
5 18 8 12 8 8 12 8 18
6 16 14 4 12 12 4 14 16
7 8 16 14 8 8 14 16 8
8 4 8 16 18 18 16 8 4

Eine Gruppe von 4 Diagrammen wird dargestellt, wobei jeder Graph die Änderung der relativen Häufigkeiten innerhalb einer einzelnen Linie kennzeichnet. Eine der grundlegend wichtigen Schlussfolgerungen, die auf der Grundlage der Analyse aller gewonnenen Daten getroffen werden können, lautet wie folgt:


  • für eine Matrix von Lösungen beliebiger Größe n stimmt die Aktivität der Zellen der i- ten Zeile mit der Aktivität der Zelle n-i + 1 überein , d. h. Die Aktivität der Zellen der ersten Reihe stimmt immer mit der Aktivität der Zellen der letzten Reihe überein, die Aktivität der Zellen der zweiten Reihe stimmt mit der Aktivität der Zellen der vorletzten Reihe überein.

    Wenn n ungerade ist, hat nur die mittlere Zeile der Lösungsmatrix kein symmetrisches Paar. Für alle anderen Zellen gilt die obige Regel
  • Nennen wir dies "die Eigenschaft der horizontalen Symmetrie der Aktivität von Zellen verschiedener Reihen der Lösungsmatrix" . Aus diesem Grund haben wir nur 4 Diagramme für eine Matrix der Größe n = 8 präsentiert, da die entsprechenden Zellaktivitätsdiagramme für die Zeilen (1, 8), (2.7), (3.6) und (4.5) völlig identisch sind.

Es ist auch zu beachten, dass die Frequenzwerte symmetrisch um die vertikale Achse der Teilungsmatrix in zwei gleiche Teile (im Fall eines geraden Wertes von n) oder durch die Mediansäule (im Fall eines ungeraden Werts von n) liegen. Nennen wir dies "die Eigenschaft der vertikalen Symmetrie der Aktivität von Zellen verschiedener Reihen der Lösungsmatrix" .


Wie aus der Analyse von Tabelle 2 hervorgeht, sind die Frequenzen in der Matrix der Lösung außerdem bezüglich der linken und rechten Hauptdiagonalen symmetrisch.



Abb.8: Die Aktivität der Zellen der entsprechenden Zeilen bei der Erstellung der Liste der Komplettlösungen, n = 8

Ich denke, dass das Vorhandensein restriktiver Regeln bei der Formulierung des Problems und die damit verbundene Eigenschaft des Nicht-Determinismus eine Art harmonische Beziehung zwischen Knoten in verschiedenen Linien bilden. Die Zweige der Suche, die in diese Regeln passen, führen zur Bildung einer vollständigen Lösung. Die verbleibenden Zweige der Suche verstoßen in einem gewissen Schritt gegen diese Regeln und „schließen ihren Weg“ in Form von kurzen Entscheidungen ab. Hierbei ist zu beachten, dass die Zellen der Entscheidungsmatrix nur eine lokale Beziehung innerhalb der Projektions-Einflussgruppe haben. Es gibt keine vorgeschriebenen Regeln für koordinierte Aktionen zwischen ihnen. Die kollektive Aktivität der Zellen ist nur eine Folge der Auswirkungen der restriktiven Regeln. Daher bleibt es eine offene, interessante Frage, wie einschränkende Regeln als Nicht-Determinismus-Faktoren betreffen die Zellen der Entscheidungsmatrix, was letztendlich zur Bildung einer "harmonischen" Matrix der Aktivität der Zellen führt - symmetrisch um die horizontale und vertikale Achse sowie um die linke und rechte Diagonale. Ist dies nur eine charakteristische Eigenschaft einer bestimmten Aufgabe oder besteht sie auch für andere nicht deterministische Probleme?


9. Von welcher Zeilennummer aus kann der Vorwärtsverfolgungsalgorithmus aktiviert werden


Wenn Sie die Arbeit des Algorithmus für die sequentielle Auswahl von Zeilen in der Entscheidungsmatrix für den Ort der Königin verfolgen, können Sie dies ab einer bestimmten Linie, die wir "StopRow" nennen, sehen. Der Vorgang des Vorwärtsbewegens ist "gebremst". Im Suchzweig ist eine solche Zeile die erste, bei der Probleme mit dem Vorhandensein von free auftreten



Abb. 9-1 Abhängigkeit des Verhältnisses des StopRow-Index zu n von der Größe der Entscheidungsmatrix (Teil-1)

Position für die Position der Königin. Aus dieser Zeile wird der Back-Tracking-Algorithmus aktiviert, um Spuren vorher durchgeführter Aktionen zu löschen und zurück zu gehen. In dieser Zeile erscheint die erste kurze Entscheidung.



Abb.9-2 Abhängigkeit des Verhältnisses des StopRow-Index zu n von der Größe der Lösungsmatrix (Teil-2)

Der Index der Zeile „StopRow“, ab der die Schwierigkeiten beim Voranschreiten beginnen, hängt von der Größe n der Entscheidungsmatrix ab. Betrachtet man das Verhältnis dieses Index, das wir mit StopInd bezeichnen, zur Größe der Matrix der Lösung n, so schwankt dieses Verhältnis, wie aus Abbildung 9-1 ersichtlich, wo die Berechnungsergebnisse für die Anfangswerte n = (7, ..., 99) dargestellt werden, mehr oder weniger Seite und neigt dazu, abzunehmen. Bei einer Erhöhung des Wertes von n = (100, ..., 300) schwankt dieses Verhältnis innerhalb von 0,619 - 0,642 (9-2), und bei einer weiteren Erhöhung von n werden die folgenden Ergebnisse erhalten (die Werte von n werden nacheinander angegeben, und StopInd und das Verhältnis StopInd / n: 1000 (619, 0,6190), 2000 (1239, 0,6195), 3000 (1856, 0,6187), 4000(2473, 0,6182), 5000 (3091, 0,6182). Überraschenderweise kann argumentiert werden, dass die Stopplinie die Entscheidungsmatrix nach der Golden-Section-Regel teilt : Das StopInd / n- Verhältnis unterscheidet sich nämlich von (n-StopInd) / StopInd um einen kleinen Betrag, der mit zunehmendem n zu null tendiert. Beispielsweise beträgt für n = 5000 die Differenz zwischen den Verhältnissen 3091/5000 und 1909/3091 0,006, was weniger als 0,1% des Durchschnitts dieser beiden Verhältnisse beträgt.


Die Grafik ist in zwei Abbildungen dargestellt. 9- (1,2) hat eine nicht zufällige Form der Variabilität, die der Aufnahme auf der "Musikmusikband" ähnelt. Man kann wiederholte Sprünge nach oben sehen und einen abgestuften Abfall mit unregelmäßiger Periodizität. Offensichtlich gibt es einen bestimmten Grund für ein solches Verhalten der Kurve, und möglicherweise ist dies für die Studie von Interesse. Aus diesem Grund wurde der Graph zwecks detaillierterer Visualisierung in zwei Abbildungen dargestellt.


Ich habe nur einen Teil der Fragen betrachtet, die auf der Grundlage der Ergebnisse der Lösung des Problems „über die Verteilung von n-Königinnen“ formuliert werden können. Ich hoffe, dass die Ergebnisse transparenter werden, um die Mechanismen der Bildung nicht deterministischer Prozesse und Veränderungen im Zustandsraum zu verstehen. Vielleicht wird dies als Grundlage für die Formulierung neuer Aufgaben und den weiteren Weg dienen.


Fazit


  • Wenn wir beim Durchsehen der Publikation zu der Schlussfolgerung gelangt sind, stellt sich natürlich die Frage: "Was ist die One Billion Queens Problem-Lösung im Titel des Artikels?" Als ich die Publikation für Habr vorbereitete, dachte ich, dass eine Person, die zum Beispiel eine Mine besitzt, in der Diamanten abgebaut werden, mindestens einen Diamanten an Freunde und Verwandte spenden sollte, andernfalls wäre das unfair. Daher möchte ich allen Mitgliedern der habr-community ein Geschenk machen: Teilnehmer, Organisatoren, Besucher. Wie der Name schon sagt, ist dies eine Lösung für das Problem der Verteilung von einer Milliarde Königinnen auf einem Milliarden-Milliarden-Schachbrett.

    Natürlich ist dies kein facettierter Diamant, aber für wahre Kenner der intellektuellen Kunst kann es wertvoller sein als "irgendeine Art Diamant". Darüber hinaus gibt es weltweit viele verschiedene Diamanten, und diese Lösung ist bisher nur in einer Kopie erhältlich. Und sieht unseren Byte-Gott (*), dass ich es aufrichtig mache.
    Die resultierende Lösung ist ein eindimensionales Array, das aus einer Milliarde Zahlen besteht und im MatLab .mat-Format dargestellt wird. Es ist verfügbar unter: One Billion Queens Problemlösung bei Google Drive
    - Das erste Element dieses Arrays kennzeichnet die Position der Dame in der ersten Zeile, das zweite Element - die Position in zweite Zeile usw. Dies ist nur eine Lösung von nBillion möglichen Lösungen. Und der Wert von nBillion ist so groß, dass man ihn als nahen Verwandten der Unendlichkeit betrachten kann.
  • Es scheint mir, dass diese Lösung der Kategorie der virtuellen intellektuellen Werte zugeordnet werden kann. Wir können sagen, "das ist etwas, in dem etwas ist." Sie können nicht wirklich berührt werden und werden im Bewusstsein nur auf der Ebene der Empfindungen wahrgenommen. In der Tat gibt es eine erstaunliche Ordnung und explizite und implizite Harmonie. Dies ist ein rein symbolisches Geschenk (im wörtlichen und im übertragenen Sinne), das an alle Mitglieder der Gemeinschaft gerichtet ist. Ich denke, " Sie sind nicht wie alle anderen ."

    (Ich hoffe, dass jemand "das Geschenk nach Hause nimmt". Die Datei ist ziemlich groß - 3,7 GB. Dies sind saubere, verifizierte Daten. Die Tatsache, dass Google Drive Warnungen anzeigt - behandeln Sie dies mit Verständnis.)
  • Bevor ich diese Entscheidung traf, dachte ich über die individuelle kollektive Natur eines solchen Geschenks nach. Stellt sich nicht heraus, dass das Original einem und der Rest der Kopie übergeben wird? Die Lösung war jedoch einfach. Die bekannten Begriffe des „Alltags“ von „Original“ und „Kopie“ verlieren dabei ihre Bedeutung. Wir kopieren nicht und erstellen ein anderes Original. Und die "Originale" für alle sind gleich und gleichwertig.
  • Ich denke, in der Gesellschaft von Verwandten werden Sie höchstwahrscheinlich der einzige sein, der ein solches "intellektuelles Produkt" als Geschenk erhalten hat. Es würde Spaß machen, wenn Sie Ihrer Schwiegermutter von einem solchen Geschenk erzählen: "Stellen Sie sich ein Schachbrett einer Mutter vor, das 50.000 km pro 50.000 km misst und auf dem 1 Milliarde Königinnen so verteilt sind, dass man einander nicht in Ruhe sieht ..." Wer weiß, vielleicht wird sein Schwiegersohn danach mehr zu schätzen wissen, da ihm ein so seltsames Geschenk gemacht wird.

Ich wünsche allen Mitgliedern der habr-Gemeinschaft Gesundheit, Erfolg und Wohlbefinden. Möge das neue Jahr uns allen viel Glück bringen.


(*) - Da ich auf den Namen eines Objekts Bezug genommen habe, sollte auch dessen Beschreibung angegeben werden.
Bytegott bedeutet eine mehrdimensionale Entität, bestehend aus Nullen und Einsen, rational in allen Richtungen und unendlich in alle Richtungen. Jede Folge von Nullen und Einsen in diesem Bereich steht für gewisses Wissen.


Referenzliste


[4] Max Bezzel, Vorschlag des 8-Damen-Problems ", Berliner Schachzeitung, Band
3 (1848), Seite 363. (Eingereicht unter dem Autorennamen \ Schachfreund".)


[5] Franz Nauck, Briefwechseln mit allen fur alle ", Illustrirte Zeitung, Band
377, Nummer 15 (1850), Seite 182.


[6] Bell Jordan; Stevens Brett (2009). "Ein Überblick über bekannte Ergebnisse und Forschungsbereiche für n-Königinnen". Diskrete Mathematik. 309 (1): 1–31


[7] Gent, Ian P .; Jefferson, Christopher; Nachtigall, Peter (August 2017). "Komplexität der n-Queens-Vollendung". Journal of Artificial Intelligence Research. AAAI Drücken Sie. 59: 815–848


[8] W. Kosters und alle, n-Queens - 342 Referenzen (20. November 2018)


[9] NJA Sloane, die Online-Enzyklopädie ganzzahliger Sequenzen, elektronisch veröffentlicht. 2016


Jetzt auch beliebt: