Damen

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche
Kurzinfo

Vista-kdmconfig.png
Bei dieser Seite handelt es sich um eine Projekt-, Kurs- oder Klassenseite.

Lösung des n-Damen-Problems

Aufgabe 1

Das n-Damen-Problem besitzt in der Regel mehrere Lösungen. Wir nennen zwei Lösungen wesentlich verschieden, wenn sie nicht durch Rotation oder Spiegelung auseinander hervorgehen.

a)Gib alle Lösungen des 4-Damen-Problems an. Gibt es wesentlich verschiedene Lösungen?

Antwort:

Nein es gibt keine wesentlich verschiedenen Lösungen, da die Lösungen einfach nur Spiegelungen an einer imaginären Achse sind!

Bild Damen1_2

b)Gib zwei wesentlich verschiedene Lösungen des 5-Damen-Problems an.

Antwort:

Hier kann keine Spiegelung erkannt werden => 2 wesentlich verschiedene Lösungen!

Bild Damen_3Bild Damen_4

c)Wie muss man den Backtracking-Algorithmus für das n-Damen-Problem modifizieren, damit er alle Lösungen bestimmt? Schreibe dazu den modifizierten Algorithmus (rekursiv oder nicht-rekursiv) im Detail auf.

Antwort:

falls i = (n+1)

    stop 

sonst

    für alle Felder der i-ten Spalte 
         falls Feld nicht bedroht 
              setze Dame auf Feld 
              N-DamenRek(i+1)

Aufgabe 2

Mit welchem Wert für i muss man den rekursiven Algorithmus N-DamenRek(i) starten?

Antwort:

Mit 1 oder 0, da der Wert immer um 1 erhöht wird und nicht erkannt wird, ob man in der Mitte anfängt oder nicht, wenn man jetzt z.B. in der letzten Spalte anfinge, würde das Programm scheitern, da es nicht genug freie Felder/Spalten bei i+1 gäbe!