Acht-Damen-Problem HILFE!

[gehweg]

Hallo,

ich muss morgen ein Fachreferat über das acht-Damen-Problem halten und habe immense Schwierigkeiten den Quelltext zu verstehen. Hier ist also ein HILFERUF!!
Der Text sieht wie folgt aus:
[JAVA=42]
public class DamenproblemOhneThis {

//Attribute

int[][] feld; //Spielfeldmatrix (1-Dame, 0-freies Feld)
public static int lösungen = 0; //Anzahl der Lösungen

//Konstruktor
public DamenproblemOhneThis ()
{

feld = new int[8][8];
}
//Methoden
public void platziere(int zeile)
{
for(int spalte = 0; spalte < 8; spalte = spalte + 1)
{
feld[zeile][spalte] = 1;
if(korrektPlatziert())
if(zeile == 7)
{
ausgabe();
System.out.println("---------------");
DamenproblemOhneThis.lösungen = lösungen + 1;
}
else
platziere(zeile+1);

//Spalte wieder nullen
feld[zeile][spalte] = 0;
}
}

public void ausgabe()
{
for(int a = 0; a < 8; a = a + 1)
{
for(int b = 0; b < 8; b = b + 1)
System.out.print(feld[a]+" ");
System.out.println("");
}
}

public boolean korrektPlatziert()
{
boolean found = false;

//Überprüfen ob in jeder Zeile max. eine Dame steht
for(int a = 0; a < 8; a = a + 1)
{
found = false;
for(int b = 0; b < 8; b = b + 1)
{
if(feld[a] == 1)
if(found == false)
found = true;
else
return false;
}
}

//Überprüfen ob in jeder Spalte max. eine Dame steht
for(int b = 0; b < 8; b = b + 1)
{
found = false;
for(int a = 0; a < 8; a = a + 1)
{
if(feld[a] == 1)
if(found == false)
found = true;
else
return false;
}
}

//[links oben] -> [rechts unten] Diagonalen überprüfen
for(int zeile = 0; zeile < 8; zeile = zeile + 1)
{
found = false;
int spalte = 0;
while(zeile+spalte < 8)
{
if(feld[zeile+spalte][spalte] == 1)
if(found == false)
found = true;
else
return false;
spalte = spalte + 1;
}
}
for(int spalte = 1; spalte < 8; spalte = spalte + 1)
{
found = false;
int zeile = 0;
while(spalte+zeile < 8)
{
if(feld[zeile][spalte+zeile] == 1)
if(found == false)
found = true;
else
return false;
zeile = zeile + 1;
}
}

//[links unten] -> [rechts oben] Diagonalen überprüfen
for(int zeile = 7; zeile >= 0; zeile = zeile - 1)
{
found = false;
int spalte = 0;
while(zeile-spalte >= 0)
{
if(feld[zeile-spalte][spalte] == 1)
if(found == false)
found = true;
else
return false;
spalte = spalte + 1;
}
}
for(int spalte = 0; spalte <8; spalte = spalte + 1)
{
found = false;
int zeile = 0;
while(spalte+zeile < 8)
{
if(feld[8-zeile-1][spalte+zeile] == 1)
if(found == false)
found = true;
else
return false;
zeile = zeile + 1;
}
}
return true;
}



public static void main(String[] args)
{
DamenproblemOhneThis AQP = new DamenproblemOhneThis();
AQP.platziere(0);
System.out.println(DamenproblemOhneThis.lösungen+" Lösungen gefunden");
}
}

[/code]

 

[Final_Striker]

ich muss morgen ein Fachreferat über das acht-Damen-Problem halten und habe immense Schwierigkeiten den Quelltext zu verstehen.

Aha, und das ist dir so um 22:00 Uhr am Vorabend aufgefallen? Na dann viel Glück bei deinem Referat.

 

[irgendjemand]

Aha, und das ist dir so um 22:00 Uhr am Vorabend aufgefallen? Na dann viel Glück bei deinem Referat.

made my day ... zu mal TO diese aufgabe bestimmt schon mindestens eine woche oder länger hat ...
ach ja .. das liebe *in-letzter-minute*

 

[gehweg]

Ich habe nicht in allerletzte minute angefangen damit... aber davor habe ich eben gedacht dass der Quelltext viel einfacher zu verstehen ist, naja und jetzt steh ich da 😀. Danke 🙂. Euch auch einen schönen Freitag.

 

[Landei]

Mit acht Damen hätte selbst ich ein Problem...

Aber für die kommenden Generationen: Der Code oben ist rekursiv und geht zeilenweise vor. Dabei wird in der Zeile eine Dame nacheinander an jede Stelle gesetzt und geprüft, ob die Stellung "erlaubt" ist (mit [c]korrektPlaziert[/c]).

Wenn ich eine Dame in der 8. Reihe korrekt platzieren konnte ([c]zeile == 7[/c] wegen nullbasiertem Array-Index), habe ich eine Lösung gefunden. Ansonsten mache ich (durch rekursiven Aufruf von [c]platziere[/c]) in der nächsten Zeile weiter.

Übrigens ein schönes Beispiel für Aufgaben, für die Java ziemlich schlecht geeignet ist. Auch wenn man obigen Code locker auf ein Viertel kürzen könnte, ist es noch eine ziemliche Lücke zu Haskell-Lösungen wie

queens n = map reverse $ queens' n where 
          queens' 0       = [[]]
          queens' k       = [q:qs | qs <- queens' (k-1), q <- [1..n], isSafe q qs]
          isSafe   try qs = not (try `elem` qs || sameDiag try qs)
          sameDiag try qs = any (\(colDist,q) -> abs (try - q) == colDist) $ zip [1..] qs

 

[Gasssssssst]

Angeber :autsch:

 

[Da_Tebe]

Haskel ist was sowas betrifft halt unangefochten...
Quick-Sort war ein dreizeiler, oder ? ^^

 

[Landei]

Angeber :autsch:

Na ja, gerade am Anfang braucht man wahrscheinlich viel länger, um ein paar Zeilen Haskell hinzubekommen, als irgend ein Java-Monster zusammenzuklöppeln.

 

[Gasssssssst]

Eine frage, ich hoffe die ist Objektiv zu beantworten:
Wenn ich Haskal könnte, wäre der Code dann genauso leserlich wie der oben vorgestellte java code? (Ganz davon zu schweigen, das man in Haskal natürlich nicht durchgängig so programmiert (oder 😉))

 

[Da_Tebe]

Also bei mir war Haskel an der Uni Pflicht.
Nach ner Zeit konnte man das schon ganz gut verstehen, aber diese scheinbar endlos in sich geschachtelten Rekursionen werfen einem am Anfang auf jeden fall aus der Bahn.

 

[Landei]

Eine frage, ich hoffe die ist Objektiv zu beantworten:
Wenn ich Haskal könnte, wäre der Code dann genauso leserlich wie der oben vorgestellte java code? (Ganz davon zu schweigen, das man in Haskal natürlich nicht durchgängig so programmiert (oder 😉))

Man kann in Haskell sehr leserlichen Code schreiben - ich denke sogar viel leserlicher als unser Java-Beispiel. Aber es ist sehr unterschiedlich, wie gut jemand mit den Abstraktionen zurecht kommt - manche kommen gut mit Funktionen höherer Ordnung, Algebraischen Datentypen, Typklassen u.s.w. klar, andere überhaupt nicht.

Ich habe auch das Gefühl, dass sich Haskell-Code während des Schreibens auch stärker verändert als in Java ("oh, hier sieht eine Comprehension besser aus, und diese Rekursion kann ich durch einen Fold ersetzen...") - jedenfalls bei mir.

 

[Landei]

Mal ein Versuch, ganz von vorn eine Lösung zu schreiben:

isSafe x xs = notElem x xs && notDiag x xs succ && notDiag x xs pred where
  notDiag _ [] _ = True
  notDiag q (x:xs) f = x /= f q && notDiag (f q) xs f
  
queens n = queens' n [[]] where
  queens' 0 acc = acc
  queens' k qss = queens' (k-1) [q:qs | qs <- qss, q <- [0..(n-1)], isSafe q qs]

[c]isSafe[/c] sagt folgendes aus: Eine neue Dame ist "sicher", wenn die Spalte noch nicht in den vorhandenen Damen-Positionen vorkommt (

notElem

gibt es dafür schon "fertig") und auch nicht diagonal bedroht wird.

succ

und

pred

sind die Funktionen "um eins erhöhen / erniedrigen".

notDiag

verwendet einfache Rekursion, um alle Zeilen durchzugehen.

queens'

zählt im ersten Argument die gewünschten Zeilen herunter, das zweite Argument enthält alle bisher gefundenen gültigen Positionen.

queens'

ist wie

notDiag

explizit rekursiv. Der Code in den eckigen Klammern entspricht einer doppelt geschachtelten Schleife: Für alle gültigen Position und für alle Spalten von 0 bis n-1 füge eine Dame hinzu und schau nach, ob die Position immer noch gültig ist. Mein

queens'

sieht dem oben sehr ähnlich, hat aber eine andere Abfolge der Rekursion (ich arbeite mit Akkumulator, der Code oben ohne).

Für den ersten Versuch finde ich das recht lesbar. Allerdings würde man jetzt üblicherweise die Rekursionen z.B. durch Folds ersetzen, oder andere Tricks anwenden. [c]isSafe[/c] könnte man z.B. so schreiben:

isSafe x xs = all (notElem x) [xs, dg [1..], dg [-1,-2..]] where dg = zipWith (+) xs

Das ist zwar deutlich kürzer, aber auch schwerer zu verstehen. Der Trick ist hier, dass [c]dg[/c] die Positionen der bereits gefundenen Zeilen stufenweise "verschiebt" (je nach übergebener Liste nach links oder rechts), so dass wir zur Überprüfung der Diagonalen auch das vorhandene [c]notElem[/c] nutzen können.

Ich finde, wenn man weniger "fertige" Haskell-Lösungen zeigen würde, sondern öfter mal den Weg von einer Anfangslösung zum polierten Endprodukt (inklusive Sackgassen), würde ein guter Teil des Haskell-Mythos verpuffen, und es wäre viel leichter, sich die ganzen Tricks abzuschauen.