# Damenproblem mit Backtracking



## jeko87 (27. Okt 2010)

Hallo,
ich hab ein Problem mit einer Aufgabe. Ich muss das n-Damenproblem implementieren mit Backtracking. 
Das würd ich auch noch ohne grösseren Aufwand hinkriegen. Nur ich muss mich an einen vorgegebenen Pseudocode halten und ich hab Probleme diese Notation in Java zu übersetzen...was den Algorithmus an sich angeht, ist mir klar.

Hier mal so eine Problemstelle:

```
M := {()}; // Menge der aktiven Knoten, Start mit Wurzel
while (!M.isEmpty()) do
wähle (a1;...;aj) € M; // Stelle an der eine Dame stehen kann
M := M\{(a1;...;aj)}; // Mengen aktualisieren
```

mein Problem ist halt, dass ich bis jetzt noch nie mit solchen Mengen arbeiten musste...
hab im Internet gesucht, und dazu mal "Set<Integer>" gefunden, müsste doch eigentlich eine Menge darstellen können ??

und wie ich (a1;...;aj) € M dann prüfen kann ist mir nicht klar...
würde mich freun wenn mir jemand weiterhelfen kann

danke danke


----------



## mfernau (27. Okt 2010)

Ich denke da gibt es X Möglichkeiten funktionierende Abbildungen für Mengen in Java zu finden.
M ist in Deinem Fall eine Menge von Mengen, die Koordinaten/Felder enthalten. Also eine Menge von (a1,...,aj).
Für die (a1,...,aj) könntest Du z.B. HashSet<Integer> verwenden. Dort kannst Du einfach Integers hinein stecken.
Für M würde sich dann einfach ein Vector eigenen. In Deinem Fall also ein Vector<HashSet<Integer>>;
Der Vector enthält also Elemente vom Typ HashSet welches seinerseits wieder Integers enthält.
Die Analogie von 

```
wähle (a1;...;aj) € M
```
wäre dann wohl sich einfach ein Element aus dem Vector zu holen. Das geht mit der Methode get() - oder noch einfacherer firstElement()/lastElement().

```
M := M\{(a1;...;aj)};
```
heisst ja nichts weiter, als das eben selektierte Element/Objekt (also das HashMap-Objekt) aus der Menge zu entfernen. Das geht dann via remove(Object);

Ich hoffe das reicht Dir erstmal als Antwort. Ansonsten müsste ich mich mit dem Damenproblem selbst erstmal wieder vertraut machen um zu wissen was genau da gefordert wurde. Meine Informatikzeiten sind zu lange her als das ich das noch im Kopf hätte 

Edit: Wenn Du mit dem Vector gut klar kommst und willst es noch "hübsch" machen, würde sich eine LinkedList anstelle des Vectors noch besser eignen. Diese Klasse implementiert eine Queue und ist perfekt geeignet mit der Methode remove() zwei Schritte auf ein mal zu erledigen. Nämlich sich ein Element aus M geben zu lassen und gleichzeitig dieses Element aus der Menge zu entfernen.


----------



## jeko87 (27. Okt 2010)

super. vielen Dank für deine schnelle Antwort. mit LinkedList und einer Queue hab ich schon gearbeitet, versuche es mal damit hinzukriegen.
HashSet wäre für mich ganz neu, hab zwar was drüber gelesen, doch bisher noch nicht implementiert.

Versuch mein Glück mal
Danke nochmals


----------



## jeko87 (27. Okt 2010)

hallo nochmal,

also hab mich nun mit meinem Problem beschäftigt, merke aber, dass ich irgendwie immer noch Probleme hab

hier ist mal mein Code:

```
public boolean solve(int m)
{	       
    //k(x) Anzahl Möglichkeiten
    //d(x) Dimension Lösungsraum

    //Menge M -> Menge von Mengen (a1,...,aj) 
    Vector<HashSet<Integer>> Menge = new Vector<HashSet<Integer>>();  
   //einzelne Menge (a1,...,aj)	    
   HashSet<Integer> n = new HashSet<Integer>();  //Menge (a1,...,aj)
   //Anzahl Felder
   int x = m;

    while (!Menge.isEmpty())
    {    	
         // ab hier hakt es bei mir...versteh einfach nicht wie ich mit den Typen umgehen muss
        // Pseudocode: 
        //wähle (a1;...; aj) € M
        // M := M\{(a1;...; aj)};
        
       for (Iterator<Integer> i = n.iterator(); i.hasNext();)  // Menge (a1,...,aj) durchlaufen
       {
           Menge = Menge.get(i);    // ich bin mir bewusst, dass hier etwas nicht stimmt 
           Menge = Menge.remove(i);
       }
    }    

     // Pseudocode: 
     //for a € {1;...;k(x)} do // prüfe alle Nachfolger -> k(x): Anzahl Möglichkeiten
     // if j + 1 = d(x) then // Blatt erreicht -> d(x): Dimension des Lösungsraums
     // if (x; (a1;...; aj; a)) € sol(x) then return 1 endif
    }
```

also sry, aber dies sind einfach die Stellen bei denen ich keinen Plan hab...ich hab im Internet andere Implementierungen gefunden, welche mir auch einleuchten...aber diese Mengenschreibweise macht mich irre...

würd mich freun wenn du mir vielleicht nochmal etwas helfen kannst

danke 
mfG


----------



## mfernau (27. Okt 2010)

Sieht doch schon mal nicht ganz so übel aus. Ich kann auch davon ausgehen, dass Du irgendwo zwischen Zeile 7 und Zeile 13 Elemente in Deinen Vector (Menge) eingefügt hast, ja? Weil der ist ja erstmal mächtig leer.. So leer wie meine Bierkiste im Keller...
Aber egal..
[java=13]while (!Menge.isEmpty())[/code]
soll also so lange laufen, wie noch Elemente drin sind. Passt...

sehen wir uns den Rest an
[JAVA=15]         // ab hier hakt es bei mir...versteh einfach nicht wie ich mit den Typen umgehen muss
        // Pseudocode: 
        //wähle (a1;...; aj) € M
        // M := M\{(a1;...; aj)};

       for (Iterator<Integer> i = n.iterator(); i.hasNext()  // Menge (a1,...,aj) durchlaufen
       {
           Menge = Menge.get(i);    // ich bin mir bewusst, dass hier etwas nicht stimmt 
           Menge = Menge.remove(i);
       }
[/code]
Es heisst ja, Du sollst ein Element aus der Menge heraus nehmen. Irgend eines. Also nehmen wir halt das letzte Element und entfernen es anschließend:
[JAVA=15]       HashSet<Integer> element = Menge.lastElement();
       Menge.remove(element);[/code]
Damit hast Du in _element_ ein beliebiges (hier das letzte) Element aus dem Vector (Deiner Menge) geholt und anschließend den Vector um dieses Element erleichtert.
Was Du damit jetzt tun musst weiss ich nicht. Aber bis hier hin ist es erstmal das, was gefordert war.
Damit wären dann die Zeilen 19 bis 24 auch überflüssig.


----------



## jeko87 (27. Okt 2010)

ja sorry...hatte einige Zeilen nicht mit kopiert...also Menge müsste gefüllt sein, also die "while" Schleife wird also bearbeitet...
was das löschen angeht ist es also egal ob ich das 1te oder das nte Element lösche ? (wenn nicht genau angegeben)
was mit dem gelöschten Element passiert bin ich nicht sicher...

im Pseudocode gehts damait weiter:

```
// prüfe alle Nachfolger, wobei k(x) = Anzahl der Möglichkeiten
for a € {1;...; k(x)} do
    // Blatt erreicht 
    if j + 1 = d(x) then 
        if (x; (a1;...; aj; a)) € sol(x) then return 1 endif
```

Also denke ich mal, dass das "a" in Zeile 2 das gelöschte Element ist, von dem die Nachbarn abgefragt werden...
also würd ich zuerst das gelöschte Element speicheren, so in etwa

```
HashSet<Integer> element = Menge.lastElement(); 
HashSet<Integer> a = Menge.remove(element);
```

Nun könnte ich dann mit Zeile 2 fortfahren...for a € {1,...,k(x)} do
wobei dies wieder ein neuen HashSet braucht...also in etwa

```
HashSet<Integer> p = new HashSet<Integer>() 
for (Iterator<Integer> i = p.iterator(); i.hasNext();) //(1,...,k(x) durchlaufen
    //Blatt erreicht
    if j+1=d(x)  // d(x)= Dimension des Lösungsraums
         // hier wird geprüft ob die Lösung ok ist...aber wie das jetzt in java aussehen soll
         if (x; (a1;...; aj; a)) € sol(x) then return 1 endif
```


also hier ist nun mal mein Code zusammengefasst (ist leichter zu beurteilen)

```
public boolean solve(int m)
	{	       
	    //k(x) Anzahl Möglichkeiten
	    //d(x) Dimension Lösungsraum
	    
            //Menge M -> Menge von Mengen (a1,...,aj)
	    Vector<HashSet<Integer>> Menge = new Vector<HashSet<Integer>>();  
	    HashSet<Integer> n = new HashSet<Integer>();  //Menge (a1,...,aj)
	    int x = m; //Anzahl Felder
            
            // (a1,...,aj) füllen
	    for (int i=0; i < x; i++)
	    {
	        n.add(i);
	    }
	    
	    while (!Menge.isEmpty())
	    {    	
	    	for (Iterator<Integer> i = n.iterator(); i.hasNext();) //(a1,...,aj) durchlaufen
	    	{
                //wähle (a1;...; aj) € M
                HashSet<Integer> element = Menge.lastElement(); 
                // M := M\{(a1;...; aj)};
                HashSet<Integer> a = Menge.remove(element);
	    	}
	    	
	    	HashSet<Integer> p = new HashSet<Integer>(); 
	    	
            for (Iterator<Integer> i = p.iterator(); i.hasNext();) //(1,...,k(x) durchlaufen
            {
                //Blatt erreicht
                if j+1=d(x)
                {
                    if (x; (a1;...; aj; a)) € sol(x)
                	{
                        return true;
                	}
                	else
                	{
                        if (x; (a1;...; aj; a)) € K then // evtl. Lsg. im Teilbaum	
                    }
                    M := M U {(a1;...; aj; a)}
                }
            }
	    }
    }
```

ab Zeile 31 kommt wieder der Pseudocode, weiter bin ich noch nicht gekommen, sorry

also ich kann dir wirklich nicht genug für deine Geduld danken, bist ein große Hilfe...super echt
danke
mfG


----------



## Landei (28. Okt 2010)

Eine Collection n (Set oder List) durchläuft man am einfachsten so:


```
for (Integer i : n) { ...
```


----------



## mfernau (28. Okt 2010)

jeko87 hat gesagt.:


> was das löschen angeht ist es also egal ob ich das 1te oder das nte Element lösche ? (wenn nicht genau angegeben)


Ja, es ist in Deinem Algorithmus nicht angegeben welches Element man nehmen soll. Also ist es egal. Du könntest das Erste, das Letzte oder eines aus der Mitte nehmen.



jeko87 hat gesagt.:


> was mit dem gelöschten Element passiert bin ich nicht sicher...


Das gelöschte Element _{1;...;k(x)}_ soll sicherlich weiter betrachtet werden.



jeko87 hat gesagt.:


> im Pseudocode gehts damait weiter:
> 
> ```
> // prüfe alle Nachfolger, wobei k(x) = Anzahl der Möglichkeiten
> ...


Ich interpretiere das _a_ eigentlich als ein Element aus der Menge _{1;...;k(x)}_ und nicht als das gelöschte Element welches wir zuvor aus M heraus geholt haben. Denn das gelöschte Element ist die ganze Menge _{1;...;k(x)}_.



jeko87 hat gesagt.:


> also würd ich zuerst das gelöschte Element speicheren, so in etwa
> 
> ```
> HashSet<Integer> element = Menge.lastElement();
> ...


Das bringt gar nichts. Denn in _element_ befindet sich nach dem ersten Befehl das letzte Objekt aus dem Vector. Mit _remove(element)_ entfernst Du nur das angegebene Objekt aus dem Vector (aus Deiner Menge). Sonst wird damit nichts gemacht. Also befindet sich auch nach dem zweiten Befehl noch immer das HashSet in element. _remove_ liefert außerdem einen boolean und kein HashSet Objekt. Dein Java-Compiler müsste also eine Fehlermeldung bringen wenn Du versuchst das zu übersetzen.

Ich bin mir gerade nicht mehr so sicher ob Du den richtigen Weg verfolgst. Ich meine mich entsinnen zu können dass man das Damenproblem mit einem rekursiven Algorithmus löst. Wie sollt ihr das machen?


----------



## Marco13 (28. Okt 2010)

Hab' das jetzt schon eine Weile so halb mitgelesen. Ein paar Punkte:

- Statt HashSet, ArrayList usw. sollte man nur Set, List usw. verwenden (wird gelegentlich als "gegen das Interface programmieren" bezeichnet). Damit bleibt der Code flexibler und allgemeingültiger. Es ist für die meisten Anwendungen wurscht, ob man nun ein HashSet oder TreeSet verwendet. Als Daumen- oder Fausregel: Man sollte immer das Interface verwenden, das gerade so die Mindestanforderungen erfüllt, die durch den Algorithmus gestellt werden.

- Vector ist ein bißchen veraltet. Manche raten dazu, komplett auf Vector zu verzichten, und stattdessen eine [c]Collections.synchronizedList(new ArrayList<E>())[/c] zu verwenden. Aber wenn man ohnehin den ersten Punkt beachtet, und der Vector überall nur als "List" bekannt ist, spicht m.E. auch nichts dagegen, einen Vector zu verwenden. Außer in diesem Fall: Ein Vector ist synchronized, und das ist in diesem Programm nicht notwendig. Eine ArrayList (die auch nur als List bekannt sein sollte) tut's auch. 

- Jede Rekursion läßt sich auch als iteratives Programm schreiben. Aber es stimmt schon: Der bisher gepostete Pseudocode ist ja nicht alles.... :bahnhof:

- Für eine möglichst direkte Umsetzung des bisher geposteten Pseudocodes würde ich eher vermuten, dass dort eine "Set<List<Integer>>" angebracht wäre: M ist eine Menge, und die Elemente der Menge sind der Form "(a1;...;aj)" - also geordnete Tupel, die man mit einer List abbilden kann. Der Code aus dem ersten Post könnte möglichst 1:1 übersetzt IMHO so aussehen

```
import java.util.*;

public class NQueens
{
    public static void main(String args[])
    {
        solve(8);
    }
    
    private static void solve(int columns)
    {
        List<Integer> root = new ArrayList<Integer>();
        for (int i=0; i<columns; i++)
        {
            root.add(i);
        }
        
        // M := {()}; // Menge der aktiven Knoten, Start mit Wurzel
        Set<List<Integer>> M = new HashSet<List<Integer>>();
        M.add(root);
        
        while (!M.isEmpty()) 
        {
            // wähle (a1;...;aj) € M; // Stelle an der eine Dame stehen kann
            List<Integer> A = M.iterator().next(); 
            
            // M := M\{(a1;...;aj)}; // Mengen aktualisieren
            M.remove(A);

            System.out.println("May place queens at "+A);
        }
    }
}
```

Das ist von einem Löser natürlich noch weit weg. Rekursion wäre schon praktisch. Vielleicht solltest du mal den kompletten Pseudocode posten....


----------



## mfernau (28. Okt 2010)

OT



Marco13 hat gesagt.:


> Statt HashSet, ArrayList usw. sollte man nur Set, List usw. verwenden [...]. Als Daumen- oder Fausregel: Man sollte immer das Interface verwenden, das gerade so die Mindestanforderungen erfüllt[...]


Das war mir neu - aber man lernt ja nie aus. Verstehe das Prinzip dahinter. Danke für die Info.
Stiftet für einen Neuling aber auch etwas mehr Verwirrung als Klarheit zu schaffen...

/OT


----------



## Marco13 (28. Okt 2010)

Hm. Wo das Verwirrung stiften soll, weiß ich nicht genau. Mit der Bedeutung von Interfaces kann man sich nicht drüh genug beschäftigen  Schon allein zum Vorbeugen gegenüber Posts wie "Hilfe, warum kennt ArrayList die Methode 'getElementAt' nicht? ;( "


----------



## jeko87 (28. Okt 2010)

ok vielen Dank für die Infos. Dann versuch ich jetzt mal mit "Sets" zu arbeiten.
Also ob ich den richtigen Weg verfolge bin ich mittlerweile auch nicht sicher.
Ich versuch den Pseudocode Zeile für Zeile abzuarbeiten, jedoch bleiben noch die Probleme mit der Mengenschreibweise in Java zu übersetzen.

wenn es weiterhilft, ich kann den Pseudocode als Datei anhängen...ich würde jedoch schon gerne "selbst" weiterkommen, also wirklich verstehen wie ich es übersetzen soll...aber wenn ich dann folgende Zeilen lese, ich komm einfach nicht drauf wie das in Java gehen soll


```
// prüfe alle Nachfolger, wobei k(x) = Anzahl der Möglichkeiten
for a € {1;...; k(x)} do
    // Blatt erreicht 
    if j + 1 = d(x) then 
        if (x; (a1;...; aj; a)) € sol(x) then return 1 endif
```

also tut mir ech leid Leute...trotzdem vielen Dank für die gute Hilfe


----------



## mfernau (28. Okt 2010)

[c]for a € {1;...; k(x)}[/c] bedeutet, sich ein Element nach dem Anderen aus einer Menge heraus zu holen

```
for(Integer a : menge) {
                // .. schlaue Sachen mit dem a anstellen
        }
```
Ich bitte hier zu Beachten, welche Mengen gemeint sind. Denn ich hab hier leider die Übersicht verloren  Ich kann Dir jetzt lediglich Java-Analogien aufzeigen, nicht aber sehen, ob das mit dem Algorithmus überein stimmt. Aber das musst Du tatsächlich selbst bewerkstelligen.

Edit: [c]for(Integer a : menge)[/c]
Damit durchläufst Du alle Elemente aus dem Set oder der List mit dem Namen _menge_ und bekommst die Referenz auf das aktuelle Element in a geliefert. Also mit jedem Durchlauf der for-Schleife bekommst Du mit _a_ das nächste Teil aus _menge_


----------



## jeko87 (28. Okt 2010)

klar, das versteh ich ja auch. Ich will ja selbst die Aufgabe lösen, nur so bringt es mir ja auch was.
Also ich versuch mein Glück jetzt noch weiter.

Wirklich vielen Dank für die Hilfe


----------



## jeko87 (28. Okt 2010)

so bin nun schon ein ganzes Stück weiter gekommen...
es fehlt mir an sich nur noch 1 Zeile 


```
// hier soll geprüft werden, ob x im Lösungsraum sol(x) enthalten ist
if (x; (a1;...; aj; a)) € sol(x)
{ 
    return true; 
}
```

mein Problem ist jetzt noch, das (x,(a1,...aj,a))
also x ist mein Eingabeparameter, das ist nicht das Problem, nur jetzt (a1,...,aj,a)
also (a1,...,aj) war bis jetzt immer eine Menge, nur jetzt steht noch ein zusätzliches a drin ???:L
kannste mir da nochmal vielleicht helfen ?
sol(x) ist dann wieder der Aufruf meiner methode, also rekursiv..


danke


----------



## mfernau (28. Okt 2010)

Also so ganz komme ich mit eurer Notation da nicht klar - aber egal..
das _a_ scheint sich auf das Element von vorher zu beziehen. Wir hatten ja das _a_ zuvor aus einer Menge erhalten: [c]for a € {1;...; k(x)}[/c].
Nun brauchst Du etwas der Art [c]if (x; (a1;...; aj; a)) € sol(x)...[/c]. Also _(a1;...; aj_ um das _a_ von eben erweitert.
Soll _(a1;...; aj_ jetzt wieder eine Menge sein oder ein n-Tupel?


----------



## jeko87 (28. Okt 2010)

die Notation ist ja auch mein Problem...ja das mit dem "a" leuchtet ein, dass hab ich von vorhin.


```
if (x,(a1,...,aj,a)) € sol(x) then return 1 endif
else if (x,(a1,...,aj,a)) € K then	// evtl. Lsg. im Teilbaum
M := M U {(a1, . . . , aj, a)}
```

womit ich Probleme hab, dass in der 1sten Zeile nur (x(a1,...,aj,a)) steht und in der letzten Zeile bei der Vereinigung wieder { }...


----------



## jeko87 (28. Okt 2010)

ich hab das Problem nun etwas eingegrenzt.
Also die Zeile 

```
if (x,(a1,...,aj,a)) € sol(x) then return 1 endif
```

kontrolliert ja wie gesagt ob es sich um eine gültige Lösung handelt.
In unserem Skript hab ich jetzt die Konditionen gefunden, die dafür gegeben sein müssen.

ai != aj (keine gleiche Zeile) und |ai − aj| !=|i − j| (nicht auf der gleichen Diagonalen)

also müsste es so in etwa zu lösen sein

```
for(Integer a : menge) 
{
    // if (x,(a1,...,aj,a)) € sol(m)             
    int cond1 = ai-aj;
    int cond2 = i-j;                
    // keine gleiche Zeile && nicht auf gleicher Diagonalen
    if ((ai != aj) && (cond1 != cond2)) 
    {
        return true;
    }
```

Das Problem ist nun jedoch das i,j, ai und aj...


----------



## mfernau (28. Okt 2010)

jeko87 hat gesagt.:


> [...]Das Problem ist nun jedoch das i,j, ai und aj...



_i_ & _j_ sind Indizes. Sie nummerieren die Elemente in Deiner Menge. Also das i-te und j-te Element Deiner Menge ist damit gemeint. ai und aj sind dann die tatsächlichen Elemente.

Also ai ist das i-te Element in einer Menge. Z.b. könnte a3 gleich 5 sein.
aj ist das j-te Element in einer Menge. Z.B. könnte a4 gleich 7 sein.
ai - aj bedeutet also, dass du das Element aj vom Element ai abziehen sollst: 
	
	
	
	





```
5-7
```
. Während i-j bedeutet, dass Du die Indizes voneinander abziehen sollst: 
	
	
	
	





```
3-4
```
. Bitte beachte auch die "|" dabei. Wenn sie eine Rechnung umgeben dann sollst Du das Ergebnis Vorzeichenlos betrachten. Einfach ai - aj zu rechnen wäre also nicht ganz korrekt.


----------



## Marco13 (28. Okt 2010)

Also zugegeben: Die Notationen und der Pseudocode sieht schon ein bißchen verwirrend aus. Am besten wäre es wahrscheinlich, den einzuscannen, damit man wenigstens weiß, WEM man das vorwerfen muss (ASCII-Art reicht eben nicht für alle mathematischen Symbole...  )

Aber das in den i und j wird jetzt halt evtl. zum Problem, wenn die Elemente von M wieder Mengen sind: Diese Elemente haben keine feste Reihenfolge. Alle indizes, die man daraus berechnet, sind also nutzlos. Ich würde jetzt mal vermuten, dass die Elemente der Menge immer Listen (tupel) aus 8 Elementen sein sollen.... ist nur geraten, würde aber IMHO Sinn machen...


----------



## jeko87 (28. Okt 2010)

ja ok. Also was vorzeichenlos angeht gibts ja ne Funktion in java, also hab ich mal gelesen...
math.abs()...wenn nicht, das könnte ich auch noch zusammenbasteln

```
if x<0 then x * (-1)
```

denk mal nicht, dass dies mein Problem sein wird 

Was die Indizes angeht, hab ich mir so gedacht, dass ich mir halt 'ne for schleife bastele (pro Index)
und so könnte ich dann die Elemente mit der jeweiligen Position des Indizes ansprechen

halt

```
int cond1 = math.abs(liste(i)-liste(j));
int cond2 = i-j;
for(int i=0; i < liste.size(); i++)
    for (int j=0; j < liste.size(); j++)
        if ((liste(i) != liste(j)) && (cond1 != cond2))
            return true;
```

also ist jetzt vereinfacht...wäre schon wenn es mit "int" gehen würde, krieg jedoch IMMER wieder 'ne Fehlermeldung wegen des Typen...
aber glaub an sich könnte es von der Logik her doch schon stimmen ?


----------



## jeko87 (28. Okt 2010)

hier ist dann der pseudo code


----------



## jeko87 (28. Okt 2010)

So hier ist nur mal der Code, also wie weit ich bis jetzt gekommen bin


```
public boolean solve(int m)
{
    
    // Was ich hier nicht recht versteh, mit dieser Schreibweise, fülle ich root mit m Werten
    // also root={1,2,3,...m}, anschließend kommt menge.add(root)
    // ich versteh es so, dass dann in menge = {{root}} steht, das müsste ich doch auch öfters
    // machen ??

    List<Integer> root = new ArrayList<Integer>();
    int j=0;
    for (int i=0; i<m; i++)
    {
        root.add(i);
    }
        
    // M := {()}; // Menge der aktiven Knoten, Start mit Wurzel
    Set<List<Integer>> menge = new HashSet<List<Integer>>();
    menge.add(root);
        
    while (!menge.isEmpty()) 
    {
        // wähle (a1;...;aj) € M; // Stelle an der eine Dame stehen kann
        List<Integer> i = menge.iterator().next(); 
        // M := M\{(a1;...;aj)}; // Menge aktualisieren
        menge.remove(i);
 
        // for a € {1,...,k(x)}
        for(List<Integer> iter:menge)
        {
            if ((j+1)==d(x))  // Zeile wurde noch nicht vom Pseudo code übersetzt
            {
                 List<Integer> liste = new ArrayList<Integer>();
                 for(int k=0; k < liste.size(); k++)
                 {
                     for (int l=liste.size(); l > 0; l--)  // Schleife beginnt hinten, da sonst k=l wäre
                     {
                         // if (x,(a1,...,aj,a)) € sol(x)
                         int cond1 = Math.abs(liste.get(k)-liste.get(l));    
                         int cond2 = k-l; 
                         // keine gleiche Zeile und nicht auf gleicher Diagonalen
                         if ((liste.get(k) != liste.get(l)) && (cond1 != cond2))
                         {
                             return true;
                         }
                     }
                 }
```

also es besteht immer noch das Problem mit den einzelnen Datentypen, da komm ich schon recht durcheinander...also Set, List, ArrayList, dann wieder int

aber ich hoffe, dass mein code wenigstens von der Logik her etwas hergibt, sonst war wirklich viel Arbeit für die Katz

danke danke
mfG


----------



## mfernau (29. Okt 2010)

> also es besteht immer noch das Problem mit den einzelnen Datentypen, da komm ich schon recht durcheinander...also Set, List, ArrayList, dann wieder int


Das ist genau das, was ich mit meinem Antwortpost zu Marco13s Einwand meinte. Auch wenn er Recht hast würde mich das als Einsteiger in diese Thematik etwas verwirren und mich vom Kernthema ablenken. 
Du musst versuchen die Übersicht darüber zu behalten und ein abstraktes Denken für so etwas zu entwickeln.

Okay, also dann sind {} Mengen und () Tupel. Der Unterschied zwischen einer Menge und Tupeln ist ja halbwegs klar denke ich. Wichtig ist hier jedenfalls, dass Tupel geordnet sind.
Also 
	
	
	
	





```
M := {()}
```
 bedeutet dann, dass Du in M ein leeres Tupel hast.

() kann man problemlos mit einer List definieren.


			
				Javadoc hat gesagt.:
			
		

> public interface List
> extends Collection
> 
> An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.



und M ist perfekt für ein Set


			
				Javadoc hat gesagt.:
			
		

> public interface Set
> extends Collection
> 
> A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.



Damit bist Du schon mal auf dem richtigen Weg was diese Elemente betreffen.
Laut Deinem Algorithmus fängst Du allerdings mit einem M an, dass ein leeres Tupel beinhaltet.

```
public boolean solve(int x)
{
    Set<List<Integer>> M = new HashSet<List<Integer>>();
    M.add(new ArrayList<Integer>());
    while (!M.isEmpty()) 
    {
        // wähle (a1;...;aj) € M; // Stelle an der eine Dame stehen kann
        List<Integer> tupel = menge.iterator().next(); 
        // M := M\{(a1;...;aj)}; // Menge aktualisieren
        menge.remove(tupel);
```

soweit ist das exakt das, was Dein Algorithmus verlangt. Nun hänge ich aber an der Notation bei euch. Was ist k(x)? was ist d(x)? Was ist K und wo kommt sol(x) her?

x ist Deine Eingabe. Also bei einem normalen Schachbrett vermutlich 8.
sol(x) soll eine Fkt sein, die eine Menge der Lösungen für das x-Damenproblem bereit stellt. Oder?
Demnach soll dieser Algorithmus also nur prüfen, ob es eine Lösung für das x-Damenproblem gibt?

Mir fehlen hier irgendwie die Informationen um zu Wissen was 
	
	
	
	





```
{1,...,k(x)}
```
, 
	
	
	
	





```
j+1=d(x)
```
 [c](x,(a1,...,aj,a)) e sol(x)[/c] oder [c](x,(a1,...,aj,a)) e K[/c] wirklich bedeuten soll


----------



## Marco13 (29. Okt 2010)

Weiter oben stand schon
        //k(x) Anzahl Möglichkeiten
        //d(x) Dimension Lösungsraum

Hab's gerade mal ausimplementiert: In diesem Fall tut's schon k(x)=d(x)=x

(x,(a1,...,aj,a)) e K
Bedeutet, dass die Teillösung konsistent ist (das ist das mit dem |i-j| und |ai-aj| von der vorigen Seite)

(x,(a1,...,aj,a)) e sol(x) 
Bedeutet, dass (a1,...,aj,a) eine Lösung ist - also eine Konsistente Teillösung, die d(x) Elemente enthält.


----------



## jeko87 (29. Okt 2010)

Also vielen Dank nochmal für die Erklärung zu den Datentypen.

1) Ja, der Algorithmus soll NUR true oder false ausgeben. Wenn ich z.B 1 oder 2 als Eingabeparameter habe, soll false rauskommen. 

2) sol(x) ist der Lösungsraum bei Eingabe x...also hier wird kontrolliert ob die Konditionen erfüllt sind, 
|ai-aj| != |i-j| und ai != aj

3) K ist im Skript als Backtracking-Kriterium beschrieben. 
"Das sog. Backtracking-Kriterium K stellt für einen inneren Knoten (a1, a2, . . . , aj ) fest, dass es im zugehörigen Teilbaum keine zulässigen Lösungen gibt."

4) d(x) die Dimension des Lösungsraums und k(x) die Anzahl Möglichkeiten je Dimension


Tut mir leid, hätte diese Informationen früher angeben müssen...sorry sorry


----------



## LoR (29. Okt 2010)

Da ich den Thread auch schon länger verfolge hier mal 3 "verschiedene" Lösungen für diejenigen die das gleiche Problem bearbeiten.


```
public interface NQueensSolver {

    public int solve();
}
```

*Die "naive" Lösung*

```
public class NQueensNaiveSolverImpl implements NQueensSolver {

    private final int[] gameField;
    private final int nQueens;

    public NQueensNaiveSolverImpl(int nQueens) {
        this.gameField = new int[nQueens];
        this.nQueens = nQueens;
    }

    @Override
    public int solve() {
        return search(0, 0);
    }

    private int search(int currentRow, int solutions) {
        if (currentRow >= nQueens) {
            return ++solutions;
        }

        for (int row = 0; row < nQueens; row++) {
            gameField[currentRow] = row;

            if (!hasCollison(currentRow)) {
                solutions = search(currentRow + 1, solutions);
            }
        }
        return solutions;
    }

    private boolean hasCollison(int currentRow) {
        for (int row = 0; row < currentRow; row++) {
            int difColumn = Math.abs(gameField[row] - gameField[currentRow]);
            int difRow = Math.abs(row - currentRow);

            if (difColumn == 0 || difColumn == difRow) {
                return true;
            }
        }
        return false;
    }
}
```

*Eine optimierte Variante*

```
public final class NQueensSolverImpl implements NQueensSolver {

    private final int[] gameField;
    private final int nQueens;
    private final int maxProblemSpace;

    public NQueensSolverImpl(int nQueens) {
        this.gameField = new int[nQueens];
        this.nQueens = nQueens;
        this.maxProblemSpace = nQueens / 2;
    }

    @Override
    public int solve() {
        int solutions = 0;
        for (int row = 0; row < maxProblemSpace; row++) {
            gameField[0] = row;
            solutions += search(1, 0);
        }
        solutions *= 2;
        if (nQueens % 2 != 0) {
            gameField[0] = maxProblemSpace;
            solutions += search(1, 0);
        }
        return solutions;
    }

    private int search(int currentRow, int solutions) {
        if (currentRow >= nQueens) {
            return ++solutions;
        }

        for (int row = 0; row < nQueens; row++) {
            gameField[currentRow] = row;

            if (!hasCollison(currentRow)) {
                solutions = search(currentRow + 1, solutions);
            }
        }
        return solutions;
    }

    private boolean hasCollison(int currentRow) {
        for (int row = 0; row < currentRow; row++) {
            int difColumn = Math.abs(gameField[row] - gameField[currentRow]);
            int difRow = Math.abs(row - currentRow);

            if (difColumn == 0 || difColumn == difRow) {
                return true;
            }
        }
        return false;
    }
}
```

*Die optimierte Variante mit mehreren Threads*

```
import java.util.concurrent.Callable;

public class NQueensProblem implements Callable<Integer> {

    private final int[] gameField;
    private final int nQueens;

    public NQueensProblem(int nQueens, int startColumn) {
        this.nQueens = nQueens;
        this.gameField = new int[nQueens];
        this.gameField[0] = startColumn;
    }

    @Override
    public Integer call() throws Exception {
        return search(1, 0);
    }

    private int search(int currentRow, int solutions) {
        if (currentRow >= nQueens) {
            return ++solutions;
        }

        for (int row = 0; row < nQueens; row++) {
            gameField[currentRow] = row;

            if (!hasCollison(currentRow)) {
                solutions = search(currentRow + 1, solutions);
            }
        }
        return solutions;
    }

    private boolean hasCollison(int currentRow) {
        for (int row = 0; row < currentRow; row++) {
            int difColumn = Math.abs(gameField[row] - gameField[currentRow]);
            int difRow = Math.abs(row - currentRow);

            if (difColumn == 0 || difColumn == difRow) {
                return true;
            }
        }
        return false;
    }
}
```


```
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.TimeUnit;

public class NQueensThreadSolverImpl implements NQueensSolver {

    private final int nQueens;
    private final int nThreads;
    private final boolean evenProblem;
    private final List<NQueensProblem> nQueensProblemSpace;

    public NQueensThreadSolverImpl(int nQueens, int nThreads) {
        this.nQueens = nQueens;
        this.evenProblem = (nQueens % 2 == 0);
        this.nQueensProblemSpace = buildNQeensProblemSpace();
        int problemSpaceSize = nQueensProblemSpace.size();
        this.nThreads = nThreads > problemSpaceSize ? problemSpaceSize : nThreads;
    }

    private List<NQueensProblem> buildNQeensProblemSpace() {
        List<NQueensProblem> nqeensProblems = new ArrayList<NQueensProblem>();
        int maxColumns = nQueens / 2;
        for (int i = 0; i < maxColumns; i++) {
            nqeensProblems.add(new NQueensProblem(nQueens, i));
        }
        if (!evenProblem) {
            nqeensProblems.add(new NQueensProblem(nQueens, maxColumns));
        }
        return Collections.unmodifiableList(nqeensProblems);
    }

    @Override
    public int solve() throws RuntimeException {
        int solutions = 0;
        try {
            solutions = execute();
        } catch (Exception ex) {
            handleException(ex);
        }
        return solutions;
    }

    private int execute() throws InterruptedException, ExecutionException {
        ExecutorService execService = Executors.newFixedThreadPool(nThreads);
        int solutions = 0;
        try {
            List<Future<Integer>> resultList = execService.invokeAll(nQueensProblemSpace);

            int problemSpaceSize = nQueensProblemSpace.size();
            for (int i = 0; i < problemSpaceSize - 1; i++) {
                Future<Integer> result = resultList.get(i);
                solutions += result.get();
            }

            int lastResult = resultList.get(problemSpaceSize - 1).get();
            solutions = (evenProblem ? (solutions + lastResult) * 2 : solutions * 2 + lastResult);
        } finally {
            execService.shutdown();
            execService.awaitTermination(60, TimeUnit.SECONDS);
        }
        return solutions;
    }

    private void handleException(Exception ex) {
        throw new RuntimeException(ex.getMessage(), ex);
    }
}
```

*Eine Testklasse*

```
public class Main {

    public static void main(String[] args) {
        int nThreads = Runtime.getRuntime().availableProcessors();
        int nQueens = 14;

        System.out.printf("Number of queens: %d%n", nQueens);
        System.out.println();
        
        long millis = System.currentTimeMillis();
        NQueensSolver naiveSolver = new NQueensNaiveSolverImpl(nQueens);
        System.out.printf("Solutions: %d%n", naiveSolver.solve());
        System.out.printf("Problem solved in: %d seconds.%n", ((System.currentTimeMillis() - millis) / 1000));

        System.out.println();

        millis = System.currentTimeMillis();
        NQueensSolver solver = new NQueensSolverImpl(nQueens);
        System.out.printf("Solutions: %d%n", solver.solve());
        System.out.printf("Problem solved in: %d seconds.%n", ((System.currentTimeMillis() - millis) / 1000));

        System.out.println();

        millis = System.currentTimeMillis();
        NQueensSolver threadSolver = new NQueensThreadSolverImpl(nQueens, nThreads);
        System.out.printf("Solutions: %d%n", threadSolver.solve());
        System.out.printf("Problem solved in: %d seconds.%n", ((System.currentTimeMillis() - millis) / 1000));
    }
}
```

*Ergebnis*

```
Number of queens: 14

Solutions: 365596
Problem solved in: 20 seconds.

Solutions: 365596
Problem solved in: 10 seconds.

Solutions: 365596
Problem solved in: 5 seconds.
```


----------



## jeko87 (29. Okt 2010)

vielen Dank für deine Lösungen.
Ich kann diese zwar selbst nicht übernehmen, aber ist vielleicht etwas dabei was mir weiterhilft

danke


----------



## Marco13 (29. Okt 2010)

LoR hat gesagt.:


> Da ich den Thread auch schon länger verfolge hier mal 3 "verschiedene" Lösungen für diejenigen die das gleiche Problem bearbeiten.



Ein Teil des Problems ist, dass es so gemacht werden sollte, wie es im Pseudocode steht. Wie "sklavisch" man sich daran halten muss, weiß man nicht, aber vielleicht ist das ja nicht so wichtig...


----------



## jeko87 (29. Okt 2010)

also es muss nicht eine 1 zu 1 Implementierung des Pseudo codes sein, aber die Struktur soll schon übereinstimmen...es soll mit den Mengen gearbeitet werden, es soll auch nur die eine Methode geschrieben werden...wobei "nur", mir schon mehr als genug Probleme bereitet


----------



## Landei (29. Okt 2010)

Hier meine Version:


```
import java.util.ArrayList;
import java.util.List;
import static java.lang.Math.abs;

public class Queens {

    private static boolean safe(Pos p, Pos q) {
        return p.x != q.x && p.y != q.y && abs(p.x - q.x) != abs(p.y - q.y);
    }

    private static List<List<Pos>> qu(int n, int k, List<List<Pos>> qss) {
        List<List<Pos>> result = new ArrayList<List<Pos>>();
        for(List<Pos> qs : qss) {
            for(int j = 1; j <= n; j++) {
                Pos p = new Pos(j, k);
                boolean isSafe = true;
                for(Pos q : qs) {
                    if (! safe(p,q)) {
                        isSafe = false;
                        break;
                    }
                }
                if (isSafe) {
                    List<Pos> p_qs = new ArrayList<Pos>();
                    p_qs.addAll(qs);
                    p_qs.add(p);
                    result.add(p_qs);
                }
            }
        }
        return result;
    }

    private static List<List<Pos>> nqueens(int n) {
        List<List<Pos>> result = new ArrayList<List<Pos>>();
        result.add(new ArrayList<Pos>());
        for (int k = 1; k <= n; k ++) {
            result = qu(n, k, result);
        }
        return result;
    }

    public static void main(String[] args) {
        for(List<Pos> solution : nqueens(8)) {
           System.out.println(solution);
        }
    }

    private static class Pos {
        final int x;
        final int y;
        private Pos(int x, int y){
            this.x = x;
            this.y = y;
        }
        @Override public String toString() { return "(" + x + "," + y + ")"; }
    }
}
```

Kaum länger als die anderen Lösungen hier (statt der Pos-Klasse würde es auch java.awt.Point tun).

Das ist eine Übersetzung von diesem Programm (Scala):

```
object queens {

   def nqueens(n: Int) = {
      import math.abs
      type Pos = (Int, Int)
      def safe(p:Pos, q:Pos) = p._1 != q._1 && p._2 != q._2 && abs(p._1 - q._1) != abs(p._2 - q._2)
      def qu(k: Int, qss:List[List[Pos]]) =
        for(qs <- qss; j <- (1 to n) if qs.forall(safe(_ ,(j,k)))) yield ((j,k) :: qs)
      (1 to n).foldRight(List(List[Pos]()))(qu)
   }

   def main(args:Array[String]) = println(nqueens(8).mkString("\n"))
}
```

Und das ist wiederum eine Übersetzung von diesem Programm in Haskell (die erste Zeile könnte man noch weglassen):

```
nqueens :: Int -> [[(Int,Int)]]
nqueens n = foldr qu [[]] [1..n]
    where qu k qss = [((j,k):qs) | qs <- qss, j <- [1..n], all (safe (j,k)) qs]
      safe (j,k) (l,m) = j /= l && k /= m && abs (j-l) /= abs (k-m)
```
(Quelle: N-Queens in Haskell : programming)

Schon eindrucksvoll, was übrig bleibt, wenn man sich auf das Wesentliche konzentriert.


----------



## jeko87 (29. Okt 2010)

wow, also Leute, ich kann mich nicht oft genug für die Hilfe bedanken.
Ich versuch mal die Elemente aus deinem Code bei mir zu implementieren...
wie gesagt, mir reicht eigentlich schon, wenn ich als Ausgabe "true" oder "false" hab...ich muss nicht die ganzen Möglichkeiten rausschreiben 

versuch mein Glück

vielen Dank
mfG


----------



## LoR (30. Okt 2010)

Pfff, was Scala kann kann Java schon lange :bae:

*Minimallösung*

```
public class NQueensMinimalSolver {
    public static int solveNQueens(int[] gf, int r, int s) {
begin:  for (int i = 0; i < gf.length && r < gf.length; i++) {
            gf[r] = i;
            for (int j = 0, dif = 0; j < r; j++)
                if ((dif =  Math.abs(gf[j] - gf[r])) == 0 || dif == Math.abs(j - r)) continue begin;
            s = solveNQueens(gf, r + 1, s);
        }
        return r >= gf.length ? ++s : s;
    }
}
```

*Aufruf*

```
NQueensMinimalSolver.solveNQueens(new int[10], 0, 0)
```

Da fühlt man sich direkt in die guten alten Goto-Zeiten zurückversetzt.


----------



## Landei (30. Okt 2010)

Na ja, dann wird es unleserlich. Code-Golf kann ich auch, wenn man es darauf anlegt, geht es kürzer:

```
object queens { def nq(n: Int) = {
def sf(p:(Int,Int), q:(Int,Int)) = p._1!=q._1&&p._2!=q._2&&math.abs(p._1-q._1)!=math.abs(p._2-q._2)
def qu(k:Int,qss:List[List[(Int,Int)]]) = for(qs<-qss;j<-(1 to n) if qs.forall(sf(_ ,(j,k)))) yield((j,k)::qs)
(1 to n).foldRight(List(List[(Int,Int)]()))(qu)}}
```
Ja, das funktioniert (in Simply Scala kopieren, ausführen und queens.nq(8) aufrufen).

Und das sind nur die offensichtlichen Änderungen, es ginge noch wesentlich kürzer...


----------

