Lernpfad:Rekursion in Java/Rekursion bei Schachproblemen: Unterschied zwischen den Versionen

Aus Informatik-Box
Zur Navigation springen Zur Suche springen
Keine Bearbeitungszusammenfassung
Keine Bearbeitungszusammenfassung
Zeile 4: Zeile 4:
Man versucht 8 Damen auf dem Schachbrett zu positionieren. Dabei müssen die Damen so aufgestellt werden,
Man versucht 8 Damen auf dem Schachbrett zu positionieren. Dabei müssen die Damen so aufgestellt werden,
dass sich keine Damen gegenseitig schlagen.
dass sich keine Damen gegenseitig schlagen.
{{Aufgabe:Start}}
Versuche auf einem 5x5 Feld 5 Damen aufzustellen.
{{Aufgabe:End}}


Ein rekursiver Algorithmus könnte wie folgt aussehen:  
Ein rekursiver Algorithmus könnte wie folgt aussehen:  
<syntaxhighlight >
<syntaxhighlight >
dame(t, zeilen)  
dame(t, zeilen)  
   Falls t < 8 ist
   Falls t < 8 ist DANN
  DANN
  Wiederhole für alle Positionen (starte bei 0)
     pos = erste Leere Zeile
     aktuelle Reihe gleich nächste Position
     wiederhole solange pos < 8 ist
     Falls die aktuelle Reihe noch frei ist DANN
      setze die Dame auf die Position
    setze die Dame auf die freie Reihe
       prüfe ob die Dame mit einer anderen kollidiert
       Falls die Dame mit keiner anderen kollidiert DANN
      Falls ja
      dame(t+1, zeilen)
        nächste freie Zeile verwenden
       Entferne die aktuelle Dame aus der Reihe
      Falls nein
        loesung = dame(t+1, zeilen)
    Falls !loesung
    DANN
       gib false zurueck
   SONST
   SONST
     speicher die Lösung / gib die Lösung aus
     speicher die Lösung  
    gib true zurueck
</syntaxhighlight >
</syntaxhighlight >
<p5js >
</p5js>
# Springerproblem  
# Springerproblem  
## https://de.wikipedia.org/wiki/Springerproblem
## https://de.wikipedia.org/wiki/Springerproblem

Version vom 8. Januar 2019, 22:43 Uhr

Im Kontext des Schachspiels gibt es zwei sehr bekannte Problemstellungen. An dieser Stelle sollen einfach nur ein paar Links für interessierte hinzugefügt werden:

  1. Dameproblem

Man versucht 8 Damen auf dem Schachbrett zu positionieren. Dabei müssen die Damen so aufgestellt werden, dass sich keine Damen gegenseitig schlagen.

Icon Heft.png
Arbeitsauftrag

Versuche auf einem 5x5 Feld 5 Damen aufzustellen.


Ein rekursiver Algorithmus könnte wie folgt aussehen: 

dame(t, zeilen) 
  Falls t < 8 ist DANN 
  	Wiederhole für alle Positionen (starte bei 0)
    aktuelle Reihe gleich nächste Position
    Falls die aktuelle Reihe noch frei ist DANN
    	setze die Dame auf die freie Reihe
      Falls die Dame mit keiner anderen kollidiert DANN 
      	dame(t+1, zeilen)
      Entferne die aktuelle Dame aus der Reihe
  SONST
    speicher die Lösung

  1. Springerproblem
    1. https://de.wikipedia.org/wiki/Springerproblem
    2. http://www.axel-conrad.de/springer/springer.html
    3. https://docplayer.org/41857208-Backtracking-mit-heuristiken.html
  1. https://www.mathe-online.at/materialien/matroid/files/schach/schachbrett.html
  1. Labyrinth http://www.erasmus-reinhold-gymnasium.de/info/rekursion-iteration/Backtracking_final.pdf
Abgerufen von „http://ngb.schule/hgwiki/index.php?title=Lernpfad:Rekursion_in_Java/Rekursion_bei_Schachproblemen&oldid=4520“