# Acht-Damen-Problem HILFE!



## gehweg (26. Apr 2012)

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 (27. Apr 2012)

> 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 (27. Apr 2012)

Final_Striker hat gesagt.:


> 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 (27. Apr 2012)

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 (27. Apr 2012)

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 (27. Apr 2012)

Angeber :autsch:


----------



## Da_Tebe (27. Apr 2012)

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


----------



## Landei (27. Apr 2012)

Gasssssssst hat gesagt.:


> 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 (27. Apr 2012)

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 (27. Apr 2012)

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 (27. Apr 2012)

Gasssssssst hat gesagt.:


> 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 (27. Apr 2012)

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.


----------

