# Anfang des Damenproblems



## Beginner94 (18. Mrz 2011)

Hallo!
Ich lerne seit einem halben Jahr Java in meiner Schule(2h pro Woche). Doch da die Aufgaben langsamg langweilig werden, habe ich mir eine schwierigere Aufgabe gesucht und zwar das Damnproblem. Ich weiß nicht ob ihr es kennt, wenn nicht, es geht darum, 8 Damen auf einem Schachfeld so zu verteilen, dass sie sich nicht gegenseitig schlagen können. Um alle Möglichkeiten herauszufinden ist mein LösungsANSATZ so:
Ich nehme ein Feld auf dem die Dame steht und setzte alle Felder(bis jetzt noch =0) nach oben/unten und rechts/links und Schrägoben/schrägunten auf 1. Um meine Gedanken weiter zu erklären dauerts zu lang, außerdem hänge ich jetzt schon fest und komme nicht weiter 
Im folgenden Quellcode nehm ich nur das Feld 0 0 und will wie grad beschrieben die Felder auf 1 setzen. Doch in meiner Methode ausgabe kommt 0 raus obwohl ich 1 haben will. 
Ich hoffe, ihr könnt mir helfen.

Danke im Voraus

Hier ist der Quellcode

```
public class BERECHNUNG
{
    
   int[][] feld;
   int z1=0; //y nach oben
   int z2=0; //y nach unten
   int z3=0; //y schraeg oben
   int z4=0; //y schraeg unten
   int v1=0; //x nach rechts
   int v2=0; //x nach links
   int v3=0; //x schraeg rechts
   int v4=0; //x schraeg links
   
   int a=0;
   int b=0;
    
    public BERECHNUNG()
    {
        feld = new int[8][8];
    }
    
    public void einssetzen()
    {
        for (int y=0;y<a;y++)
        {
            z1=y;
            z2=y;
            z3=y;
            z4=y;
            for (int x=0;x<b;x++)
            {
                    v1=x;
                    v2=x;
                    v3=x;
                    v4=x;

                    feld[y][x]=1;
                    while( z1<=7 )           //y nach oben
                    {
                        feld[z1][x]=1;
                        z1++;
                    }
                    while( z2>=0 )           //y nach unten
                    {
                        feld[z2][x]=1;
                        z2--;
                    }
                    while( v1>=7 )           //x nach rechts
                    {
                        feld[y][v1]=1;
                        v1++;
                    }
                    while( v2>=0 )           //x nach links
                    {
                        feld[y][v2]=1;
                        v2--;
                    }
                    while( z3>=7 && v3>=7)    //schraeg nach rechts oben
                    {
                        feld[z3][v3]=1;
                        z3++;
                        v3++;
                    }
                    while( z4>=0 && v4>=0)    //schraeg nach links oben
                    {
                        feld[z4][v4]=1;
                        z4--;
                        v4--;
                    }  
            }
        }
    }
    
    public void ausgabe()
    {
        System.out.println(feld[7][7]);
    }
}
```


----------



## Andi_CH (18. Mrz 2011)

Schreib ein ganz kleines Hauptprogramm
Nimm einen Debugger und finde heraus was "a" in der Schleife in der Methode "einsetzen()" für einen Wert hat ...

Vielleicht schaffst du es auch ohne Debugger durch codereading


----------



## Beginner94 (18. Mrz 2011)

Die variable a hat in der schleife den Wert 0. Jetzt check ichs 
Ein leichtsinnsfehler, sry, aber wenn ich a und b lösche und dafür eine 1 einsetzte geht es leider trotzdem nicht.
Meine einzige Idee ist, dass der Wert des Feldes nur innerhalb einer Schleife gespeichert wird und für die anderen immer 0 ist.
Aber ich weiß nicht, ob das der Fehler ist.
Ich bin ahnungslos


----------



## icarus2 (19. Mrz 2011)

Ich hatte als Thema meiner Maturaarbeit das N-Damen Problem. Im Moment verstehe ich nicht, was dein Algorithmus macht. Ich würde dir empfehlen, das Problem durch rekursives Backtracking zu lösen. Damit kommst du auf eine ziemlich schöne Lösung.

Suche mal auf Wikipedia oder so wie du die Damen am besten setzen kannst.

Falls du später möchtest, kann ich auch mal meinen Code ausgraben und hier posten.


----------



## Beginner94 (20. Mrz 2011)

Ich versuche nochmal meinen Lösungsansatz zu erklären.
Ich fange an, die erste Dame auf das feld 00 zu setzen. Alle 64 Felder haben den Wert 0.
Danach setze ich alle Felder, die nach oben, rechts und schräg oben(das gleiche nach unten etc.) von der Dame aus gehen auf den Wert 1. 
Nun setze ich die 2.Dame in der 2.Reihe auf das erste Feld mit dem Wert 0 und setze wieder wie oben beschrieben die betreffenden Felder auf 1. 
Dann setze ich die 3. Dame in der 3.Reihe auf das erste Feld mit dem Wert 0, etc.
Wenn in Reihe 8 noch ein Feld mit dem Wert 0 übrig bleibt, habe ich eine Lösung.
So gehe ich nicht alle Möglichkeiten durch, 8 Damen zu setzen.
Wenn ihr denkt, dass das zu aufwendig ist und mir von diesem Lösungsansatz abratet, setze ich mich im Internet mit dem rekursiven Backtracking auseinander. Ich wollte einfach nur selbst auf eine Lösung kommen und nicht alles abschauen. Denn da ist immer so ein tolles Gefühl wenn man etwas alleine geschafft hat und es gut funktioniert, wenn ihr wisst was ich meine 

Ich bin auf eure Antworten gespannt!


----------



## Beginner? (20. Mrz 2011)

Andere Leute hatten sicher auch ein gutes Gefühl, wenn sie bedeutende Algorithmen erfunden haben^^

Warum wird die Methode, die verschiedene Arrayelemente verändert, nirgends aufgerufen?

Was du versuchst zu schrieben, kann nur mit 8 ineinander geschachtelten Schleifen funktionieren, was kein guter Programmierstiel deshalb ist, weil sich mit selber Lösung keine Probleme beliebiger Brettgrößen lösen lassen.

Wenn du dich nicht mit Rekursion beschäftigst, kommst zu keiner lesbaren Lösung. Für das Problem muss ja ausprobiert werden, ob auf Felder gesetzte Damen sich sehen oder nicht. Ist das der Fall, waren die gesetzten Damen nicht auf den richtigen Feldern und müssen umgesetzt werden. Es kann berücksichtigt werden, dass in jeder Reihe/Spalte nur jeweils eine Dame gesetzt sein kann, damit sich Damen nicht gegenseitig sehen. Weiterhin kann berücksichtigt werden, dass bereits eine Teilmenge gesetzter und sich sehender Damen die Lösung hinfällig macht.


----------



## Beginner94 (20. Mrz 2011)

Ok. Dann setze ich mich jetzt mit rekursivem backtracking auseinander.


----------



## LoR (20. Mrz 2011)

Das wurde auch hier im Forum schon ausführlich besprochen.

z.B.
http://www.java-forum.org/allgemeine-java-themen/107798-damenproblem-backtracking-2.html


----------



## Beginner94 (21. Mrz 2011)

Ich hab mir jetzt das rekursive Backtraking angeschaut.
Ich versuche es erst mal mit einem 4*4 Schachfeld. Mein Programm ist jetzt so weit, dass es die 1.Zeile durchgeht und das erste unbesetzte Feld mit einer Dame besetzt. Danach geht es automatisch in die nächste Zeile und macht das gleiche, usw.
Jetzt bin ich aber wieder an dem Punkt angelangt, an dem ich die von der Dame bedrohten Felder bestimmen muss.
Ist das jetzt ein Fehler wenn ich wieder vesuche eine Methode dazu zu schreiben?


----------



## Beginner? (21. Mrz 2011)

Nööö, kann man.

Du hast bestimmt keine Lust, längere komplexere Texte zulesen, wie 80 % auch. Deshalb hier ein minimales Beispiel mit Kommentierung:


```
public static boolean solveViaBT(boolean[][] game, int row) {
        if (row == 8) { // Abbr.
            return true;
        }

        for (int col = 0; col < 8; col++) { // Kand.
            game[row][col] = true; // Kand. einf.
            if (valid(game, row, col)) { // Kand. richtig
                printGame(game);
                if (solveViaBT(game, row + 1)) { // andere Kand. richtig
                    return true; // Loes.
                }
            }
            game[row][col] = false; // Kand. rueckgaeng.
        }

        return false; // Keine Loes.
    }

    private static boolean valid(boolean[][] game, int row, int col) {
        // vertikal
        for (int rowA = 0; rowA < game.length; rowA++) {
            if (game[rowA][col] && rowA != row) {
                return false;
            }
        }

        // diagonal
        // ??????

        return true;
    }

    private static void printGame(boolean[][] game) {
        for (boolean[] ba : game) {
            System.out.println(Arrays.toString(ba));
        }

        System.out.println();
    }

    public static void main(String[] args) {
        solveViaBT(new boolean[8][8], 0);
    }
```

Die Prüfung, ob auf den Diagonalen Damen sich befinden, musst du selbst schreiben. Beim Schreiben habe ich mich hieran Backtracking ? Wikipedia und hieran Damenproblem ? Wikipedia orientiert. Es können auch alle Möglichkeiten berechnet werden, lässt man bei row=8 nicht nicht zurückgeben, oder zufällige, mischt man die Kandidaten.


----------



## Beginner94 (21. Mrz 2011)

Danke für deine Lösung.
Ich bin noch am versuchen sie zu verstehen 
kann ich nicht auch einfach schleifen machen?


----------



## Beginner? (21. Mrz 2011)

ja, das würde für ein 3x3-Feld ungefähr so sein:


```
boolean[][] game = new boolean[3][3];

        for (int i = 0; i < game[0].length; i++) {
            game[0][i] = true;
            if (valid(game, 0, i)) {
                for (int j = 0; j < game[1].length; j++) {
                    game[1][j] = true;
                    if (valid(game, 1, j)) {
                        for (int k = 0; k < game[2].length; k++) {
                            game[2][k] = true;
                            if (valid(game, 2, k)) {
                                // Loesung
                            } else {
                                // Rueckgaengig
                            }
                        }
                    } else {
                        // Rueckgaengig
                    }
                }
            } else {
                // Rueckgaengig
            }
        }
```

Du siehst, es wird unübersichtlich. Man kann auch mit einer Queue die Rekursion direkt auflösen.

Ich würde mir wirklich zuerst Rekursion pauken in Bezug auf java und dann Backtracking an einfachen Beispielen verstehen und dann selbst schreiben..


----------



## Beginner? (21. Mrz 2011)

Mit der obigen valid()-Methode kommt, wenn man den else-Zweig weg lässt - das muss man auch(!!) -, eine ganz interessante Ausgabe:


```
public static void main(String[] args) {

        boolean[][] game = new boolean[3][3];

        for (int i = 0; i < game[0].length; i++) {
            game[0][i] = true;
            if (valid(game, 0, i)) {
                for (int j = 0; j < game[1].length; j++) {
                    game[1][j] = true;
                    if (valid(game, 1, j)) {
                        for (int k = 0; k < game[2].length; k++) {
                            game[2][k] = true;
                            if (valid(game, 2, k)) {
                                printGame(game);
                            }
                            game[2][k] = false;
                        }
                    }
                    game[1][j] = false;
                }
            }
            game[0][i] = false;
        }

    }
```


----------



## Beginner94 (22. Mrz 2011)

Ich hab jetzt schon einiges dazu gelernt, doch ich möchte mein schachfeld mit 0,1 und 2 besetzen.
0= unbestztes Feld
1= bedrohtes Feld
2= Dame auf dem Feld

Ich könnte doch auch 3 oder 6 schleifen machen die nicht in einander verschachtelt sind um die bedrohten Felder herauszufinden ohne dass ich true und false und das ganze Zeug benutze, da ich mich noch nicht so gut damit auskenne. Außerdem braucht man doch eigentlich 3 typen, für unbestztes, bedrohtes und mit Dame besetztes Feld. Wie reicht da true und false?


----------



## Beginner94 (22. Mrz 2011)

Ich hab mir grad meinen Quellcode angeschaut, den ich gepostet hab, und einige Fehler gefunden.
Aber eigentlich müsste es doch so gehen (wenn die Fehler behoben sind)?!


----------



## Beginner94 (22. Mrz 2011)

Mein Quellcode wäre jetzt so, wenn z=waagerecht und j=senkrecht:


```
public void bedrohung()
    {

        while( z<4 ) // nach unten
        {
            z++;
            feld[z][j] = 1;
        }
        
        while( z>0 ) // nach oben
        {
            z--;
            feld[z][j] = 1;
        }
        
        while( j<4 ) //nach rechts
        {
            j++;
            feld[z][j] = 1;
        }
        
        while( j>0 ) //nach links
        {
            j--;
            feld[z][j] = 1;
        }
        
        while( z<4 && j<4 ) //nach rechts unten
        {
            z++;
            j++;
            feld[z][j] = 1;
        }
        
        while( z<4 && j>0 ) //nach links unten
        {
            z++;
            j--;
            feld[z][j] = 1;
        }
        
        while( z>0 && j<4 ) //nach rechts oben
        {
            z--;
            j++;
            feld[z][j] = 1;
        }
        
        while( z>0 && j>0 ) //nach links oben
        {
            z--;
            j--;
            feld[z][j] = 1;
        }
    }
```


----------



## kirax (22. Mrz 2011)

Ich kann nachvollziehen, dass du gern auf deine eigene Lösung kommen möchtest. Aber die Lösung wird dich kaum erfreuen. Sie ist unübersichtlich und höchstwahrscheinlich auch noch extrem langsam.
Wenn du die Lösung mit rekursivem Backtracking hinbekommst, wirst du a) eine einfache, aber recht effiziente Lösung sehen, b) Rekursion verstehen lernen und c) die Lösung leicht optimieren können. Darüberhinaus ist die Lösung gleich die Lösung des N-Damenproblems (nicht nur 8) 

Nichtsdestotrotz ist das N-Damenproblem keine leichte Aufgabe für Einsteiger. Also erwarte nicht zu früh zu viel von dir.
Aber wenn man es schafft, ist es ein cooles Gefühl (spreche aus Erfahrung ^^).


----------



## Beginner94 (22. Mrz 2011)

Ich hab schon wieder Fehler gefunden. Überall, wo eine 4 steht, muss eine 3 stehen.
Aber dann habe ich eine Endlosschleife mit meiner anderen methode, neueZeile() :


```
public void neueZeile()
    {
        for( j=1; j<n; j++ )
        {
            if( feld[z][j] == 0 )
            {
                j--;
                feld[z][j] = 2;
                if( feld[z][j] == 2 )
                {
                    bedrohung();
                }
                System.out.println("feld["+z+"]["+j+"]= "+feld[z][j] );
                if( z<3 )
                {
                    z++;
                }
                else
                {
                    break;
                }
            }
        }    
    }
```


----------



## Beginenr94 (22. Mrz 2011)

Ich weiß, dass es eine schwere Aufgabe für Anfänger ist.
Aber ich will die Aufgabe schaffen.
Ist es nicht rekursives Backtracking, wenn ich folgendes mache:
erstes 0-Feld auf 2 setzten   //Dame gesetzt
alle bedrohten Felder auf 1 setzen
nächste Zeile erstes 0-Feld auf 2 setzen  //2.Dame gesetzt
alle bedrohten Felder von Dame 2 auf 1 setzen
usw.
bis kein 0-Feld für Dame,
dann eine Zeile zurück, nächstes 0 Feld auf 2 setzen
alle bedrohten Felder auf 1
usw.

ist das nicht rekursives Backtracking?


----------



## xehpuk (22. Mrz 2011)

Weil sich j nie mehr ändert, wenn du einmal in die if kommst.


----------



## Beginner94 (22. Mrz 2011)

Aber wenn er alle schleifen von bedrohung()  durch hat, müsste er doch aus dem if rausgehen und ganz normal weitermachen, oder?


----------



## kirax (22. Mrz 2011)

Du musst beim korrigierten Setzen einer Dame die dadurch nicht mehr bedrohten Felder wieder auf 0 setzen. Das wird schön komplex.
Alternativ kannst du dir verschiedene Bretter "zwischenspeichern", auf die du zurückgreifen kannst, falls was schief ging. BÄM wären wir bei Rekursion


----------



## Beginner94 (22. Mrz 2011)

und noch ne Frage:
bei bedrohung() in der ersten while schleife. wenn er aus der schleife rausgeht, dann hat z schon noch den wert, den er vor der schleife hatte oder?


----------



## xehpuk (22. Mrz 2011)

Beginner94 hat gesagt.:


> Aber wenn er alle schleifen von bedrohung()  durch hat, müsste er doch aus dem if rausgehen und ganz normal weitermachen, oder?


Ja, macht er auch. Nur wenn der Wert bei 
	
	
	
	





```
feld[z][j]
```
 immer 0 bleibt, dann wird j nach dem Inkrementieren auch immer wieder dekrementiert.
Beispiel:

```
static void endless() {
    for (int j = 0; j < 10; j++) {
        if (j == 5) {
            System.out.println(j--);
        }
    }
}
```



Beginner94 hat gesagt.:


> und noch ne Frage:
> bei bedrohung() in der ersten while schleife. wenn er aus der schleife rausgeht, dann hat z schon noch den wert, den er vor der schleife hatte oder?


Du veränderst ihn in der Schleife, also: Nein.


----------



## kirax (22. Mrz 2011)

Du musst die Zustände zwischenspeichern. Das kann man selber machen, muss man aber nicht (ich sag nur Rekursion).


----------



## Beginner94 (22. Mrz 2011)

Ok.
ich dachte rekursives Backtracking ist das:

Manchmal muss man einen Schritt zurückgehen, um 2 Schritte nach vorn zu kommen. Nach diesem Prinzip arbeitet das Backtracking-Verfahren.
• Man führt einen Algorithmus so lange aus, bis man an eine Grenze stößt.
• Ist das der Fall, kehrt man zum letzten Schritt zurück und testet einen anderen Folgeschritt.
• Versuche, eine gültige Teillösung auf dem Weg zum Ergebnis zu finden.
• Baue auf diese Teillösung den restlichen Weg zum Ziel auf.
• Ist das nicht möglich, versuche eine andere Teillösung zu finden.

Was muss ich dann grundsätzlich ändern, um Rekursion zu machen?


----------



## Beginner? (22. Mrz 2011)

Beginenr94 hat gesagt.:


> Ich weiß, dass es eine schwere Aufgabe für Anfänger ist.
> Aber ich will die Aufgabe schaffen.
> Ist es nicht rekursives Backtracking, wenn ich folgendes mache:
> erstes 0-Feld auf 2 setzten   //Dame gesetzt
> ...



Im Prinzip ist es das Teilweise. Es kann vorkommen, dass alle Felder entweder besetzt oder bedroht sind, aber noch nicht alle Damen gesetzt werden konnten. Dann ist die bisherige Lösung hinfällig und Schritte müssen rückgängig gemacht werden. Das ist BT (!) - das Probieren aller Möglichkeiten schrittweise und nur solange, wie die Teillösung gültig ist. Das muss für Anfänger wie böhmische Dörfer klingen. Auf den zwei Wikipedia-Seiten oben wird das aber gut erklärt.

Die BT-Methode arbeitet z.B. so: Es gibt eine Lösung, die vollständig sein kann oder nicht und die gültig sein kann oder nicht. Die Lösung ist ein 2D-boolean-Array, dessen Einträge false sind, wenn keine Dame sich an der entsprechenden Stellen befindet, oder true. Es werden nun alle Möglichkeiten ausprobiert, 8 Damen auf dem 8x8-Feld so zu platzieren, dass die Lösung vollst. und gültig ist. Sie ist gültig, wenn keine zwei Damen sich schlagen können, und vollständig, wenn 8 Damen insgesamt platziert sind. Für jede Reihe/Spalte kann eine Dame an 8 unterschiedlichen Stellen platziert werden, deshalb wird die Platzierung in einer Schleife durchgeführt. Zu jedem Feld der ersten Reihe/Spalte können die verliebenden 7 Damen beliebig platziert werden, zu jedem Feld der zweiten Reihe/Spalte die verbleibenden 6 Damen usw. usf. Methoden, die Damen in der ersten zweiten, dritten usw. Reihe/Spalte platzieren, müssen dann also einmal, 8-mal, 64-mal usw. aufgerufen werden - das geht, wenn man den rekursiven Aufruf innerhalb der Methode innerhalb der Schleife, die die Damen einfügt, schreibt. Nach dem Platzieren wird geprüft, ob dieser neue Teillösungsschritt gültig ist. Wenn nicht, dann wird er rückgängig gemacht. Sind weitere Teillösungsschritte nicht mehr vorhanden, wird wieder ein Schritt rückgängig gemacht, indem in der Rekursionsebene "ein Schritt weiter zurück" gegangen wird, wo es evtl. noch weitere Teillösungsschritte gibt usw. Ungefähr verständlich?


----------



## Beginner94 (22. Mrz 2011)

Ja, danke.
Ich musste es mir 2-3 mal durchlesen um es besser zu verstehen. Alles ist noch nicht ganz klar, aber ich taste mich ran. 
Man kann ja so ein Programm auch nicht an einem Tag als Anfänger schreiben.


----------



## Beginner? (22. Mrz 2011)

OK, hab auch den roten Faden verloren oder besser gesagt, gar nicht gehabt. Ich will auch nicht Rekursion erklären und schon gar nicht Backtracking. Dafür gibt es wirklich bereits präsente.

Um dich an das Thema ranzutasten, könntest du eine Methode schreiben, die alle zweistelligen Kombinationen der Buchstaben A und B ausgibt. Das könnte mit zwei geschachtelten Schleifen passieren, wobei jede Hilfs-/Zählvariable der Schleifen immer die erste oder zweite Stelle verändert, oder eben mit einer rekursiven Methode, der ein Parameter angehört, der die Stelle angibt, die verändert werden soll.

Aufjedenfall erst mal -> imperative Methoden -> rekursive Methoden -> Backtracking


----------



## Andi_CH (23. Mrz 2011)

kirax hat gesagt.:


> Du musst beim korrigierten Setzen einer Dame die dadurch nicht mehr bedrohten Felder wieder auf 0 setzen. Das wird schön komplex.
> Alternativ kannst du dir verschiedene Bretter "zwischenspeichern", auf die du zurückgreifen kannst, falls was schief ging. BÄM wären wir bei Rekursion



Ich nehme es vorweg - die Diskussion ist etwas zu wirr um nach einigen Tagen Absenz alles nachzulesen.

Bedrohung auf 0 setzen ist kaum richtig, denn es könnte sein, dass ein Feld von mehr als einer Dame bedroht wird. Vielleicht funktioniert das mit einem Zähler, inkerement und dekrement?

Aber warum denn die Bedrohung speichern?

Mein Ansatz (fertig implementiert und getestet) ist der, dass ich mir nur die Position der schon gesetzten Damen merke.
Wenn ich eine weitere Dame auf ein freies Feld setzen will, überprüfe ich ob die zu setzende Dame irgend eine andere Dame bedrohen würde. Wenn ja, würde auch sie bedroht, also versuche ich es auf dem nächsten Feld.

Rekursion ist eben schon das Einfachste um dann die Damen auch wieder abzuräumen und auf das nächste freie Feld (wenn es dann noch eines hat) zu setzen.
Eine Iterative Lösung schreibe ich erst auf ausdrücklichen Wunsch - das ist mir zu kompliziert


----------



## kirax (23. Mrz 2011)

Eben nur da auf 0 setzen, wo ein Feld von keiner Dame mehr bedroht wird.
Aber das wird eben *schön komplex*, wenn ich nur eine 1 schreibe für ein Feld, das generell bedroht wird.
Das wollte ich mit meinem Statement aussagen  Klar - ein Feld kann von mehreren Damen bedroht sein. Ein extra Zustand für "Feld bedroht" bringt nichts. Es sei denn, naja dazu s.u. 

Eine sehr schöne Möglichkeit ist glaub ich ein int-Array mit 8 (bzw. n) Feldern zu nehmen - für jede Spalte eines und die Position der Dame in dieser Spalte zu speichern.
Damit ist es dann auch recht easy, die Bedrohungskontrolle zu implementieren.

Setze Dame auf erstes freies Feld in der Spalte
Prüfe, ob diese Dame eine schon bestehende bedroht
wenn ja, springe eine Spalte weiter und beginne von vorne
wenn nein, lösche die Dame und setze sie auf das nächste freie Feld in der Spalte und prüfe
solange, bis entweder n Damen gesetzt sind, oder keine Dame in der Spalte gesetzt werden kann, dann gehe eine Spalte zurück und lösche dort die Dame und setze sie ein Feld weiter

Außerdem kannst du dich zur Vereinfachung auf ein paar Dinge verlassen:
- wenn du die (m+1)te Dame setzt, bedroht sich auf dem Feld m x n keine Dame (deshalb musst du immer nur die neu gesetzte Dame prüfen)
- in einer Spalte und einer Zeile darf immer nur eine Dame stehen (deshalb geht die Repräsentation mit einem eindim. int-Array der Länge n), also musst du auch gar nicht die Spalten durchchecken.

Natürlich könntest du jetzt zu jedem gültigen m x n Brett speichern, welche Felder in der jeweils nächsten Spalte davon bedroht würden, dann musst du nicht erst dort eine Dame hinsetzen, um das auszuprobieren. Das bringt aber erst einen spürbaren Vorteil, wenn du das für mehrere Spalten im Voraus machst, was aber sehr(!!!) aufwändig wird und sich die Frage nach der Speicherplatzkomplexität stellt


----------



## Beginner? (23. Mrz 2011)

Andi_CH hat gesagt.:


> Mein Ansatz (fertig implementiert und getestet) ist der, dass ich mir nur die Position der schon gesetzten Damen merke.
> Wenn ich eine weitere Dame auf ein freies Feld setzen will, überprüfe ich ob die zu setzende Dame irgend eine andere Dame bedrohen würde. Wenn ja, würde auch sie bedroht, also versuche ich es auf dem nächsten Feld.



Meine Lösung oben wird anscheinend nicht beachtet oder aber ich habe jemanden die Lorbeeren genommen, weshalb er jetzt sauer ist:


```
public static boolean solveViaBT(boolean[][] game, int row) {
        if (row == 8) { // Abbr.
            return true;
        }
 
        for (int col = 0; col < 8; col++) { // Kand.
            game[row][col] = true; // Kand. einf.
            if (valid(game, row, col)) { // Kand. richtig
                printGame(game);
                if (solveViaBT(game, row + 1)) { // andere Kand. richtig
                    return true; // Loes.
                }
            }
            game[row][col] = false; // Kand. rueckgaeng.
        }
 
        return false; // Keine Loes.
    }
```

game ist die Lösung (das Feld), in die Damen platziert werden. Es ist ein 2d boolean array. Damit ist die Ausgabe recht einfach zu schreiben und ich glaube, es macht kaum einen Unterschied, ob 64 boolean oder 8 int Speicher verwendet werden...

Die Methode fügt immer in die durch den Parameter row angegebene Reihe eine Dame ein. Es gibt dafür 8 Möglichkeiten 
	
	
	
	





```
for (int col = 0; col < 8; col++)
```
. Nur wenn die Teillösung nach der neu eingefügten Damen noch gültig ist 
	
	
	
	





```
if (valid(game, row, col))
```
, wird versucht, weitere Damen in den nächsten Reihen einzufügen 
	
	
	
	





```
solveViaBT(game, row + 1)
```
. Ist das möglich, wird die Methode mit true verlassen. Ist das nicht möglich oder war die in der aktuellen Reihe eingefügte Dame ungültig, wird die Einfügung rückgängig gemacht.

valid(game, row, col) prüft, ob eine Teillösung (game), in die bei (row, col) eine Dame einfügt wurde, noch gültig ist oder jetzt ungültig geworden ist.

@kirax
Weil wir davon ausgehen können, dass zuerst keine Damen sich in game befindet und stets nach jeder neu einfügten Dame geprüft wird, ob game noch gültig ist, muss nur geprüft werden, ob die zuletzt/neu eingefügte Damen nicht dort platziert wurde, wo sie andere schlagen könnte.

@Beginner94
leer/bedroht/besetzt zu speichern und stets aktuell zu halten, ist deshalb unnötig aufwändig, weil nach dem Entfernen einer oder mehrerer Damen alle Bedrohungen zurückgesetzt und wieder neu gesetzt werden müssten.

Jetzt ist das Geheimnis mit der Damenwelt ja schon fast gelüftet^^


----------



## Beginner94 (23. Mrz 2011)

Mir gefällt die Variante von Andi_CH der gut 
Das Problem, auf das ich jetzt stoße ist, dass wenn ich z.b auf feld[0][0]=true, also eine dame setze, und dann feld[1][0], also eine reihe tiefer, die nächste, wie ich dann überprüfen kann, ob sie sich schlagen. Denn die Variablen der Koordinaten des feldes sind ja für beide damenbesetzte Felder gleich, so kann ich sie schlecht verändern um etwas zu vergleichen.


----------



## Beginner94 (23. Mrz 2011)

Ich sollte mal mehr nachdenken, bevor ich hier immer etwas poste, sry.
Ich bin jetzt soweit, dass ich in jeder Reihe eine Dame setzen kann, ohne dass sie von der vorherigen Dame bedroht ist.
Jetzt fehlt nur noch, dass das Programm eine Reihe zurückgeht, wenn es keine Möglichkeit mehr gibt, etc.
Ich wollte nur mal wissen, ob bisher alles richtig ist, bevor am Ende wieder alles nicht geht, wegen dem Anfang.


```
public class xxx
{
    int n=4;
    int reihe=0;
    int reihez=0; //zwischenspeicher
    int spalte=0;
    int spaltez=0; //zwischenspeicher
    
    boolean[][] feld;
    
    public xxx()
    {
        feld = new boolean[n][n];
    }
    
    public void berechnung()
    {
        for( int i=0; i<n; i++ )
        {
            feld[reihe][spalte] = true;
            if( feld[reihe][spalte] == true )
            {
                reihez = reihe;
                spaltez = spalte;
            }
            reihe++;
            bedrohung();
            feld[reihe][spalte] = true;
        }
    }
    
    public void bedrohung()
    {
        for( int j=0; j<n; j++ )
        {
              if( spalte == spaltez || spalte-1 == spaltez )
              {
                  spalte++;
              }
        }
    }
    
}
```


----------



## kirax (23. Mrz 2011)

Beginner? hat gesagt.:
			
		

> game ist die Lösung (das Feld), in die Damen platziert werden. Es ist ein 2d boolean array. Damit ist die Ausgabe recht einfach zu schreiben und ich glaube, es macht kaum einen Unterschied, ob 64 boolean oder 8 int Speicher verwendet werden...


Ja im Prinzip machst du ja in deinem Code genau das was ich meinte. Beim eindimensionalen Array wird halt schon technisch ausgeschlossen, dass in jeder Zeile respektive Spalte nur eine Dame sein kann.

@Beginner94
Sieht nicht soo verkehrt aus, aber es wird schwierig auf diese Weise einen Schritt zurückzugehen. Du kriegst mit deiner Methode nämlich nie und nimmer ein rekursives BT hin.


----------



## Beginner? (23. Mrz 2011)

@Beginner94:
Die Methoden verändern viele Instanzvariablen, das ist nicht gut  Klassennamen: groß und aussagekräftig.

Schreib erst mal ein Programm, dass
AA
AB
BA
BB

zur Übung ausgibt. Man kann es mit drei sich wesentlich voneinander unterscheidenden Methoden umsetzen. Zeig her


----------



## Beginner94 (24. Mrz 2011)

Kann ich zum Lernen des BT auch die Türme von Hanoi programmieren?


----------



## kirax (24. Mrz 2011)

Beginner94 hat gesagt.:


> Kann ich zum Lernen des BT auch die Türme von Hanoi programmieren?


BT muss man da nicht machen, da es einen geschlossenen Algorithmus gibt, mit dem man es in wenigen Zeilen in einer Rekursion lösen kann.


----------



## Beginner? (24. Mrz 2011)

Kann man (dann käme man auch mal weg von diesem dubiosen "Damenproblem"), würde aber in einem stack overflow error enden, weil das Abbruchkriterium nach beliebig vielen Schritten nicht erreicht wird^^

Kleinere Programme schreiben, die dem eigenen Lernfortschritt angemessen sind. Und hier hat keiner Lust, BT zu erklären, wenn es das bereits A woanders erklärt gibt und B nichts davon "hängen" bleibt^^


----------



## icarus2 (24. Mrz 2011)

Ich habe jetzt nicht die Zeit gehabt alles zu lesen ausser der Frage, ob sich die Türme von Hanoi zum erlernen von Backtracking eignen.

Eine gute Möglichkeit mit Backtracking etwas zu experimentieren ist die Wegsuche aus einem Labirinth heraus. Da ist das Prinzip der Tiefensuche sehr anschaulich, da die Tiefe dann einfach einer möglichen Weglänge entspricht. Man kann das dann auch rekursiv implementieren (jedoch nicht für grosse Labirinthe geeignet). Wenn du nach "Java Maze" oder so etwas in der Art googelst solltest du bestimmt etwas darüber finden.


----------



## Beginner? (24. Mrz 2011)

Es kann zyklische Wege geben und dann, bäääääm, stack overflow error


----------



## Andi_CH (24. Mrz 2011)

Die Türme von Hanoi sind etwas einfacher zu implementieren, weil es da ohne Bedrohungsszenario geht und auch dafür findest du sicher diverse fertige Lösungen 

Das sucht alle möglichen Lösungen:


```
package com.javaforum.rekursionen;

import java.util.*;

public class Damenproblem implements Comparable<Damenproblem> {

	private static final String nl = System.getProperty("line.separator");

	private static class Position implements Comparable<Position> {
		final private int mX, mY, mMax;
		public Position(int x, int y, int max) {mX = x; mY = y; mMax = max;}
		public Position(Position pos) {mX = pos.x(); mY = pos.y(); mMax = pos.mMax;}
		public int x(){return mX;}
		public int y(){return mY;}
		@Override
		public String toString(){return ("X : " + mX + ", Y : " + mY);}
		@Override
		public int compareTo(Position o) {
			Integer value = mY*mMax+mX;
			Integer oValue = o.mY*o.mMax+o.mX;
			return value.compareTo(oValue);
		}
	}

	final private int size;
	private boolean[][] schachbrett;
	private int anzahlGesetzt = 0;
	static private TreeSet<Damenproblem> loesungen;
	
	private boolean[][] clone (boolean[][] arr) {
		boolean[][] res = new boolean[arr.length][];
		for(int y=0; y<arr.length; y++) {
			res[y] = new boolean[arr[y].length];
			for (int x=0; x<arr[y].length; x++)
				res[y][x] = arr[y][x];
		}
		return res;
	}

	public Damenproblem(int pSize) {
		size = pSize;
		schachbrett = new boolean[size][size];
		if (loesungen==null)
			loesungen = new TreeSet<Damenproblem>();
		init();
	}
	
	public Damenproblem(Damenproblem dp) {
		size = dp.size;
		schachbrett = clone(dp.schachbrett);
		anzahlGesetzt = dp.anzahlGesetzt;
	}


	private Position ersteBesetzte() {
		for (int y=0; y<size; y++)
			for (int x=0; x<size; x++)
				if (schachbrett[y][x])
					return new Position(x, y, size);
		return null;
	}

	private Position naechstePosition(Position pos) {
		if (pos==null)
			return null;
		// Spielfeldgrenzen
		if ((pos.x()>=size) || (pos.y()>=size) ||	// Grenzen überschritten
				(pos.x()<0) || (pos.y()<0) ||			// Grenzen unterschritten
				(pos.x()>=(size-1) && (pos.y()>=(size-1)))) // letztes Feld
			return null;
		// Übertrag
		if ((pos.x()==size-1)) {
			return new Position(0, pos.y()+1, size);
		}
		return new Position(pos.x()+1, pos.y(), size);
	}

	private Position naechsteFreie(Position pos) {
		if (pos==null)
			return null;
		Position result = naechstePosition(pos);
		while (result != null && !feldOk(result)) {
			result = naechstePosition(result);
		}
		return result;
	}

	private void init() {
		for (int y=0; y<size; y++)
			for (int x=0; x<size; x++)
				schachbrett[y][x] = false;
	}

	private boolean feldOk(Position pos) {return feldOk(pos.x(), pos.y());}
	private boolean feldOk(int x, int y) {
		if (!spalteOk(x))
			return false;
		if (!zeileOk(y))
			return false;
		return diagonalenOk(x, y);
	}

	private boolean diagonalenOk(int x, int y) {
		if ((x>=size) || (y>=size))
			return true;
		int tmpX, tmpY;
		for (int i=0; i<size; i++) {
			// right up
			tmpX = x+i;
			tmpY = y+i;
			if ((tmpX<size) && (tmpY<size) && schachbrett[tmpY][tmpX])
				return false;
			// right down
			tmpX = x+i;
			tmpY = y-i;
			if ((tmpX<size) && (tmpY>=0) && schachbrett[tmpY][tmpX])
				return false;
			// left up
			tmpX = x-i;
			tmpY = y+i;
			if ((tmpX>=0) && (tmpY<size) && schachbrett[tmpY][tmpX])
				return false;
			// left down
			tmpX = x-i;
			tmpY = y-i;
			if ((tmpX>=0) && (tmpY>=0) && schachbrett[tmpY][tmpX])
				return false;
		}
		return true;
	}

	private boolean zeileOk(int y) {
		if ((y>=0) && (y<size)) {
			for(int x=0; x<size; x++) {
				if (schachbrett[y][x])
					return false;
			}
		}
		return true;
	}

	private boolean spalteOk(int x) {
		if ((x>=0) && (x<size)) {
			for(int y=0; y<size; y++) {
				if (schachbrett[y][x])
					return false;
			}
		}
		return true;
	}

	private void set(Position pos){set(pos.x(), pos.y());}
	private void set(int x, int y) {
		anzahlGesetzt++;
		schachbrett[y][x] = true;
	}
	private void reset(Position pos){reset(pos.x(),pos.y());}
	private void reset(int x, int y) {
		anzahlGesetzt--;
		schachbrett[y][x] = false;
	}

	private boolean feldVoll(){return anzahlGesetzt==size;}

	private String sep(){
		String ret = "+";
		for(int x=0; x<size; x++) {
			ret += "-+";
		}
		return ret + nl;
	}
	private String zeile(int y) {
		String ret = "|";
		for(int x=0; x<size; x++) {
			if(schachbrett[y][x])
				ret += "x|";
			else
				ret += " |";
		}
		return ret + nl;
	}

	@Override
	public String toString() {
		String ret = sep();
		for(int y=0; y<size; y++) {
			ret += zeile(y);
			ret += sep();
		}
		return ret;
	}

	public void loese(Position anfang) {
		if (anfang==null) {
			return;
		}
		Position pos = new Position(anfang);
		while (!feldVoll() && pos!=null) {
			if(feldOk(pos)) {
				set(pos); // platziere Dame
				loese(naechsteFreie(pos));
				if (feldVoll())
					loesungen.add(new Damenproblem(this)); // alle Damen gesetzt
				reset(pos); // enferne zuletzt gesetzte Dame
				pos = naechsteFreie(pos);
			} else {
				pos = naechsteFreie(pos);
			}
		}
	}

	public boolean equals(Object anObject) {
		if (this == anObject)
			return true;
		if (anObject instanceof Damenproblem) {
			Damenproblem otherDp = (Damenproblem)anObject;
			if (size == otherDp.size) {
				for (int y=0; y<size; y++) {
					for (int x=0; x<size; x++) {
						if (this.schachbrett[y][x]!= otherDp.schachbrett[y][x])
							return false;
					}
				}
				return true;
			}
		}
		return false;
	}

	@Override
	public int compareTo(Damenproblem o) {
		if (o==null)
			System.out.println("o = null");
		if (this.equals(o))
			return 0;
		Position tep = ersteBesetzte();
		Position oep = o.ersteBesetzte();
		if (oep==null)
			System.out.println("oep = null");
		return tep.compareTo(oep);
	}

	public static void main(String[] args) {
		int groesse = 8;
		Damenproblem dp = null;
		Position pos = new Position(0,0, groesse);
		while (pos != null) {
			dp = new Damenproblem(groesse);
			dp.loese(pos);
			pos = dp.naechstePosition(pos);
		}
		final int s = loesungen.size();
		if (s==1) {
			System.out.println("Für die Grösse " + groesse + " wurde 1 Lösung gefunden");
		} else {
			System.out.println("Für die Grösse " + groesse + " wurden " + s + " Lösungen gefunden");
		}
		int c = 1;
		for(Damenproblem d : loesungen) {
			System.out.println("Lösung " + c++);
			System.out.println(d);
		}
	}
}
```


----------



## Beginner? (24. Mrz 2011)

```
public static void solveViaBT(boolean[][] game, int row) {
        if (row == 8) { // Abbr.
            printGame(game);
            return;
        }
 
        for (int col = 0; col < 8; col++) { // Kand.
            game[row][col] = true; // Kand. einf.
            if (valid(game, row, col)) { // Kand. richtig
                solveViaBT(game, row + 1)
            }
            game[row][col] = false; // Kand. rueckgaeng.
        }
    }
```

DAS findet auch alle Lösungen und ist ein bisschen übersichtlicher^^


----------



## Andi_CH (24. Mrz 2011)

Da bin ich anderer Meinung - dein Routine findet genau eine Lösung und nicht mehr.

Bei mir sind Speicherung der gefunden Lösungen, eliminieren von doppelt gefunden Lösungen (ja, das gibt es), die Speicherung der gefunden Lösungen und das Hauptprogramm mit dabei - dass es bsonders schön implementiert ist, habe ich nie behauptet.


----------



## icarus2 (24. Mrz 2011)

Beginner? hat gesagt.:


> Es kann zyklische Wege geben und dann, bäääääm, stack overflow error



Jo, ich meinte ein perfektes Maze. Da passiert sowas nicht.


Für das N-Damen-Problem würde ich folgende Implementierung vorschlagen: Es berechnet alle Lösungen und gibt diese sogleich aus. Sie werden nur nicht gespeichert aber das kann man sehr leicht abändern. Ich habe den Code vor zwei bis drei Jahren geschrieben als ich gerade mal knapp ein halbes Jahr programmiert hatte. Ein par kleine Dinge könnte man vielleicht noch abändern:
[Java]
public class NQueenProblem {
	static int queens;
	static int amountOfConfigurations = 0;
	static int[] config;

	/**
	 * Calculates all configurations and counts the amount of solutions for n queens
	 * on a n x n chess board. The configurations are calculated by a recursive
	 * backtracking algorithm.
	 * 
	 * @param k - the column where the program must try to set the next queen to get
	 * 				   a new position. (Must start with 0).
	 */
	public static void calculateConfigurations(int k){

		//for loop goes through every row in a certain column. It starts at the top
		//and it goes down all rows. There are as many rows as queens.
		for(int row = 0; row < queens; row++){

			config[k] = row; //The current row is stored in the array f at
						//the position of the current column.

			//The current position is checked.
			if(positionFree(config, k)){
				//If the last column is reached a new solution is known.
				if(k == queens - 1){
					amountOfConfigurations++;
					printConfiguration();
				}
				//If the last column is not reached yet the program goes to
				//the next column to set a queen.
				else {
					calculateConfigurations(k + 1); //recursive call
				}
			}	
		}
	}

	/**
	 * Checks if the position of the last set queen is threatened or not.
	 * 
	 * @param f - int array where the positions of the queens are stored
	 * @param k - current column of the queen
	 * @return true if the position is not threatened, else false
	 */
	public static boolean positionFree(int[] f, int k){
		//Checks for all queens further left than the queen at k
		for(int i = 0; i < k; i++){
			if(Math.abs( f_-f[k] ) == k - i | f == f[k]){
				return false; //If the position at k is threatened once the method
							  //returns false
			}
		}

		return true; //If the position at k is never threatened it returns true
	}

	public static void printConfiguration(){
		String print = "";

		for(int i = 0; i < config.length; i++){
			print += (" " + ( config + 1 ) );
		}

		System.out.println(print);
	}


	public static void main(String[] args){

	    System.out.print("Enter the amount of Queens: ");
	    queens = InOut.getInt();;	//The amount of queens is read
	    config = new int[queens];		//The array where the positions are stored is initialized

	    System.out.println();
	    calculateConfigurations(0); //parameter must be 0 to start in the first column
	    System.out.println();
	    System.out.println("Number of solutions: "+nqp.amountOfConfigurations);		
	}	
}
[/Java]

PS:
Das Beispiel wird nicht kompilieren weil die Klasse InOut fehlt zum einlesen. Habe die gerade nicht mehr gefunden. Wer den Code laufen lassen möchte kann sich ja selber kurz um den Input kümmern.

Die Abfrage in der Methode positionFree kann man leicht mit ein paar geometrischen Überlegungen anhand eines Schachbretts nachvollziehen._


----------



## Beginner? (25. Mrz 2011)

Andi_CH hat gesagt.:


> Da bin ich anderer Meinung - dein Routine findet genau eine Lösung und nicht mehr.
> 
> Bei mir sind Speicherung der gefunden Lösungen, eliminieren von doppelt gefunden Lösungen (ja, das gibt es), die Speicherung der gefunden Lösungen und das Hauptprogramm mit dabei - dass es bsonders schön implementiert ist, habe ich nie behauptet.



Probiere sie doch erst mal aus, die Routine, bevor du so was verzapfst.


```
public class BTSpas {

    public static void solveAndPrint(boolean[][] game, int row) {
        if (row >= game.length) { // Abbr.
            print(game);
            return;
        }

        for (int col = 0; col < game[row].length; col++) { // Kand.
            game[row][col] = true; // Kand. einf.
            if (valid(game, row, col)) { // Kand. richtig
                solveAndPrint(game, row + 1);
            }
            game[row][col] = false; // Kand. rueckgaeng.
        }
    }

    private static void print(boolean[][] game) {
        for (boolean[] ba : game) {
            for (boolean b : ba) {
                System.out.print(b ? "X " : "O ");
            }
            System.out.println();
        }
        System.out.println();
    }

    private static boolean valid(boolean[][] game, int row, int col) {
        // up -> down
        for (int rowNew = 0; rowNew < game[row].length; rowNew++) {
            if (game[rowNew][col] && rowNew != row) {
                return false;
            }
        }

        // middle -> upper left
        for (int rowNew = row - 1, colNew = col - 1; rowNew >= 0 && colNew >= 0; rowNew--, colNew--) {
            if (game[rowNew][colNew]) {
                return false;
            }
        }

        // middle -> lower right
        for (int rowNew = row + 1, colNew = col + 1; rowNew < game.length && colNew < game[rowNew].length; rowNew++, colNew++) {
            if (game[rowNew][colNew]) {
                return false;
            }
        }

        // middle -> upper right
        for (int rowNew = row - 1, colNew = col + 1; rowNew >= 0 && colNew < game[rowNew].length; rowNew--, colNew++) {
            if (game[rowNew][colNew]) {
                return false;
            }
        }

        // middle -> lower left
        for (int rowNew = row + 1, colNew = col - 1; rowNew < game.length && colNew >= 0; rowNew++, colNew--) {
            if (game[rowNew][colNew]) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        solveAndPrint(new boolean[8][8], 0);
    }
}
```

Eine komplette Klasse zum Ausprobieren. Die valid()-Methode, die Prüft, ob der zuletzt gemachte Zug gültig ist, sprich, die zuletzt eingefügte Dame keine andere schlagen kann, ist etwas lang geworden. da müsste ein Mathematiker mal eine kürzere schreiben ^^

Es gibt ganz schön viele Lösungen..


----------



## kirax (25. Mrz 2011)

Soll hier jetzt jeder seine Lösung fürs N-Damen Problem posten?! :smoke: :noe:

Das Prüfen auf Gültigkeit geht in der Tat einfacher 
Ob du mich deswegen jetzt als Mathematiker bezeichnen willst, sei dir überlassen... 1 Semester Info-Studium reichen dafür aus:


```
/**
* Returns <code>true</code> if one queen menaces another queen on the
* board.
* 
* Checks for every queen its row and its diagonals if there is another
* queen.
* 
* @return <code>true</code> if one queen menaces another queen on the
*         board, <code>false</code> otherwise.
*/
public boolean hasConflict() {
  boolean conflict = false;
  // check that every row has only one queen
  int i = 0;
  while (i < board.length && !conflict) {
    // because we must only test queens right of the actual queen
    int j = i + 1;
    // holds the distance from the actual queen to a new possible queen,
    // increases with every column we go away from our queen testing
    int distanceToCheck = 1;
    while (j < board.length && !conflict) {
      // 1st test: if queens are in the same row, 2nd test: if queens
      // are in the 1st diagonal, 3rd test: if queens are in the 2nd
      // diagonal
      conflict = board[i] == board[j]
        || board[i] + distanceToCheck == board[j]
        || board[i] - distanceToCheck == board[j];
      j++;
      distanceToCheck++;
      }
    i++;
    }
    return conflict;
}
```

Die Lösung beruht darauf, dass ich ein eindimensionales int-Array verwende für die Darstellung des Feldes.


----------



## Beginner? (25. Mrz 2011)

kirax hat gesagt.:


> Die Lösung beruht darauf, dass ich ein eindimensionales int-Array verwende für die Darstellung des Feldes.



*gähn* diese Inkrementierungen irgendwo in den Schleifen würde ich so nicht schreiben, und bei dir ist die von BT auszubauende Lösung ganz anders strukturiert, deshalb lässt sich es sich nicht übertragen.

Hatte das nicht im Studium, aber in der Schulzeit irgendwann und es ging nur darum, zu zeigen, dass die Methode eben doch funktioniert, deshalb der post. Von mir aus ist es das N-Damenproblem. Gibt man aber ein null-Array oder ein Array, dessen UnterArrays nicht gleichlang sind, der Methode, gibt es array index out of bounds exception

Was aber eigentlich möglich wäre, das ist das Übertragen auf andere Probleme, wenn man nur eine Methode, die vlaid()-Methode, ändert


----------



## kirax (26. Mrz 2011)

He es hat niemand davon gesprochen, dass die Lösung so übertragen werden kann. Ich wollte damit nur zeigen, dass es mit weniger Zeilen geht


----------



## icarus2 (26. Mrz 2011)

kirax hat gesagt.:


> He es hat niemand davon gesprochen, dass die Lösung so übertragen werden kann. Ich wollte damit nur zeigen, dass es mit weniger Zeilen geht



Schau dir doch mal in meinem Code die Methode positionFree an, die macht das selbe wie deine hasConflict, nur ist sie noch viek kürzer.

Ich habe das Gefühl, dass die meisten hier die Überprüfung auf Bedrohung viel zu kompliziert machen. Hat mein Prof letztes mal in der Vorlesung sogar gemacht ^^


----------



## Beginner? (26. Mrz 2011)

icarus2 hat gesagt.:


> Schau dir doch mal in meinem Code die Methode positionFree an, die macht das selbe wie deine hasConflict, nur ist sie noch viek kürzer.



Dann erkläre mal Zeile 49: 
	
	
	
	





```
if(Math.abs( f[i]-f[k] ) == k - i | f[i] == f[k]){
```

Da du alle anderen Zeilen außer diese kommentiert hast und 
	
	
	
	





```
return true;
```
 zu kommentieren relativ sinnlos ist, denke ich, dass sie nicht mal von dir stammt ^^


----------



## kirax (26. Mrz 2011)

Gut - ich könnte auch [c]Math.abs[/c] verwenden... spart eine Zeile.
Meine ist aber deswegen noch länger, weil sie gleich das ganze Board überprüft. Das war damals Vorgabe (richtig, wenn ich das ändere, kommt genau deine positionFree raus).

@Beginner?:
Vor dem OR wird die diagonale Bedrohung geprüft. Wenn man das [c]Math.abs[/c] rauszieht, kommt genau das gleiche raus, wie in meiner hasConflict. Hinter dem OR die Bedrohung in jeder Reihe/Spalte (nur eins von beiden wegen der Realisierung).

Übrigens: [c]||[/c] statt [c]|[/c] machts noch nen Ticken schneller.


----------



## Beginner94 (26. Mrz 2011)

Euer battle ist noch etwas zu hoch für mich^^
mein kompliment an beide lösungen ist, dass ich sie nicht verstehe 
ich hab mich nochmal lange mit rekursion etc beschäftigt und das programm neu angefangen.
Mein problem ist jetzt bei der bedrohung.
Wie kann ich die koordinaten von den bisher gesetzten Damen speichern, um zu überprüfen, ob die neu zu setzende Dame bedroht ist?


----------



## icarus2 (27. Mrz 2011)

Beginner? hat gesagt.:


> Dann erkläre mal Zeile 49:
> 
> 
> 
> ...



Teil links vom |:
Das Steigungsdreieck zwischen zwei Damen darf nicht gleichschenklig sein.

Teil rechts vom |:
Die Damen dürfen natürlich nicht in der selben Zeile stehen.

.. glaubst du noch immer, dass ich es nicht selber geschrieben habe?


----------



## Beginner94 (27. Mrz 2011)

Ich habe das Programm jetzt neu geschrieben, aber bisher ohne das Backtracking.
Ich habe versucht jetzt mal Rekursion zu verwenden.
Doch beim Ausführen von main() kommt eine Fehlermeldung und ich finde den Fehler nicht...


```
public class QUEENPROBLEM
{
    int n = 4;
    int[] feld;
    int zeile = 0;
    int spalte = 0;
    int bedrohung = 2; //0=true, 1=false
    
    
    public QUEENPROBLEM()
    {
        feld = new int[n];
    }

    public void main()
    {
        gibWert();
        setzeDame(0, 0);
        
        for( int i=0; i<n; i++)
        {
            System.out.println("feld["+i+"]= "+feld[i]);
        }
        
        

    }
    
    
    public void setzeDame(int zeile, int spalte)
    {
        if( zeile < n )
        {
            feld[zeile] = spalte;
        }
        istBedroht();
        if( istBedroht() == true )
        {
            setzeDame(zeile, spalte+1);
        }
        else if( istBedroht() == false )
        {
            setzeDame(zeile+1, spalte=0 );
        }
    }
    
    public boolean istBedroht()
    {
        for( int i=0; i<zeile; i++ )
        {
            if( feld[i]==spalte  ||  feld[i]-spalte==i-zeile  ||  feld[i]-spalte==i+zeile ) 
            //   senkrecht              schräg links oben           schräg rechts oben
            {
                bedrohung = 0;
            }
            else
            {
                bedrohung = 1;
            }
            
        }
        
        if( bedrohung == 0 )
        {
            return true;
        }
        else 
        {
            return false;
        }
    }
    
    public void gibWert()
    {
        for( int i=0; i<n; i++ )
        {
             feld[i] = n+1;
        }
    }
    
}
```


----------



## kirax (27. Mrz 2011)

"Fehlermeldung" kann viel bedeuten. Hier hat leider niemand eine Kristallkugel, also musst du uns schon auf herkömmlichem Wege an deiner Weisheit teilhaben lassen  (wie lautet die genaue Fehlermeldung mit StackTrace?)
Wobei ich mal vermute, dass du einen StackOverflowError oder einen OutOfMemoryError bekommst. Irgendwo in deiner setzeDame(). Das liegt daran, dass du keine Abbruchbedingung hast und das Programm in einer Endlosrekursion hängt.

Ich geh das mal einzeln nacheinander durch 

```
public void setzeDame(int zeile, int spalte)
    {
        ///////////
        // hier muss noch eine Abbruchbedingung rein. zeile == n vielleicht? :)
        ///////////
        if( zeile < n )
        {
            feld[zeile] = spalte;
        }
        istBedroht();  // kannst du dir sparen, da du das Ergebnis nicht speicherst und in der nächsten
                       // Zeile eh nochmal aufrufst
        if( istBedroht() == true )
        {
            setzeDame(zeile, spalte+1);
        }
        else if( istBedroht() == false )  // hier reicht auch ein einfaches else, denn entweder ist das
                                          // Ergebnis von istBedroht() im ersten Fall true oder false
        {
            setzeDame(zeile+1, spalte=0 );
        }
    }
```


----------



## Beginner94 (27. Mrz 2011)

Danke 
Ich habe noch ein paar andere Kleinigkeiten geändert und jetzt kommt als Ergebnis raus
feld[0]=0
feld[1]=2
feld[2]=0
feld[3]=2

Das ist natürlich falsch, aber jetzt fehlt nur noch das BT


----------



## Beginner94 (28. Mrz 2011)

Nochmal danke an alle!
Mein Programm funktioniert jetzt 
Aber bis jetzt sagt es mir nur eine Lösung, deswegen muss ich jetzt noch was ändern, damit ich die Anzahl aller Lösungen bekomm.


----------



## Beginner94 (28. Mrz 2011)

Ok, ein problem habe ich doch noch..
Bei einem 4*4 Schachfeld funzt alles, doch bei 8*8 gibt es einen StackoverflowError. Er findet 9 Lösungen aber dann kommt der Fehler in der Zeile

```
if( istBedroht(zeile, spalte) == true )
```

Hier ist der vollständige Code


```
public class QUEENPROBLEM
{
    int n = 8;
    int[] feld;
    int zeile = 0;
    int spalte = 0;
    int lösungsanz;
    
    
    public QUEENPROBLEM()
    {
        feld = new int[n];
    }

    public void main()
    {
        gibWert();
        setzeDame(0, 0);
        System.out.println("Lösungen für "+n+"*"+n+" Schachfeld: "+lösungsanz);
    }
    
    
    public void setzeDame(int zeile, int spalte)
    {
        if( zeile == n )
        {
            lösungsanz++;
            System.out.println("Anzahl: "+lösungsanz);
            System.out.println();
            for( int i=0; i<n; i++)
            {
                System.out.println("feld["+i+"]= "+feld[i]);
            }
            int i=1;
            if( zeile>0 )
            {
                while( feld[zeile-i]==n-i && (zeile-i)>0 )
                {
                    i++;
                }
                setzeDame( zeile-i, feld[zeile-1]+1 );
            }
        }
        else
        {
            if( zeile < n )
            {
                feld[zeile] = spalte;
            }
            if( istBedroht(zeile, spalte) == true )
            {
                if( spalte < n-1 )
                {
                    setzeDame(zeile, spalte+1);
                }
                if( spalte == (n-1) )
                {
                    if( feld[zeile-1]==n-1 )
                    {
                        if( zeile >= 2 )
                        {
                            int i=2;
                            while( feld[zeile-i]==n-i && (zeile-i)>0 )
                            {
                                i++;
                            }
                            setzeDame( zeile-i, feld[zeile-i]+1);
                        }
                    }
                    else
                    {
                        setzeDame( zeile-1, feld[zeile-1]+1 );
                    }
                }
            }
            else
            {
                setzeDame(zeile+1, 0 );
            }
        }
    }
    
    public boolean istBedroht(int zeile, int spalte)
    {
        boolean bedroht = false;
        for( int i=0; i<zeile; i++ )
        {
            if( feld[i]==spalte  ||  feld[i]-spalte==i-zeile  ||  feld[i]-spalte==zeile-i ) 
            //   senkrecht              schräg links oben           schräg rechts oben
            {
               bedroht = true;
            }
            
        }
        
       return bedroht;
    }
    
    public void gibWert()
    {
        for( int i=0; i<n; i++ )
        {
             feld[i] = n+1;
        }
    }
    
}
```


----------



## kirax (28. Mrz 2011)

Mit nem Debugger kannst du rausfinden, wo das Problem liegt. Ich vermute mal, dass er viel zu viele Instanzen von setzeDame() erzeugt.


----------



## Beginner94 (29. Mrz 2011)

Wenn ich Zele13-43 lösche, dann findet er nur eine Lösung.
Was müsste ich in das if( zeile==n ) reinschreiben, damit er nicht nur eine, sondern alle Lösungen findet?
Da schaffe ichs jetzt, dass das Programm ne Lösung findet und jetzt scheiterts an sowas...


----------



## Beginner94 (29. Mrz 2011)

Sry, ich meine zeile 35 und nicht 13


----------



## goto94 (29. Mrz 2011)

wie alt bist du - 16? dann ist es leider zu früh zum programmieren. lerne html.


----------



## kirax (29. Mrz 2011)

goto94 hat gesagt.:


> wie alt bist du - 16? dann ist es leider zu früh zum programmieren. lerne html.



Sorry - lange keinen so unqualifizierten Kommentar gelesen! *autsch*


----------



## Beginner94 (29. Mrz 2011)

goto94, mit den 16 Jahren liegst du richtig.
Nenne mir einen guten Grund, warum dieses Alter zu früh zum programmieren ist?!
Ich lerne es seit einem halben Jahr in der Schule und es interessiert mich sehr.
Wenn man keine Antwort auf eine gestellte Frage hat, dann (entschuldigung jetzt, liegt an meinen 16 Jahren ;-), aber sowas kotzt mich an) EINFACH MAL DIE FRESSE HALTEN!


----------



## goto94 (29. Mrz 2011)

Beginner94 hat gesagt.:


> goto94, mit den 16 Jahren liegst du richtig.
> Nenne mir einen guten Grund, warum dieses Alter zu früh zum programmieren ist?!
> Ich lerne es seit einem halben Jahr in der Schule und es interessiert mich sehr.
> Wenn man keine Antwort auf eine gestellte Frage hat, dann (entschuldigung jetzt, liegt an meinen 16 Jahren ;-), aber sowas kotzt mich an) EINFACH MAL DIE FRESSE HALTEN!



beleidigungen führen auch nicht dazu das der alle vorherigen post gelöscht werden - selbst ausprobiert  nimm den rat an und lerne html


----------



## kirax (29. Mrz 2011)

goto94 hat gesagt.:
			
		

> beleidigungen führen auch nicht dazu das der alle vorherigen post gelöscht werden - selbst ausprobiert  nimm den rat an und lerne html


Nimm meinen Rat an und lerne Deutsch


----------



## Beginner94 (29. Mrz 2011)

@goto94
Nimm meinen Rat und schreib keine Antwort mehr, außer du weißt die Lösung, ansonsten ist das für mich Spaming!


----------



## goto94 (29. Mrz 2011)

kirax hat gesagt.:


> Nimm meinen Rat an und lerne Deutsch



sagt wer oder was? auch 16, auch keine ahnung? tut euch doch zusammen


----------



## nrg (29. Mrz 2011)

goto94 hat gesagt.:


> sagt wer oder was?



einer spricht es aus und der Rest denkt sich seinen Teil... Werd' erwachsen. Du sitzt nicht dein ganzes Leben hinter einem Gateway.


----------



## goto94 (29. Mrz 2011)

nrg hat gesagt.:


> einer spricht es aus und der Rest denkt sich seinen Teil...



was denkt sich welcher teil?


----------



## Andi_CH (30. Mrz 2011)

Ich z.B. denk mir meinen Teil - die Lösung habe ich längst gepostet - was streitet ihr hier überhaupt noch, TO schliess doch den Thread und analysiere was du schon hast.

Und das mit html ist auf primitve Art das gesagt, was ich dir empfehle - befasse dich doch einmal damit wie man Probleme analysiert und dann Software designet und danach fällt dir das Programmieren viel einfacher.


----------



## nrg (30. Mrz 2011)

Andi_CH hat gesagt.:


> Und das mit html ist auf primitve Art das gesagt, was ich dir empfehle - befasse dich doch einmal damit wie man Probleme analysiert und dann Software designet und danach fällt dir das Programmieren viel einfacher.



das hast aber gerade du auch nicht von heute auf morgen getan...


----------



## Beginner94 (30. Mrz 2011)

Ok, vllt werde ich HTML anfangen, aber davor möchte ich nun endlich mein Programm zuende bringen.
Anid, ich habe deine Lösung nicht genau gefunden, vllt bin ich zu dumm...
Könnt ihr mir nochmal sagen, wie das Programm weiter machen soll, sobald es eine Lösung gefunden hat?!


----------



## nrg (30. Mrz 2011)

du setzt die letzte dame einfach ein feld daneben. dann geht die rekursion nach der nächsten lösung weiter. natürlich solltest du bei deiner lösung den stack durch eine iteration entlasten, sonst kassiert du wieder einen stackoverflow (wobei du es auch so schreiben kannst, dass der stack sich nach einer lösung wieder komplett abbaut)


----------



## Beginner94 (30. Mrz 2011)

Ok, ich habe mir angeschaut was eine Iteration ist, aber wie soll ich jetzt noch mein Programm in Schleifen umwandeln?
Hab ich vllt was falsch verstanden?
Gibt es noch eine Möglichkeit meinen StackoverflowError zu verhindern?


----------



## goto94 (30. Mrz 2011)

Beginner94 hat gesagt.:


> Ok, ich habe mir angeschaut was eine Iteration ist, aber wie soll ich jetzt noch mein Programm in Schleifen umwandeln?
> Hab ich vllt was falsch verstanden?
> Gibt es noch eine Möglichkeit meinen StackoverflowError zu verhindern?



normal fängt man mit anderen problemen und verfahren an, um rekursives backtracking verstehen zu lernen.


----------



## nrg (30. Mrz 2011)

naja. damit meinte ich eigentlich einer iteration in der rekursion. so wie es Beginner? in seiner Lösung gemacht hat. dadurch ist dein Stack schonmal etwas entlastet

bei dir ist derzeit: 1 versuch = 1 methodenaufruf (edit: und auch jeden backtrack etc. hab deine lösung jetzt aber auch nur kurz überflogen). mit einer iteration wäre es 1 gültiger versuch = 1 methodenaufruf.

aber naja. warum red ich eigentlich. kuck dir die lösung von Beginner? an. sehr viel besser kann man die rekursion zum finden aller Lösungen kaum machen


----------



## goto94 (1. Apr 2011)

die valid()-Methode kann so abgeändert werden, dass nur eine Schleife benötigt wird. Das wäre Rechnerei mit den Indices und wäre nicht zeiteffizienter.


----------



## Beginner94 (1. Apr 2011)

goto94 hat gesagt.:


> die valid()-Methode kann so abgeändert werden, dass nur eine Schleife benötigt wird. Das wäre Rechnerei mit den Indices und wäre nicht zeiteffizienter.



Und was willst du mir damit sagen?
Ich weiß nämlich immer noch nicht, wie ich meinen Code ändern muss...
Ich bin schon dauernd am Probieren, aber mehr als 24 Lösungen hat er noch nicht geschafft.


----------



## goto94 (1. Apr 2011)

> Andere Methoden
> 
> Ein iterativer Reparaturalgorithmus beginnt mit einer beliebigen Stellung der Damen auf dem Brett. Es zählt dann die Anzahl der Konflikte, und versucht, durch Umpositionieren der Damen die Anzahl der Konflikte zu reduzieren. Effizient ist etwa, die Dame mit den meisten Konflikten senkrecht auf die Position zu verschieben, auf der die geringste Anzahl von Konflikten auftritt. Mit dieser Methode kann das 1.000.000-Damen-Problem ausgehend von einer „vernünftigen“ Versuchsposition gelöst werden. Derart große Bretter lassen sich mit expliziten Konstruktionsalgorithmen nicht lösen (triviale Lösungen ausgenommen); allerdings kann ein solcher Iterationsalgorithmus nicht mit Sicherheit eine Lösung finden.


Damenproblem ? Wikipedia
findet sehr schnell eine lösung oder gar keine und ist einfach zu implementieren.


----------



## kirax (1. Apr 2011)

BT ist aber einfacher...


----------



## Beginner94 (4. Apr 2011)

Ich habe jetzt wirklich viel ausprobiert, aber ich kann den Fehler nicht beheben. Kann mir bitte jemand sagen, was ich an meinem Code ändern muss, damit es funktioniert?


----------

