Zur MathePrisma-Startseite
Zur Modul-Startseite  


Backtracking (Damen 2 )
 

  

 
 
 
 Auch das n-Damen-Problem kann man systematisch mittels Backtracking lösen:

  • Bei einer Lösung steht in jeder Spalte des Brettes genau eine Dame.
  • Die Lösung kann durch eine Folge von Entscheidungen gefunden werden:
    die i-te Entscheidung legt die Position der Dame in der i-ten Spalte fest.
 
Wieviele Möglichkeiten gibt es für die i-te Entscheidung?
 
i
1
n
n-i

Und wann ist eine Entscheidung erkennbar falsch?
 
wenn die Position von einer der bereits gesetzten Damen
    bedroht wird
wenn die neue Dame eine der bereits gesetzten bedroht
wenn die neue Dame auf ein Feld einer anderen Farbe
    als die zuletzt gesetzte kommt
wenn in der Spalte noch ein weiteres Feld unbedroht ist
 
 
 
 Hier ist die Verwendung von Backtracking vorgeschrieben.
  • Es gibt immer nur genau ein Feld ('das richtige'), das du anklicken sollst. Dabei wird eine Dame gesetzt oder entfernt).
  • Erkennbar falsche Entscheidungen sollst du gar nicht erst treffen.
  • Die möglichen Entscheidungen für die Position in eine Spalte werden immer in der Reihenfolge 'von oben nach unten' gefällt.
 
 
 Wenn du das Prinzip verinnerlicht hast, bearbeite folgende Aufgabe.
 
Ordne die Zeilen so in das obere Feld ein, dass ein korrekter Backtracking-Algorithmus für das n-Damen Problem beschrieben wird.
Achtung: Du musst jede Zeile auch richtig einrücken.

 
 
 Und hier findest du die  elegante Version
 
Seite 7/10