Ein nicht-rekursiver, speichereffizienter blindes Verfahren zur Suche aller möglichen Lösungen des N-Damen-Problems

Das N-Damen-Problem ist das Problem, N Schachdamen auf ein NxN-Schachbrett so zu platzieren, dass sich keine von ihnen gegenseitig bedroht. Eine Schachdame kann horizontal, vertikal und diagonal bewegen. Daher müssen die Nachbarn einer Dame so angeordnet werden, dass in diesen drei Richtungen keine Kollision auftritt. Wissenschaftler akzeptieren die Tatsache, dass der Verzweigungsgrad annähernd linear ansteigt. Mittels künstlicher Intelligenz basierender Suchstrategien wie Breiten-First-Search (BFS), Tiefen-First-Search (DFS) und Rückverfolgungs-Algorithmen haben viele Akademiker dieses Problem untersucht und mehrere Techniken zur Berechnung möglicher Lösungen für das N-Damen-Problem entwickelt. Lösungsansätze, die einen blinden Ansatz verfolgen – also ungefähre Suchverfahren wie BFS und DFS – verwenden Rekursion. Ebenso setzt der Rückverfolgungsansatz Rekursion zur Lösung dieses Problems ein. Alle diese rekursiven Algorithmen nutzen einen Systemstapel, der begrenzt ist. Daher erschöpft sich der Speicher bereits bei kleinen Werten von N schnell, wobei dies von der jeweiligen Hardware abhängt. In dieser Arbeit wird das oben genannte Problem behandelt und ein nicht-rekursiver, auf DFS basierender Ansatz vorgeschlagen, um den System-Speicher zu schonen. In dieser Studie wird der Tiefen-First-Search (DFS) als blinder oder ungeklärter Suchansatz eingesetzt. Die experimentelle Untersuchung liefert beachtliche Ergebnisse hinsichtlich Zeit- und Speicheraufwand.