Damenproblem mit Backtracking

[jeko87]

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]

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]

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]

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]

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]

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]

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

for (Integer i : n) { ...

 

[mfernau]

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.

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

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

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...

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)}.

also würd ich zuerst das gelöschte Element speicheren, so in etwa

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

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]

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]

OT

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]

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]

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]

[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]

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]

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]

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]

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]

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]

[...]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]

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]

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]

hier ist dann der pseudo code

 

[jeko87]

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]

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.

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

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]

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]

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]

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]

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

danke

 

[Marco13]

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]

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]

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]

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]

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]

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...