vorige nächste Programm

Das Problem der acht Damen


Im folgenden Text soll nun gezeigt werden, dass man auch mit den einfachen Suchverfahren der Tiefensuche oder Breitensuche das gegebene Problem lösen kann, aber es soll auch die prinzipielle Erweiterbarkeit des Problems mit den sich daraus ergebenden prinzipiellen Problemen betrachtet werden.

Der erste Schritt zur Lösung des Problems führt auf die Frage nach der Datenstruktur, in der die Belegung des Spielfeldes gespeichert werden soll. Der erste naheliegende Ansatz ist, das Feld als Array zu betrachten, die Positionen im Feld lassen sich dann mit Koordinatenpaaren identifizieren. Verwendet man tatsächlich ein 8 x 8 Array, dann würde jede Position die Information tragen, dass sie mit einer Dame belegt ist der nicht. Damebrett

In Scheme ist eine Liste naheliegender. Bleibt man beim Grundkonzept eines Arrays mit 8 x 8 Feldern, die mit ihren Koordinaten zu beschreiben sind, dann ist eine Liste der Form

[ (1 . 1)    (2 . 3)    (3 . 5)    (4 . 8)    (5 . 4)    (6 . 7)    (7 . 2)    (8 . 6) ] .

eine mögliche Belegung mit Damen. Ob sie allerdings zulässig ist, sei hier noch dahin gestellt. Es werden nun also nur die Koordinaten der Positionen angegeben, die belegt sind.

Nun ergibt sich nach dem Prinzip des Generate and Test folgende sehr primitive "Lösung" des Problems:

Nach diesem Prinzip arbeitet das angegebene Programm: Startet man dieses Programm, kann man "ziemlich lange warten" ! Woran liegt das ?

 


 

 

Anmerkung zum Begriff Suchraum

Der Begriff Suchraum ist hier unglücklich gewählt, da er als Fachausdruck festgelegt ist: Mit dem Begriff Suchraum bezeichnet man die Menge aller möglichen Zustände des Systems. Beim Problem der Acht Damen sind das z.B. die im zweiten Satz angegebenen möglichen Kombinationen.

Wenn Sie Verständnisprobleme fürchten, ersetzen Sie den Begriff durch einen anderen.