Anfang des Damenproblems

[Beginner94]

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]

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]

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]

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]

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

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]

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

 

[LoR]

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]

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

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]

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

 

[Beginner?]

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

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]

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]

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]

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]

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]

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]

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]

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

 

[Beginner94]

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

 

[kirax]

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]

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]

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

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]

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

 

[Beginner94]

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

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?

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]

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

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]

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]

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

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]

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]

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]

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

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

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

 

[kirax]

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

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]

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

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

 

[Andi_CH]

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

    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]

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]

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

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]

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

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]

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]

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