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?
b) Gib zwei wesentlich verschiedene Lösungen des 5-Damen-Problems an.
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.
Mit welchem Wert für i muss man den rekursiven Algorithmus N-DamenRek(i) starten?
Formuliere einen rekursiven und einen nicht-rekursiven Backtracking-Algorithmus für das Spiel Quinto.
Wir haben uns bei den hier behandelten Aufgaben nie überlegt, ob es überhaupt eine Lösung gibt.
a) Hat das n-Damen-Problem für n=3 eine Lösung? (Begründung!)
b) Hat Quinto für die Größe 3 eine Lösung?
c) Wie muss man die Backtracking-Algorithmen (nicht-rekursiv und rekursiv) abändern, dass sie die Information 'es gibt keine Lösung' ausgeben?
Bearbeite das MathePrisma-Modul 'Vierfarbenproblem'.
Beschreibe in eigenen Worten die Aufgabenstellung und eine nicht-rekursive
sowie eine rekursive Variante eines Backtracking-Algorithmus, welcher
für eine gegebene Karte eine gesuchte Einfärbung findet.