Wie kann man einen Algorithmus zur Bestimmung der domination number für das Damenproblem implementieren?

Beim Damenproblem wird mit domination number die Anzahl an Damen bezeichnet, die man mindestens benötigt, um das gesamte Schachbrett zu beherrschen. In Entwicklung eines brute force Algorithmus für das Damenproblem wurde ein brute-force-Algorithmus entwickelt, der zu einer gegebenen Seitenlänge n des Schachbrettes alle Möglichkeiten durchspielt, k Damen auf dem Feld zu plazieren und zählt, wie viele dieser Möglichkeiten das Damenproblem lösen.

Zur Bestimmung der domination number in Abhängigkeit von n ist es natürlich unsinnig, diesen brute-force-Algorithmus einzusetzen. Wie könnte ein Algorithmus aussehen, der die domination number oder zumindest eine gute Approximation berechnet?

In Entwicklung eines brute force Algorithmus für das Damenproblem wurden einige Lösungen des Damenproblems diskutiert; dabei hat sich gezeigt, dass die Lösungen symmetrisch sind, wenn es nur sehr wenige Lösungen gibt (siehe die Ergebnisse für n = 6, n = 10 und n = 11). Es ist daher naheliegend anzunehmen, dass man eine "kleine Menge" an symmetrischen Konstellationen angeben kann, unter denen sich die Lösungen des Damenproblems befinden müssen oder zumindest mit hoher Wahrscheinlichkeit befinden. Kann man dies zu einer schnellen Suche nach der domination number verwenden?

Alle Kommentare
Durch die Nutzung dieser Website erklären Sie sich mit der Verwendung von Cookies einverstanden. Unsere Datenschutzbestimmungen können Sie hier nachlesen