"Grundkurs Programmieren in Java - Band 1 (3. Auflage, 2006)"
2001-2007, Carl Hanser Verlag
Lösungsvorschlag zu Aufgabe 7.4 (Version 4.0)
(c) 2001-2007 D. Ratz, J. Scheffler, D. Seese, J. Wiesenberger
a)
Ersetzt man
setze( brett, spalte+1 );
durch
setze( brett, ++spalte );
so findet das Programm keine einzige Lösung.
Wenn die Methode setze innerhalb der for-Schleife zum v-ten Mal
aufgerufen, so werden damit (v-1) Spalten übersprungen (wobei in
diesen (v-1) Spalten die Damen sich an unzulässigen Positionen befinden).
b)
Damit das Programm nicht nach der ersten gefundenen Lösung bereits abbricht,
müssen Sie einfach die Zeilen 42 und 43 auskommentieren:
if (success) // falls es geklappt hat
return true;
Insgesamt gibt es 92 Lösungen.
Am Ende der ausgabe-Methode sollte man noch mittels
System.out.println();
eine Leerzeile ausgeben, damit nicht alle Lösungen aneinander geklebt
werden. Zudem macht auch ein Zähler für die Anzahl der gefundenen Lösungen
Sinn.
Quelltext: AchtdamenAlle.java
Hinweis:
Man kann rekursive Algorithmen anhand eines Baumes anschaulich darstellen. Dazu wollen
wir der Einfachheit halber von einem 2x2-Schachbrett ausgehen (hier gibt es keine zulässige
Lösungs-Konstellation). Jeder Knoten in solch einem Baum stellt in unserem Fall
eine (unvollständige) Schachbrett-Konstellation dar.
Beim Übergang von der i-ten zur (i+1)-ten Ebene des Baumes
wird jeweils die Position der Dame in einer i.ten Spalte bestimmt. Da wir jeweils alle beide
Möglichkeiten ausprobieren, hat jeder Knoten in unserem Baum (bis auf die Blätter in der
untersten Ebene) genau zwei Söhne. Der linke Sohn soll immer zusätzlich die
Dame in der oberen Position, der rechte Sohn immer in der unteren Position haben.
Die einzelnen Knoten entsprechen folgenden Schachbrett-Konstellationen:
(1)
| | |
| | |
(2) (3)
|D| | | | |
| | | |D| |
(4) (5) (6) (7)
|D|D| |D| | | |D| | | |
| | | | |D| |D| | |D|D|
Es macht selbstverständlich keinen Sinn, immer den vollständigen Baum
zu konstruieren (das Programm tut dies auch nicht).