Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:8-damen-problem:start [25.02.2025 07:40] – Frank Schiebel
+++ faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:8-damen-problem:start [25.02.2025 14:44] (aktuell) – [Algorithmus unplugged] Frank Schiebel
@@ Zeile 9: / Zeile 9: @@
 ==== Algorithmus unplugged ====
-Wie würde man das Problem algorithmisch lösen? Am besten probiert man es einmal ohne PC an einem normalen Schachbrett aus - wenn du keines zur Hand hast, kannst du [[https://info-bw.de/static/h5p/8-damen-problem.html|diese Aktivität im Browser]] verwenden, um die 8 Damen auf einem virtuellen Schachbrett zu platzieren.
+Wie würde man das Problem algorithmisch lösen? Am besten probierst du es ohne PC an einem normalen Schachbrett aus - wenn du keines zur Hand hast, kannst du [[https://info-bw.de/static/h5p/8-damen-problem.html|diese Aktivität im Browser]] verwenden, um die 8 Damen auf einem virtuellen Schachbrett zu platzieren. Um mit weniger Feldern zu beginnen, kannst du auch die {{ :faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:8-damen-problem:n-damen-unplugged.pdf |folgende Vorlage}}verwenden.
 <WRAP center round info 75%>
 Lies hier erst weiter, nachdem du dir selbst Gedanken gemacht hast, wie du vorgehen könntest.
@@ Zeile 25: / Zeile 25: @@
 <code java>
-// die Methode reihe(r) hat nur die Aufgabe, die übergebene Reihe r fehlerfrei zu befüllen
+// die Methode befuelleZeile(zeile) hat nur die Aufgabe,
-reihe(r):
+// die übergebene Zeile fehlerfrei zu befüllen
-    wenn r < 8:
+befuelleZeile(zeile):
-        für jede Spalte s (0-7):
+    wenn zeile < 8:
-            wenn die Spalte frei ist:   // lagere die Überprüfung in separate Methode aus!
+        für spalte von 0 bis 7:
-                setze Dame ins Feld [r][s]
+            wenn istPositionErlaubt(zeile, spalte):
+                setze Dame ins Feld [zeile][spalte]
-                wenn kollisionsfrei auf Diagonalen:    // lagere die Überprüfung in die bereits VORGEGEBENE Methode aus!
+                befuelleZeile(zeile+1)              // Nächste Zeile befüllen
-                    reihe(r+1)     // Die aktuelle Dame ist korrekt platziert -> fülle die nächste Reihe
+                loesche Dame im Feld [zeile][spalte] // Warum?
-                // wenn ich wieder aus der Rekursion zurückkomme ODER wenn es eine diagonale Kollision gab:
-                entferne Dame aus Feld [r][s]
     sonst:
-        druckeFeld()   // Lösung gefunden - gib das komplette Schachfeld aus!
+        druckeFeld()  // Lösung gefunden - gib das komplette Feld aus!
 </code>
 Man startet diese Methode mit dem Aufruf von ''reihe(0)''.
@@ Zeile 45: / Zeile 42: @@
 === (A1) ===
-  - Lade die {{ .:8-damen-problem.zip | Vorlage}} herunter und mache dich mit dem bereits vorgegebenen Code vertraut.
+Arbeite mit der folgenden Vorlage: https://codeberg.org/qg-info-unterricht/bluej-8-Damen-console
-  - Überlege dir, welcher **Datentyp** für das Spielfeld sinnvoll ist. Setze den Typ in der Instanzvariablen und initialisiere das Spielfeld / die Variable im Konstruktor.
-  - Implementiere den Pseudocode im vorgegebenen Methodengerüst. Für die Kollisionsprüfung auf der Diagonalen kannst du die bereits vergegebene Methode ''kollisionsfrei()'' nutzen. Implementiere dabei auch die folgenden zusätzlich nötigen Methoden:
-    - ''druckeFeld()'': Druckt den gesamten Zustand des Feldes, wenn eine Lösung gefunden wurde. Tipp: Unterstrich für ein leeres Feld, X für eine Dame.
-    - ''spalteFrei(int spalte)'': Prüfe für die übergebene Spalte, ob diese komplett frei ist.
-Um zu testen, ob eine Dame an eine bestimmte Position gesetzt werden darf, implementiert man die Methode ''boolean erlaubtePosition(int zeile, int spalte)''. Diese gibt ''true'' zurück, wenn die Dame platziert werden darf, andernfalls ''false''.
+**(A)** Modelliere das Feld mit einem zweidimensionalen Array des Typs ''boolean''. Definiere das Feld als Attribut der Klasse, initialisiere es im Konstruktor.
+**(B)** Implementiere eine Methode ''druckeFeld()'', die den gesamten Zustand des Schachbretts ausdruckt. Du kannst bei der Ausgabe z.B. einen Unterstrich für ein leeres Feld des Bretts, X für ein Feld mit einer Dame verwenden((Du kannst auch Unicode Zeichen wie ⬚ und ♕ verwenden)). Teste deine Methode, indem du im Konstruktor das leere Feld ausgeben lässt, eine oder mehrere Damen setzt und dann das Feld mit den Damen ausgeben lässt.
+**(C)** Implementiere eine Testmethode, die zurück gibt, ob an der aktuellen Position eine Dame gesetzt werden darf.
+Um zu testen, ob eine Dame an eine bestimmte Position gesetzt werden darf, implementiert man die Methode
+<code java>
+boolean istPositionErlaubt(int zeile, int spalte)
+</code>
+Diese gibt ''true'' zurück, wenn die Dame platziert werden darf,  andernfalls ''false''.
 Einige Überlegungen zu dieser Methode:
@@ Zeile 59: / Zeile 62: @@
   -  Wir müssen also nur die Diagonalen oberhalb und die Spalte oberhalb der Position überprüfen, auf die wir gerne eine Dame platzieren würden.
-Die folgende Skizze stellt die Situation dar:
+Die Skizze stellt die Situation dar. Jetzt kann man sich überlegen, wie man an die Koordinaten der "gestrichelten" Felder kommt, die man überprüfen muss:
-{{ :faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:8-damen-problem:5damen-kollision.excalidraw.png?nolink |}}
-Jetzt kann man sich überlegen, wie man an die Koordinaten der "gestrichelten" Felder kommt, die man überprüfen muss:
+{{ :faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:8-damen-problem:5damen-kollision.excalidraw.png?500|}}
    * Die Felder in der Zeile oberhalb der aktuellen Position haben die Koordinaten ''O(0...zeile-1|spalte)''
+   * Wenn man mit der Variablen ''zeileAktuell'' zeilenweise von oben nach unten über das Feld iteriert, haben die Felder der "linken" Diagonalen die Koordinaten ''L(zeileAktuell|spalte-(zeile-zeileAktuell)''. Die Felder der rechten Diagonalen haben die Koordinaten ''R(zeileAktuell|spalte+(zeile-ZeileAktuell))''. In beiden Fällen muss man jedoch darauf achten, dass die berechnete Spalte sich innerhalb des erlaubten Bereichs für die Spaltenindex befindet: 0 bis N-1. Im Beispiel gibt es in Zeile 0 nämlich weder links noch rechts ein Feld auf der Diagonalen, da sowohl ''2-(3-0)=-1'' als auch ''2+(3-0)=5'' sich außerhalb des Feldes befinden. In Zeile 1 erhalten wir aber die Koordinaten der beiden Diagonalenfelder: ''L(1|2-(3-1)=L(1|0)'' und ''R(1|2+(3-1))=R(1|4)''.
+**(D)** Teste deine Methode ''istPositionErlaubt'':
+  * Erzeuge ein Schachbrett 8x8
+  * Setze eine Dame auf das Feld ''(0|2)''
+  * Überprüfe, ob deine Methode beim Aufruf aus der Objektleiste die korrekten Antworten für mögliche Damen auf den Feldern ''(1|0)'', ''(1|1)'', ''(1|2)'', ''(1|3)'' und ''(1|6)'' gibt.
+++++ Hilfestellung 1 zu "istPositionErlaubt": |
+<code java>
+public boolean istPositionErlaubt(int zeile, int spalte) {
+        // Füge hier deinen Code für die Kollisionserkennung ein.
+        // Einen Lösungsvorschlag findest du im Wiki
+        // Alle Zeilen von 0 bis zeile-1 untersuchen:
+        for(int zeileAktuell=0; zeileAktuell<zeile; zeileAktuell++) {
+            // Felder oberhalb untersuchen, wenn Dame:
+            // return false
+            if( FIXME ) {
+                return false;
+            }
+            // Felder der Diagonalen untersuchen, wenn Dame:
+            // return false
+            // Linke Diagonale
+            if( FIXME ) {
+                return false;
+            }
+            // Rechte Diagonale
+            if( FIXME ) {
+                return false;
+            }
+        }
+        return true;
+    }
+</code>
+++++
+++++ Lösungsvorschlag zu "istPositionErlaubt": |
+<code java>
+public boolean istPositionErlaubt(int zeile, int spalte) {
+        // Füge hier deinen Code für die Kollisionserkennung ein.
+        // Einen Lösungsvorschlag findest du im Wiki
+        // Alle Zeilen von 0 bis zeile-1 untersuchen:
+        for(int zeileAktuell=0; zeileAktuell<zeile; zeileAktuell++) {
+            // Felder oberhalb untersuchen, wenn Dame:
+            // return false
+            if(feld[zeileAktuell][spalte]) {
+                return false;
+            }
+            // Felder der Diagonalen untersuchen, wenn Dame:
+            // return false
+            if(spalte - (zeile-zeileAktuell) >= 0 && feld[zeileAktuell][spalte - (zeile-zeileAktuell)] ) {
+                return false;
+            }
+            if( spalte + (zeile-zeileAktuell) < SIZE && feld[zeileAktuell][spalte + (zeile-zeileAktuell)] ) {
+                return false;
+            }
+        }
+        return true;
+    }
+</code>
+++++
+**(E)** Wenn du geprüft hast, dass deine ''istPositionErlaubt''-Methode korrekt funktioniert, kannst du den Pseudocode für ''befuelleZeile'' in deinem BlueJ-Projekt implementieren. Tipp: Nicht zuviel nachdenken, versuche den Pseudocode in  Java zu "übersetzen".
+Teste die Methode mit Schachbrettern 4x4 und 8x8. Überprüfe die ausgegebenen Lösungen stichprobenartig.
 {{:aufgabe.png?nolink  |}}
 === (A2) ===
-Was ist der Basisfall dieser Rekursion?
+Was ist der Basisfall dieser Rekursion? Finde einen Weg, dir mit dem Debugger den Stack anzeigen zu lassen, wenn der Basisfall eintritt. Was fällt dir dabei auf?
 {{:aufgabe.png?nolink  |}}
-=== (A3) - Für die Schnellen ===
+=== (A3) ===
 Erweitere das Programm: Lass dir ausgeben, wie viele Lösungen gefunden wurden.
-{{:aufgabe.png?nolink  |}}
-=== (A4) - Für die Schnellen ===
-Wenn du früh fertig bist, dann kannst du überlegen, ob du selbst eine andere/eigene Lösung für die Kollisionsprüfung auf der Diagonalen findest (das ist ziemlich knifflig, wenn man nicht den mathematischen Kniff der Vorlage nutzt).\\ \\
 <WRAP center round info 75%>
@@ Zeile 84: / Zeile 156: @@
 https://www.mathematik.ch/spiele/N_Damenproblem/
 </WRAP>
+==== Material ====
+{{simplefilelist>:faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:8-damen-problem:*}}