"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.

Suchbaum

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).