Kann man den brute force Algorithmus zur Lösung des Damenproblems beschleunigen?

In Entwicklung eines brute force Algorithmus für das Damenproblem wird ein brute-force-Algorithmus entwickelt, der das Damenproblem löst. Wobei hier mit Damenproblem gemeint ist: Es sollen gerade so viele Damen auf einem n × n-Schachbrett aufgestellt werden, dass sie das gesamte Schachbrett beherrschen.

Der Algorithmus soll folgende Forderungen erfüllen:

  1. Er soll alle Möglichkeiten untersuchen, die Damen auf dem Schachbrett zu plazieren, und jeweils feststellen, ob sie das gesamte Schachbrett beherrschen.
  2. Er soll die Lösungen in irgendeiner Form ausgeben oder abspeichern.
  3. Er soll die Anzahl der Lösungen und die Anzahl der durchprobierten Möglichkeiten angeben.

Der Algorithmus, der entwickelt wurde, beruht auf der Verwendung der Funktion combn() zur Iteration über alle Möglichkeiten und einer selbstgeschriebenen Funktion isSolution(), die innerhalb von combn() aufgerufen wird.

Gibt es eine Möglichkeit die Funktionalitäten des brute-force-Algorithmus beizubehalten, aber dafür zu sorgen, dass er deutlich schneller abgearbeitet wird? (Die Berechnung der Adjazenz-Matrix kann mit Sicherheit vereinfacht und beschleunigt werden. Da sie aber nur einmalig berechnet wird, ist sie für die Rechenzeit nicht maßgeblich.)

Alle Kommentare
Durch die Nutzung dieser Website erklären Sie sich mit der Verwendung von Cookies einverstanden. Außerdem werden teilweise auch Cookies von Diensten Dritter gesetzt. Genauere Informationen finden Sie in unserer Datenschutzerklärung sowie im Impressum.