faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:8-damen-problem:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:8-damen-problem:start [25.02.2025 07:57] – Frank Schiebelfaecher: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 ==== ==== 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%> <WRAP center round info 75%>
 Lies hier erst weiter, nachdem du dir selbst Gedanken gemacht hast, wie du vorgehen könntest. Lies hier erst weiter, nachdem du dir selbst Gedanken gemacht hast, wie du vorgehen könntest.
Zeile 25: Zeile 25:
  
 <code java> <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:     sonst:
-        druckeFeld()   // Lösung gefunden - gib das komplette Schachfeld aus!+        druckeFeld()  // Lösung gefunden - gib das komplette Feld aus!
 </code> </code>
 Man startet diese Methode mit dem Aufruf von ''reihe(0)''.  Man startet diese Methode mit dem Aufruf von ''reihe(0)''. 
Zeile 45: Zeile 42:
 === (A1) ===  === (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.+
  
-=== Testmethode: Darf an eine Position eine Dame gesetzt werden? ===+**(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 Um zu testen, ob eine Dame an eine bestimmte Position gesetzt werden darf, implementiert man die Methode
Zeile 66: 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.   -  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 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?500|}} {{ :faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:8-damen-problem:5damen-kollision.excalidraw.png?500|}}
  
-Jetzt kann man sich überlegen, wie man an die Koordinaten der "gestrichelten" Felder kommt, die man überprüfen muss: 
  
    * Die Felder in der Zeile oberhalb der aktuellen Position haben die Koordinaten ''O(0...zeile-1|spalte)''    * 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)''.      * 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  |}} {{:aufgabe.png?nolink  |}}
 === (A2) ===  === (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  |}} {{:aufgabe.png?nolink  |}}
-=== (A3) - Für die Schnellen ===  +=== (A3) ===  
-Erweitere das Programm: Lass dir ausgeben, wie viele Lösungen gefunden wurden.+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%> <WRAP center round info 75%>
Zeile 92: Zeile 156:
 https://www.mathematik.ch/spiele/N_Damenproblem/ https://www.mathematik.ch/spiele/N_Damenproblem/
 </WRAP> </WRAP>
 +
 +
 +==== Material ====
 +
 +{{simplefilelist>:faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:8-damen-problem:*}}
 +
  
  • faecher/informatik/oberstufe/algorithmen/rekursion/backtracking/8-damen-problem/start.1740470240.txt.gz
  • Zuletzt geändert: 25.02.2025 07:57
  • von Frank Schiebel