BlueJ: Das 8-Damen Problem (Backtracking)

[Ne0Nebul0sa]

Guten Tag liebes Forum,

Zunächst als Hinweis: Mir ist bekannt, dass das Problem möglicherweise auf Wikipedia behandelt wurde, aber ich möchte gerne selbst zum Ziel kommen ohne "abzuschreiben".

Ich stehe vor einem neuen "Problem" mit hoffentlich etwas mehr Wissen.

Bei der Umsetzung des s.g. 8-Damen Problems sollen zunächst zwei Ablaufmodelle (Struktogramme) erstellt werden. Das erste soll den Ablauf mit Backtracking beschreiben (natürlich auf das Projekt bezogen), das andere den Algorithmus für die "Kollision","Bedrohung" oder "Berührung" zweier Damen.

Das Schachbrett ist 8x8 Felder groß und es sollen acht Damen gesetzt werden.

Schön wäre es, wenn mir jemand sagen könnte, ob mein Pseudocode korrekt ist und ob es noch Optimierungen im Performancebereich gibt

Da wende ich mich insbesondere an Flashpixx, der mir letztes Mal (teilweise über private Nachrichten) gute Hinweise und Tipps gegeben hat.

Zur Problemlösung habe ich mir folgende Gedanken gemacht:

Einmalig: int x,y = 1


Methode(a) [Damen setzen]: 

Solange noch nicht alle acht Damen gesetzt wurden

-> rufe Methode( auf


Methode( [Damen setzen: durchlaufe das Schachbrett]:

1. Struktogramm: 

(2te Schleife in erster Schleife)

1. (while-)Schleife: Solange y kleiner gleich 8 

1.2. (while-)Schleife: Solange x kleiner gleich 8

1.2.1 if-Abfrage: Dame bedroht?

1.2.1.1 Fall ja (erhält false - s. anderes Struktogramm): x+1

1.2.1.2 Fall nein (erhält true - s. anderes Struktogramm): Dame setzen, return true.

1. y+1, x=1 setzen


(eigentliches Backtracking)

1.2.2 if-Abfrage: x,y gleich 8

1.2.2.1 Fall ja: gehe zu Position letzte Dame, lösche letzte Dame,

1.2.2.1.1 if-Abfrage: x kleiner 8 

1.2.2.1.1.1 Fall ja: x+1 

1.2.2.1.1.2 Fall nein: y+1, x=1 setzen

1.2.2.1.2 Dame setzen

1.2.2.2 Fall nein : rufe Methode rekursiv auf


Methode(c) [ist die Dame bedroht?]:

[I]Allgemeiner Gedanke:[/I]

Fall 1 - Diagonaler Lauf (rechts unten nach oben links): x-y=1

Fall 2 - Diagonaler Lauf  (links oben nach rechts unten): x+y=11

Von x,y = 1 ausgehend:

Fall 3 - waagerechter Lauf: y festgelegt, x+1

Fall 4 - senkrechter Lauf: x festgelegt, y+1


2. Struktogramm

Algorithmus durchlaufen:

Methode(d):

1. If-Abfrage für Fälle 1+2

1.1 Fall ja: return false (s. anderes Struktogramm)

1.2 Fall nein: return true (s. anderes Struktogramm)


Methode(e):

2. if-Abfrage für Fälle 3+4

1.1 Fall ja: return false (s. anderes Struktogramm)

1.2 Fall nein:

1.2.1 while-Schleife für Fälle 3+4: Solange x/y kleiner 8

1.2.1 x/y++

1.2.1 rufe Methode(e) rekursiv auf


1.2. return true (s. anderes Struktogramm)[/code]

Ich hoffe, dass mir geholfen wird und irgendjemand den Pseudocode durchschaut

Viele liebe Grüße & Danke

Ne0

PS: Diesmal sind alle Gedanken zum Code von mir - nicht wie letztes Mal ;-)

Bearbeitet 21. Juni 2012 von Ne0Nebul0sa

[flashpixx]

Zunächst als Hinweis: Mir ist bekannt, dass das Problem möglicherweise auf Wikipedia behandelt wurde, aber ich möchte gerne selbst zum Ziel kommen ohne "abzuschreiben".

Ich poste da mal den Link zu Wiki, falls es jemand auch nachlesen mag Damenproblem

Schön wäre es, wenn mir jemand sagen könnte, ob mein Pseudocode korrekt ist und ob es noch Optimierungen im Performancebereich gibt

also sieht schon mal gar nicht schlecht aus, leicht verwirrend Dein Pseudocode aber durchaus okay. Ob es jetzt performant und auch korrekt arbeitet habe ich auf die Schnelle nicht geprüft.

Da wende ich mich insbesondere an Flashpixx, der mir letztes Mal (teilweise über private Nachrichten) gute Hinweise und Tipps gegeben hat.

Da werd ich ja gleich rot.......

Einmalig: int x,y = 1


Methode(a) [Damen setzen]: 

Solange noch nicht alle acht Damen gesetzt wurden

-> rufe Methode( auf


Methode( [Damen setzen: durchlaufe das Schachbrett]:

1. Struktogramm: 

(2te Schleife in erster Schleife)

1. (while-)Schleife: Solange y kleiner gleich 8 

1.2. (while-)Schleife: Solange x kleiner gleich 8

1.2.1 if-Abfrage: Dame bedroht?

1.2.1.1 Fall ja (erhält false - s. anderes Struktogramm): x+1

1.2.1.2 Fall nein (erhält true - s. anderes Struktogramm): Dame setzen, return true.

1. y+1, x=1 setzen


(eigentliches Backtracking)

1.2.2 if-Abfrage: x,y gleich 8

1.2.2.1 Fall ja: gehe zu Position letzte Dame, lösche letzte Dame,

1.2.2.1.1 if-Abfrage: x kleiner 8 

1.2.2.1.1.1 Fall ja: x+1 

1.2.2.1.1.2 Fall nein: y+1, x=1 setzen

1.2.2.1.2 Dame setzen

1.2.2.2 Fall nein : rufe Methode rekursiv auf


Methode(c) [ist die Dame bedroht?]:

[I]Allgemeiner Gedanke:[/I]

Fall 1 - Diagonaler Lauf (rechts unten nach oben links): x-y=1

Fall 2 - Diagonaler Lauf  (links oben nach rechts unten): x+y=11

Von x,y = 1 ausgehend:

Fall 3 - waagerechter Lauf: y festgelegt, x+1

Fall 4 - senkrechter Lauf: x festgelegt, y+1

[/code]

[Ne0Nebul0sa]

also sieht schon mal gar nicht schlecht aus, leicht verwirrend Dein Pseudocode aber durchaus okay. Ob es jetzt performant und auch korrekt arbeitet habe ich auf die Schnelle nicht geprüft.

Hört sich gut an :-)

Wie verwirrend er ist, ist mir aufgefallen, als ich ihn geschrieben hatte. Davor war ich mit der korrekten Entzerrung der einzelnen Methoden und Funktionen so sehr beschäftigt, dass es mir nicht einmal auffiel

Ich werde "das" auf jedenfall nochmal als übersichtlicheres Struktogramm umschreiben, sodass ich auch selbst einen Durchblick in der Programmierungsphase habe.

Danke!

Ob es jetzt performant und auch korrekt arbeitet habe ich auf die Schnelle nicht geprüft.

Naja, das werd ich dann wohl in der Testphase sehen

Da werd ich ja gleich rot.......

Solange Du nicht blau anläuftst und dich übergibst ist mir das recht ;-)

Also so grob wäre das meine Überlegung, d.h. ich reduziere einmal via Rekursion das 8-Damenproblem auf ein 7-Damenproblem usw.

Hört sich auch gut an. Mich plagt aber das Gefühl, dass ich zwar weiß, was Du mit "linearer Funktion" meinst, aber ich nicht weiß, wie ich das umsetzen soll. Ich kann ja bspw. schlecht für die Horizontale schreiben

lineare Funktion: f(x)= mx+b <=> f(x) = b

:D

Du kannst auch um es zu vereinfachen, einfach die Damen via Schleife setzen und nur die Position backtracken.

Genau das hatte ich vor (ist hoffentlich aus dem Pseudocode ersichtlich) :bimei.

ob Du eine Heuristik nimmst um die Dame zu setzen, d.h. also eine zufallsbasierte Struktur, wobei man dort auch noch mal optimieren kann, wenn man sich überlegt welche Felder nicht belegt werden dürfen.

Das mit der Heuristik baue ich vielleicht noch ein. Das ist mit dem Bibs von SuM relativ einfach möglich

Aber die Felderüberlegung ist mir glaube ich zu weit. Dazu muss ich erst einmal an vielen anderen Stellen ansetzen.

Aber beachte, dass wenn Du das Problem auf n Damen und einem beliebig großen Feld machst ggf keine Lösung existiert, wenn nämlich sehr viele Damen verwendet werden, das muss man ggf im Quellcode dann besonders im "setzeDame" abfangen, wenn also kein Feld mehr gefunden werden kann

Wenn kein Feld mehr gefunden wird, so wird mein Code mit "return false" gestoppt - oder so ähnlich. Zumindest hatte ich in der Überlegungsphase daran gedacht ;)

Naja, ich schaue mal, ob und wie ich das die Tage realisieren kann und melde mich ggf. nochmal -wenn ich darf ;-)

Viele liebe Grüße & danke

Ne0

Bearbeitet 21. Juni 2012 von Ne0Nebul0sa

[flashpixx]

Hört sich auch gut an. Mich plagt aber das Gefühl, dass ich zwar weiß, was Du mit "linearer Funktion" meinst, aber ich nicht weiß, wie ich das umsetzen soll. Ich kann ja bspw. schlecht für die Horizontale schreiben

lineare Funktion: f(x)= mx+b <=> f(x) = b

Überleg Dir das doch einfach mal etwas praktisch, wenn Du zwei Damen hast, wann tritt eine "Kollision" auf, einmal wenn zwei Damen in der gleichen Zeile oder Spalte oder Diagonalen stehen. Nehmen wir mal praktisch an, Du hast eine Dame auf dem Feld (3,4) stehen, welche Felder sind dann ausgeschlossen, auf denen Du eine Dame stellen kannst?

[Ne0Nebul0sa]

Überleg Dir das doch einfach mal etwas praktisch, wenn Du zwei Damen hast, wann tritt eine "Kollision" auf, einmal wenn zwei Damen in der gleichen Zeile oder Spalte oder Diagonalen stehen. Nehmen wir mal praktisch an, Du hast eine Dame auf dem Feld (3,4) stehen, welche Felder sind dann ausgeschlossen, auf denen Du eine Dame stellen kannst?

Auf den Feldern (1-8,4), (3,1-8), (3,4), (4,3), (5,2), (6,1), (3,4), (2,5), (1,6), (2,3), (1,2), (4,5), (5,6), (6,7) und (7,8)

Das hatte mich auf den Ansatz

Methode(c) [ist die Dame bedroht?]:

Allgemeiner Gedanke:

Fall 1 - Diagonaler Lauf (rechts unten nach oben links): x-y=1

Fall 2 - Diagonaler Lauf  (links oben nach rechts unten): x+y=11

Von x,y = 1 ausgehend:

Fall 3 - waagerechter Lauf: y festgelegt, x+1

Fall 4 - senkrechter Lauf: x festgelegt, y+1

gebracht

:-)

Danke Dir & viele Grüße

Ne0

[flashpixx]

Fall 1 - Diagonaler Lauf (rechts unten nach oben links): x-y=1

Fall 2 - Diagonaler Lauf (links oben nach rechts unten): x+y=11

setze das einmal in Beziehung zu "linearen Funktionen". Mit Hilfe von ein wenig Mathematik kann man diese Prüfung recht effizient machen.

Fall 3 - waagerechter Lauf: y festgelegt, x+1

Fall 4 - senkrechter Lauf: x festgelegt, y+1

für diese beiden Fälle braucht man keine Schleife, das kann ohne prüfen.

[DerEinwanderer]

Hallo!

Ich kommen aus den Niederlanden (halbniederlande), daher ist mein Deutsch nicht so toll.

Bitte Sie haben Verständnis dafür :-)

Ich haben Das gleiche problem wie "Ne0Nebul0sa", bin aber schon weiter:

import sum.kern.*;

import sum.strukturen.*;

/**

 * @author Dieter VanDerOpple

 */


public class VanDerOpple {

    Bildschirm hatscherm;

    Stift hatpen;


    public VanDerOpple()

    {

        hatscherm = new Bildschirm(600,600);

        hatpen = new Stift();


        int damen = 8; 

        this.tekenensalgo(damen);

        int[] array = new int[damen];

        this.instellenDame(array, 0);

    }


    public void instellenDame(int[] array, int damen) {

        int stakingx, stakingy;   

        if (damen == array.length) {

            int lijn = 1; 

            for (int kolom : array)

            {

                     stakingx = (kolom + 1);

                     stakingy = lijn++;                

                     System.out.println(stakingx+","+stakingy);             

                     hatpen.bewegeBis(100,100); 

                     hatpen.bewegeBis((stakingx*20), (stakingy*20));

                     this.tekenenDame();               

            }

        }

        else {

            for (int koloma = 0; koloma < array.length; koloma++) {

                if (damen == 0) {

                    array[0] = damen; 

                    instellenDame(array, damen + 1); 


                }

                int kolomb = 0; 

                for (int lijna = 0; lijna < damen; lijna++) {  


                    if (array[lijna] != koloma)  

                        if (array[lijna] != koloma + (damen - lijna))    

                            if (array[lijna] != koloma - (damen - lijna))

                                kolomb++; 

                }

                if (kolomb == damen) {

                    array[damen] = kolomb;  

                    instellenDame(array, damen + 1); 

                }       

            }

        }

    }


    public void tekenensalgo(int Damennummer)

    {

        int x = Damennummer;

        int y = Damennummer;


        int xNaam = 1, yNaam = 1;


        hatpen.hoch();

        hatpen.bewegeBis(100,100);

        hatpen.runter();     

        for(int nummerb=1; nummerb<=y;nummerb++)

        {

            for(int nummeri=1; nummeri<=x;nummeri++)

            {

                hatpen.runter();

                hatpen.bewegeUm(20);              

                for(int i=1; i<=4; i++)

                {

                    hatpen.dreheUm(90);

                    hatpen.bewegeUm(20);

                }

                xNaam++;

            }

            hatpen.hoch();

            hatpen.bewegeBis(100,hatpen.vPosition()+20);

            hatpen.runter();

            yNaam++;

            xNaam = 1;

        }

        hatpen.hoch();

    }


    public void tekenenDame()

    {

        hatpen.runter();        

        hatpen.dreheUm(45);

        hatpen.runter();

        hatpen.bewegeUm(20);

        hatpen.hoch();

        hatpen.dreheUm(180);

        hatpen.bewegeUm(20);

        hatpen.dreheUm(135);

        hatpen.bewegeUm(20);

        hatpen.dreheUm(135);

        hatpen.runter();

        hatpen.bewegeUm(20);

        hatpen.hoch();

        hatpen.dreheBis(0); 

    }

}

Muss wohl was kaput gemacht haben, da Programm von hier kupiert und in meine "language" (weiß nicht das deutsches Word) übersetzt: Ling homepage war auch deutsch, daher schwierig für mich zu verstehen. Ansonsten hatte ich "SuM" genutzt, dass ist eine Bilbiothek: hier Soll nicht so gut sein, da aber deutsch, die helfen mir weiter. So. Hoffentlich habe ich alles erwänt und sie verstehen mich. Ich kann noch besser Englisch, falls er hilft. Ich kann auch Programm in ihre "language" übersetzen. "Google translate" ist manchmal hilfreich. Meine Frage sein, dass ich versuchen will eine schönen oeberflaeche für Gast machen will. Also ohne Console. Einmal hat das Program geklappt aber nun geht wohl die erste "for" nicht mehr da

System.out.println(stakingx+","+stakingy);    

nicht ausgegeben wird. Als Programm war aktiv, da wurden Ergebniss korrekt angezeigt, aber ich konnte nur mit

System.exit(0);

beenden. Dann war aber scherm weg und das willen ich nicht. mit

return false

wollte nicht klappen.

Also ich wäre froh, wenn sie Programm wieder aktivieren und mir helfen könen. Ich weiß meine language ist nicht so toll, aber bitte sie verstehen mich :-)

Ich danke von Herzen und wünsche Ihnen einen angenehmen Tag (hat mir mal ein Deutscher geschrieben, hoffe ich nicht beleidigen niemanden)

Dieter

[flashpixx]

I will answer in englisch.

Please take a look to the picture in this post. You see the queen (red circle), and the lines are the fields which can not be used by a new queen. You use loops for detecting this problem. This is very slow and inefficient. Please think about the chessboard, your board is a NxN array, each field in the board can be addressed by its numbers (x,y). So you only need to store the size of the board.

On the first step I set my first queen into the field, it is a good solution to do this random. You can do this because there exists a theorem that a random algorithm is not better / worse to another. Here comes the backtracking now.

So next we will try to set the next queen and we get the position also with random, but now we must check if we can place the queen. So this can be do with a little math. You see the green lines, which are parallel to the axis, so we can check both situation with an if contraint. The blue lines are the diagonal lines which can describe with lineare functions ( Linear function - Wikipedia, the free encyclopedia ). The yellow triangular help you to create the lineare function. Each lineare function can be written as y = m*x+b so x and y are the coordinates, m the rise and b the value of the y-axis. So if I would place a new queen, I would check only all lineare function on all other queens. If there is a collision, the f(x)=y (f = lineare function) equation is satisfied. So on each placed queen you must create this linear function f (you need only one f, because you see in the picture, that the blue lines are symmetric, this changes only the sign in a parameter of the lineare function f). You generate new coordinates until you can place the queen or you have all fields are visited. If we can not place a queen, than we step back within the backtracking and create for the prior queen a new position. Attention about the recursion: Each queen must be stored a mark, which field(s) is / are visited. If a queen has visited all board fields, the backtracking must be stopped, because there does not exists a solution. You must step back in the backtracking.

Generally you can place n queens on a NxN field, so first you should check if there are more queens like the board dimension, if yes, there exists no optional solution.

You need only one loop for creating the coordinates of a new queen. My hint is, that you use classes, so you create a queen class in which the linear function is stored and you can check the collision like

bool collision = false;

foreach(queen in queenlist && !collision)

     collision = queen.checkCollision(new_queen)

if (collision)

     new_queen.generatePosition()

Than you create only a board class, which stores the size of the board and a list of the placed queens. Your code is very large and you do a lot of unnecessary operation. You need only the size of the board, a list of queens and each queen must / can be check if there is a collision with another queen. So the queen must stored the position of itself. The lineare function can be create relative to the queen or global to the board (the picture shows the relative solition).

You create a native solution, that means you try to solve problem with iterate over all solution. This works for small problems only, but not for complex problems. You can calculate if your board has a size 1000x1000 fields and you will place 200 queens on it, how many backtracking steps are needed to create a solutions. On a board with 8x8 fields you must check 2^48 different options to find a solution in the worst-case. Other algorithms like generic algorithms are better, so my hint to add a random component can help you.

Your code is a sequential code without any object-orientated structures, so the first is, that you use this paradigm to describe the problem. A sequential code creates a lot of problems, because you must create the correct structures and calls in it. A class is a black box structure, so you can use it, but you do not know the content. Also split input, output and algorithms, do not mix output and algorithm, because this is very confusing. If you would like to debug your code, use a debugger or add a logger to the code. You do not need any rotation option on the queen position or board position, because with the maths I can calculate each position directly and need no iteration over the fields. Looping over large datasets are very slow, so try to beware loops if you can determine the position / result directly.

Reduce your code and you can find the bugs easy, also keep in mind, that you create a efficient algorithms a brute-force method is not efficient

Bearbeitet 6. Juli 2012 von flashpixx

[Ne0Nebul0sa]

Hi DerEinwanderer, Hi Flashpixx,

Ich habe mittlerweile auch mein Programm umgesetzt, sehe aber den Wald vor lauter Bäumen nicht mehr..

Zum einen habe ich zwar die Backtracking-methode, aber die wird in meinem Programm nicht genutzt, da ich den wichtigen Teil des Backtrackings irgendwie in die Methode "SchachbrettDurchlaufen" eingebaut habe.

Bei der Methode "bedroht" weiß ich leider noch immer nicht, wie ich die linearen Funktionen nutzen soll und dementsprechend scheiter ich auch daran. Meine Idee ist eher quantitativ als qualitativ.

Weiter weiß ich nicht, wie ich die Klasse "Dame" aufbauen soll. Ich habe im Moment lediglich Methoden, die die Dame zeichnen und ich denke nicht, dass damit genüge getan ist.

Allgemein weiß ich auch nicht, ob ich nicht lieber ein Typ Objekt statt des Typs Dame nehmen sollte. Denn meine Klasse Dame kann nichts, was sie grundlegend von einem Element/Objekt unterscheidet.

Ob die Methoden "setzeDame" und "loescheDame" richtig sind, weiß ich auch nicht. Bisher ist mein ganzes Projekt eher ein Scheiterhaufen als ein wirklicher Erfolg :-D

Mein eigentliches Ziel ist das nDamen Problem mit einer GUI darzustellen (also ein Schachbrett mit n*n Feldern und n platzierten Damen). Ich habe allerdings gehört, dass das Problem bis maximal 25 Damen (25*25 Feldern) umsetzbar sei. Danach muss wohl ein weiterer "Trick" her.

Letztendlich soll das fertige Programm in etwa aussehen wie in diesem Video:

Ich weiß, der Uploader stellt den Quellcode zur Verfügung, aber es wäre gut, wenn ich mit eurer Hilfe auf die Lösung käme :-)

Nun mein Programmfortschritt:

import sum.kern.*;

/**

 * @author 

 * @version 

 */

public class nDamen

{

    // Bezugsobjekte

    Bildschirm hatBildschirm;

    Stift hatStift;

    // Attribute


    // Konstruktor

    public nDamen(int DamenAnzahl) //bis maximal 25 moeglich!

    {

        hatBildschirm = new Bildschirm();

        hatStift = new Stift();

    }


    // Dienste

    public void DameSetzen(int x, int y, Dame pDame)

    {

        int N = 8;

        for(int i=0; i<N; i++)//zunaechst 8DamenPrblem DamenAnzahl)

        {

            this.SchachbrettDurchlaufen(x,y, pDame);

        }

    }


    public void SchachbrettDurchlaufen(int x, int y,Dame pDame)

    {

        this.zeichnen();

        while(y<=8)

        {

            while(x<=8)

            {

                if(this.bedroht(pDame, x, y))

                {

                    x++;

                }

                else

                {

                    this.setzeDame(pDame);

                }

            }

            y++;

            x=1;

        }

    }


    public void Backtracking(Dame pDame, int x, int y)

    {


        if(x == 8 && y == 8)

        {

            this.loescheDame(x, y);

            if(x<8)

                x++;

            else if(y<8)

            {

                y++;

                x=1;

            }

            else

            {

                hatStift.hoch();

                hatStift.bewegeBis(500,500);

                hatStift.runter();

                hatStift.schreibeText("Es gibt keine Loesung!");

                hatStift.hoch();

            }

            this.setzeDame(pDame);

        }

        else

            this.Backtracking(pDame, x, y);

    }


    public void loescheDame(int x, int y)

    {

        hatStift.radiere();

        this.zeichnen();

        hatStift.normal();

    }


    public void zeichnen()

    {      

        for(int i=1; i<=4; i++)

        {

            hatStift.runter();

            hatStift.bewegeUm(1);

            hatStift.dreheUm(90);

        }


        hatStift.hoch();

        hatStift.bewegeUm(1);

    }


    public boolean bedroht(Dame pDame, int x, int y)

    {

        if(x == zH)

            return false;

        else if(y == zV)

            return false;

        else if(x - y == zH - zV)

            return false;

        else if(x + y == zH + zV)

            return false;

        else 

            return true;

    }


    public void setzeDame(Dame pDame)

    {

        this.zeichnen();

    }

}

Meine Klasse Dame sieht wie folgt aus:

import sum.kern.*;

import sum.strukturen.*;

/**

 * @author 

 * @version 

 */

public class Dame

{

    // Bezugsobjekte

    Stift hatStift;

    // Attribute


    // Konstruktor

    public Dame()

    {

         hatStift = new Stift();

    }



    // Dienste

    public void zeichneDame()

    {

          hatStift.runter();

          hatStift.bewegeUm(1);

          hatStift.hoch();

          hatStift.bewegeUm(-0,5);

          hatStift.runter();

          hatStift.dreheUm(90);

          hatStift.bewegeUm(1);

    }

}

Danke für die Hilfe und viele Grüße

Ne0

Nachtrag: Mir ist noch aufgefallen, dass bisher nur ein Feld des Schachbretts gezeichnet würde. Das ist aber für mich erst einmal nebensächlich und ist später mit weiteren Schleifen zu lösen :-)

Bearbeitet 2. Juli 2012 von Ne0Nebul0sa
Nachtrag

[flashpixx]

Bei der Methode "bedroht" weiß ich leider noch immer nicht, wie ich die linearen Funktionen nutzen soll und dementsprechend scheiter ich auch daran. Meine Idee ist eher quantitativ als qualitativ.

Wie bedeutet denn "bedroht"? Das heißt, dass eine Dame auf der gleichen Horizontalen / Vertikalen / Diagonalen steht, wie schon eine andere. Du kannst die Horizontale und Vertikale extrem einfach prüfen, die Diagonale durch die lineare Funktion, d.h. Du musst eine Funktion aufstellen, in die Du die x-Koordinate einer neuen Dame einsetzt, diese Funktion berechnet dann eine Y-Koordinate und wenn diese gleich der Y-Position der neuen Dame ist, dann hast Du eine Kollision. Wie man diese lineare Funktion aufstellt, steht in den Verlinkten Wikipediaartikeln (Stichwort Steigungsdreieck)

Weiter weiß ich nicht, wie ich die Klasse "Dame" aufbauen soll. Ich habe im Moment lediglich Methoden, die die Dame zeichnen und ich denke nicht, dass damit genüge getan ist.

Allgemein weiß ich auch nicht, ob ich nicht lieber ein Typ Objekt statt des Typs Dame nehmen sollte. Denn meine Klasse Dame kann nichts, was sie grundlegend von einem Element/Objekt unterscheidet.

Was muss denn eine Damen alles können? Im Moment knallst Du den Quellcode in eine Klasse ohne sinnvoll zu strukturieren. Das was Du dort fabrizierst ist Spagetthicode. Ich habe schon so viele Anregungen gepostet (auch im letzten Post), im Grunde muss Du das nur noch in Quellcode gießen.

Ob die Methoden "setzeDame" und "loescheDame" richtig sind, weiß ich auch nicht. Bisher ist mein ganzes Projekt eher ein Scheiterhaufen als ein wirklicher Erfolg :-D

Man braucht weder setze noch lösche Dame, denn ich kann durch einen einzigen Aufruf (generatePosition) die Koordinaten für eine Dame generieren und kann dann prüfen, ob eine Kollision auftritt, wenn ja generiere ich neue Positionen.

Mein eigentliches Ziel ist das nDamen Problem mit einer GUI darzustellen (also ein Schachbrett mit n*n Feldern und n platzierten Damen).

Bei Dir klappt noch nicht einmal der Algorithmus und bevor der nicht funktioniert, würde ich an so etwas wie GUI überhaupt nicht denken. GUI kommt zum Schluss.

Ich habe allerdings gehört, dass das Problem bis maximal 25 Damen (25*25 Feldern) umsetzbar sei.

Danach muss wohl ein weiterer "Trick" her.

auch das habe ich in meinem letzten Post ausgeführt, nennt sich genetische Algorithmen.

Fang doch einmal damit an überhaupt ohne diesen ganzen sum.kern Quatsch das Problem zu lösen. Schreibe ein einfaches Hauptprogramm und dann brauchst Du dazu zwei Klassen mehr nicht um den Algorithmus überhaupt erst einmal funktionsfähig zu bekommen. Erst wenn der Algorithmus fest ist, dann kannst Du über die GUI nachdenken.

[Ne0Nebul0sa]

Wie bedeutet denn "bedroht"? Das heißt, dass eine Dame auf der gleichen Horizontalen / Vertikalen / Diagonalen steht, wie schon eine andere. Du kannst die Horizontale und Vertikale extrem einfach prüfen, die Diagonale durch die lineare Funktion, d.h. Du musst eine Funktion aufstellen, in die Du die x-Koordinate einer neuen Dame einsetzt, diese Funktion berechnet dann eine Y-Koordinate und wenn diese gleich der Y-Position der neuen Dame ist, dann hast Du eine Kollision. Wie man diese lineare Funktion aufstellt, steht in den Verlinkten Wikipediaartikeln (Stichwort Steigungsdreieck)

okay, für die Diagonalen müsste gelten:

f(x) = -1/2x+8 (von oben links nach unten rechts) und f(x) = 1/2x von unten links nach oben rechts, wenn der Ursprung unten links liegt.

für die x-Koordinate setze bspw. 4 ein. Dann ist der y-Wert 6 bzw. 2?.

..und wenn ich das richtig verstanden habe tritt eine Kollision auf, wenn die neue Dame (also die Dame, dessen Position ich eben ermittelt habe) die gleiche y-Koordinate hat wie die bereits vorhandene Dame. Dazu müsste ich mir alle Koordinaten der bereits erfolgreich gesetzten Damen merken, oder?

Dann könnte ich die Werte in einer Liste speichern und diese mit den neuen Koordinaten abfragen. Aber wie durchsuche ich die Liste (programmiertechnisch)? ..und wie gebe ich diese lineare Funktion in Java an?

für die Horizontalen:

f(x) = b (b ist variabel für die einzelnen Horizontalen)

für die Vertikalen:

f(x) = x

Was muss denn eine Damen alles können?

Ehrlich gesagt weiß ich nicht, was die Dame können muss. Ich finde, sie sollte sich selbst erzeugen und entfernen können und wissen, wie sie laufen kann damit sie weiß, ob sie kollidiert. Aber wie die einzelnen Methoden aussehen, ist mir wieder schleierhaft.

Im Moment knallst Du den Quellcode in eine Klasse ohne sinnvoll zu strukturieren. Das was Du dort fabrizierst ist Spagetthicode. Ich habe schon so viele Anregungen gepostet (auch im letzten Post), im Grunde muss Du das nur noch in Quellcode gießen.

Das ich weder nach dem MVC-Prinzip strukturiert habe, ist mir jetzt auch klar geworden :upps

Der Rest liegt wohl daran, dass mir der Durchblick fehlt - trotz vorheriges Struktogramm.

Daher auch der

Spagetthicode

. Nettes Wort übrigens

Ich habe schon so viele Anregungen gepostet (auch im letzten Post), im Grunde muss Du das nur noch in Quellcode gießen.

Das mag sein, ich habe doch auch versucht zu einer Lösung zu kommen - auch wenn mein Spaghetticode sicherlich andere Bände spricht. Aber ich schaffe es einfach nicht

Man braucht weder setze noch lösche Dame, denn ich kann durch einen einzigen Aufruf (generatePosition) die Koordinaten für eine Dame generieren und kann dann prüfen, ob eine Kollision auftritt, wenn ja generiere ich neue Positionen.

"generatePosition" kannte ich nicht. Es gibt wohl in SuM eine Methode die eine Zufallsposition generiert :upps:upps (ganzeZufallszahl).

Dass heißt ich gestalte meine Methode wie folgt:

Generiere Position auf dem Schachbrett (für ein Schachbrett mit 8x8 Feldern):

derRechner.ganzeZufallszahl(1,8),derRechner.ganzeZufallszahl(1,8)

alle Damen setzen: for-schleife: bis 8 Damen:

derRechner.ganzeZufallszahl(1,8),derRechner.ganzeZufallszahl(1,8)

if(kollision)

derRechner.ganzeZufallszahl(1,8),derRechner.ganzeZufallszahl(1,8)

else

zeichneDame

Aber das wäre doch kein Backtracking?

Bei Dir klappt noch nicht einmal der Algorithmus und bevor der nicht funktioniert, würde ich an so etwas wie GUI überhaupt nicht denken. GUI kommt zum Schluss.

Alles klar, chef.

auch das habe ich in meinem letzten Post ausgeführt, nennt sich genetische Algorithmen.

Fang doch einmal damit an überhaupt ohne diesen ganzen sum.kern Quatsch das Problem zu lösen. Schreibe ein einfaches Hauptprogramm und dann brauchst Du dazu zwei Klassen mehr nicht um den Algorithmus überhaupt erst einmal funktionsfähig zu bekommen. Erst wenn der Algorithmus fest ist, dann kannst Du über die GUI nachdenken.

Okay. Zunächst erst einmal ohne genetische Algorithmen.

Den Pseudocode den ich oben gepostet habe: ist der so in Ordnung?

Mein Hauptprogramm sollte (nach meinen bisherigen Ideen) folgendes machen, also: Methode "generierePosition" aufrufen, dann "alleDamensetzen". Mehr denke ich nicht.

Die beiden Methoden würde ich in eine seperate Klasse packen (nicht in die Klasse "Dame").

Passt das soweit?

Vielen Dank & viele Grüße

Ne0

Bearbeitet 2. Juli 2012 von Ne0Nebul0sa

[flashpixx]

..und wenn ich das richtig verstanden habe tritt eine Kollision auf, wenn die neue Dame (also die Dame, dessen Position ich eben ermittelt habe) die gleiche y-Koordinate hat wie die bereits vorhandene Dame. Dazu müsste ich mir alle Koordinaten der bereits erfolgreich gesetzten Damen merken, oder?

wir kommen langsam in die richtige Richtung. Mein Tipp, die lineare Funktion wird einfacher, wenn man immer die Dame, die man schon auf dem Brett stehen hat, gedanklich in den Koordinatenursprung legt.

Dann könnte ich die Werte in einer Liste speichern und diese mit den neuen Koordinaten abfragen. Aber wie durchsuche ich die Liste (programmiertechnisch)? ..und wie gebe ich diese lineare Funktion in Java an?

Ich hatte was über Klassen geschrieben und ich hatte etwas Pseudocode zur Kollisionserkennung gepostet. Du brauchst keine Liste mit Koordinaten

für die Horizontalen:

f(x) = b (b ist variabel für die einzelnen Horizontalen)

für die Vertikalen:

f(x) = x

ja

Ehrlich gesagt weiß ich nicht, was die Dame können muss. Ich finde, sie sollte sich selbst erzeugen und entfernen können und wissen, wie sie laufen kann damit sie weiß, ob sie kollidiert. Aber wie die einzelnen Methoden aussehen, ist mir wieder schleierhaft.

Erzeugung = Konstruktor

Entfernen = Destruktor, brauchst Du hier aber nicht

laufen = anderes Feld besetzen

Kollision erkennen mit einer anderen Dame

Der Rest liegt wohl daran, dass mir der Durchblick fehlt - trotz vorheriges Struktogramm.

Ein Struktogramm bringt Dir hier nichts, außerdem ist es auch eine veraltete Darstellung. Ein Struktogramm kannst Du nur verwenden, wenn Du eine einzelne Methode darstellen willst, für die Strukturen von Klassen wird UML verwendet (bzw. andere Diagramme)

http://de.wikipedia.org/wiki/UML

http://de.wikipedia.org/wiki/Aktivitätsdiagramm

http://de.wikipedia.org/wiki/Sequenzdiagramm

Das mag sein, ich habe doch auch versucht zu einer Lösung zu kommen - auch wenn mein Spaghetticode sicherlich andere Bände spricht. Aber ich schaffe es einfach nicht

OOP ist nichts anderes als das man "jedes Ding aus der realen Welt" in eine Klassenstruktur packt und sich eben überlegt was dieses "Ding" innerhalb des Programms können muss (=Methodenname). Welche Inhalte das "Ding" dann hat ist dann das Property.

Also Auto, Farbe, fahren:

Auto = Klasse

Farbe = Property

fahren = Methode

Jedes "Ding" also jede Klasse, steht mit anderen "Dingen" in Bezieheung z.B. Auto und Reifen.

"generatePosition" kannte ich nicht. Es gibt wohl in SuM eine Methode die eine Zufallsposition generiert :upps:upps (ganzeZufallszahl).

Wie wäre es, wenn Du diesen Quark von SuM in die Tonne trittst und es erst mal mit den normalen Standard Java Strukturen machst

Random (Java 2 Platform SE v1.4.2)

"generatePosition" ist einfach ein Methodenname, man kann selbst die Namen festlegen. Dieser Methodenname sollte verdeutlichen, dass eine Position erzeugt (generiert) wird.

Generiere Position auf dem Schachbrett (für ein Schachbrett mit 8x8 Feldern):

derRechner.ganzeZufallszahl(1,8),derRechner.ganzeZufallszahl(1,8)

alle Damen setzen: for-schleife: bis 8 Damen:

derRechner.ganzeZufallszahl(1,8),derRechner.ganzeZufallszahl(1,8)

if(kollision)

derRechner.ganzeZufallszahl(1,8),derRechner.ganzeZufallszahl(1,8)

else

zeichneDame

Wieso generiert das Schachbrett die Positionen? Das Brett hat keine Position. Das Brett ist lediglich ein Koordinatensystem und hat eine Liste mit n Damen. Wieso wird in der Schleife gezeichnet, wenn es OOP sein soll, dann muss das Brett sich zeichnen können und jedes Objekt, das durch das Brett dargestellt wird, muss zeichnen können. Aber GUI fällt raus, ebenso wie SuM !

Mein Hauptprogramm sollte (nach meinen bisherigen Ideen) folgendes machen, also: Methode "generierePosition" aufrufen, dann "alleDamensetzen".

Wieso soll das Hauptprogramm generierePositionen aufrufen? Ich kann keine Dame ohne ein Schachbrett setzen und wieso "alleDamensetzen", Du setzt eine Dame nach der anderen

Die beiden Methoden würde ich in eine seperate Klasse packen (nicht in die Klasse "Dame").

Wieso eine seperate Klasse? Noch einmal der Hinweis den Algorithmus kann man ohne SuM machen. Du solltest erst einmal versuchen, dass Du ein Schachbrett beliebiger Größe erzeugen kannst und darauf n Damen platzierst, wobei auf jedem Feld immer nur eine Dame stehen darf. Dein Hauptprogramm soll somit verschiedene Schachbretter unterschiedlicher oder gleicher Größe erzeugen können und auf jedem dieser Bretter sollen einfach n Damen platziert werden ohne dass zwei Damen auf den gleichen Positionen stehen. Das Ergebnis kannst Du auf der Konsole ausgeben. Das Hauptprogramm sollte dann ungefähr so aussehen:

public static void main(String[] argc) {


     Brett x = new Brett(2);

     Brett y = new Brett(8);


     System.out.println("Ausgabe Brett 1:\n"+x);

     System.out.println("Ausgabe Brett 2:\n"+y);

}

Die Ausgabe kann dann so aussehen

Ausgabe Brett 1:

Dame auf Position (1,1)

Dame auf Position (2,2)


Ausgabe Brett 2:

Dame auf Position (1,1)

Dame auf Position (4,5)

Dame auf Position (6,8)

Dame auf Position (2,4)

Dame auf Position (3,7)

Dame auf Position (5,4)

Dame auf Position (3,2)

Dame auf Position (1,4)

Bearbeitet 2. Juli 2012 von flashpixx

[Ne0Nebul0sa]

wir kommen langsam in die richtige Richtung. Mein Tipp, die lineare Funktion wird einfacher, wenn man immer die Dame, die man schon auf dem Brett stehen hat, gedanklich in den Koordinatenursprung legt.

Super, danke.

Ich hatte was über Klassen geschrieben und ich hatte etwas Pseudocode zur Kollisionserkennung gepostet. Du brauchst keine Liste mit Koordinaten

Mh, okay. Dann bin ich wohl noch immer auf den Holzweg. Wärst Du so nett mir die entsprechende Stelle zu zitieren? Ich bin nicht sicher, was Du meinst :-)

Erzeugung = Konstruktor

Entfernen = Destruktor, brauchst Du hier aber nicht

laufen = anderes Feld besetzen

Kollision erkennen mit einer anderen Dame

Also stelle ich im Hauptprogramm lediglich durch den Konstruktor die entsprechenden Damen etc. her, bzw. durch eine Main-Methode?

Ach, und ich setze die Damen nicht sondern prüfe vorher ob sie passen und falls nicht, dann setzen?

Wie müsste ich denn die linearen Funktionen, die ich gepostet habe, in Java umsetzen?

Habe mit linearen Funktionen noch nicht programmiert - zumindest nicht absichtlich ;-)

..und damit kann ich dann auch die Damenkollision erkennen.

Ein Struktogramm bringt Dir hier nichts, außerdem ist es auch eine veraltete Darstellung. Ein Struktogramm kannst Du nur verwenden, wenn Du eine einzelne Methode darstellen willst, für die Strukturen von Klassen wird UML verwendet (bzw. andere Diagramme)

Unified Modeling Language

Aktivitätsdiagramm

Sequenzdiagramm

Richtig, danke. Das Aktivitätsdiagramm und das Sequenzdiagramm werde ich mir mal anschauen.

OOP ist nichts anderes als das man "jedes Ding aus der realen Welt" in eine Klassenstruktur packt und sich eben überlegt was dieses "Ding" innerhalb des Programms können muss (=Methodenname). Welche Inhalte das "Ding" dann hat ist dann das Property.

Also Auto, Farbe, fahren:

Auto = Klasse

Farbe = Property

fahren = Methode

Jedes "Ding" also jede Klasse, steht mit anderen "Dingen" in Bezieheung z.B. Auto und Reifen.

Das ist mir in der Theorie auch bewusst - meist fehlt mir die logische Übetragung auf das Praxisbeispiel :-(

Wie wäre es, wenn Du diesen Quark von SuM in die Tonne trittst und es erst mal mit den normalen Standard Java Strukturen machst

Random (Java 2 Platform SE v1.4.2)

"generatePosition" ist einfach ein Methodenname, man kann selbst die Namen festlegen. Dieser Methodenname sollte verdeutlichen, dass eine Position erzeugt (generiert) wird.

Nichts lieber als das. Allerdings bin ich durch die Schule genötigt diesen Quark zu nutzen :-(. Insofern wäre ich froh, wenn wir damit, so schwer es auch sein mag, weiterarbeiten könnten.

Okay, danke. Da kann ich wieder auf SuM zurückgreifen, wenn ich es schon nutzen muss kann ich es ja auch benutzen :-).

Wieso generiert das Schachbrett die Positionen? Das Brett hat keine Position. Das Brett ist lediglich ein Koordinatensystem und hat eine Liste mit n Damen.

Wieso wird in der Schleife gezeichnet, wenn es OOP sein soll, dann muss das Brett sich zeichnen können und jedes Objekt, das durch das Brett dargestellt wird, muss zeichnen können.

Aber GUI fällt raus, ebenso wie SuM !

Soll es ja nicht. Also doch eine Liste? Du verwirrst mich :-D :-D

Mh, okay. Aber wie realisiere ich das ganze in OOP? Meinst Du damit rekursiv?

Ich würde gerne die GUI am Ende machen, ist das okay?

Wieso soll das Hauptprogramm generierePositionen aufrufen? Ich kann keine Dame ohne ein Schachbrett setzen und wieso "alleDamensetzen", Du setzt eine Dame nach der anderen

Nun, da die erste Position der Dame generiert wird, oder nicht? Mit "alleDamensetzen" meinte ich eben die Prozedur, eine zweite Dame an eine bestimmte Stelle zu setzen und wenn diese kollidiert, diese auf eine andere Position zu verschieben (sollte ich das auch zufällig machen oder eher strukturiert?).

Wieso eine seperate Klasse?

Nun, da die Methoden nicht mehr zum Hauptprogramm oder zur Dame gehören, oder?

Noch einmal der Hinweis den Algorithmus kann man ohne SuM machen. Du solltest erst einmal versuchen, dass Du ein Schachbrett beliebiger Größe erzeugen kannst und darauf n Damen platzierst, wobei auf jedem Feld immer nur eine Dame stehen darf.

Klar :-). Hier nochmal die Frage: Wie mache ich das Schachbrett objektorientiert? Rekursiv?

..und n Damen platziere ich indem nach oben genannten Muster.

Dein Hauptprogramm soll somit verschiedene Schachbretter unterschiedlicher oder gleicher Größe erzeugen können und auf jedem dieser Bretter sollen einfach n Damen platziert werden ohne dass zwei Damen auf den gleichen Positionen stehen. Das Ergebnis kannst Du auf der Konsole ausgeben. Das Hauptprogramm sollte dann ungefähr so aussehen:

...

Okay, die Main-Methode soweit klar. Ich könnte ja zusätzlich noch bei der Kollision abfragen, ob die Damenposition bereits belegt ist indem ich die gesetzte Position der Dame mit der neuen vergleiche.

Wie ich auf die Idee mit der Liste kam:

Wie kann ich den prüfen, wenn beispielsweise 6 (von 8) Damen platziert sind, ob die 7te nicht mit einer der anderen sechs kollidiert? Ich meine, ich könnte mir die letzte Dame (und ihre Position) in einer Variable merken, aber alle sechs Damen (und ihre Positionen?)

Da liegt auch noch eine gedankliche Lücke.

Danke Dir und viele Grüße

Ne0

[flashpixx]

Mh, okay. Dann bin ich wohl noch immer auf den Holzweg. Wärst Du so nett mir die entsprechende Stelle zu zitieren? Ich bin nicht sicher, was Du meinst :-)

You need only one loop for creating the coordinates of a new queen. My hint is, that you use classes, so you create a queen class in which the linear function is stored and you can check the collision like

bool collision = false;

foreach(queen in queenlist && !collision)

     collision = queen.checkCollision(new_queen)

if (collision)

     new_queen.generatePosition()

Also stelle ich im Hauptprogramm lediglich durch den Konstruktor die entsprechenden Damen etc. her, bzw. durch eine Main-Methode?

Die main-Methode ist der Einstiegspunkt für die JRE. Noch einmal als Anmerkung, kann eine Dame ohne Schachbrett existieren, also ist dies sinnvoll? Damit kannst Du die Frage auch selbst beantworten.

Ach, und ich setze die Damen nicht sondern prüfe vorher ob sie passen und falls nicht, dann setzen?

Ja Du kannst doch auch z.B. wenn der König im Schach stehen würde ihn nicht auf dieses Feld setzen

Wie müsste ich denn die linearen Funktionen, die ich gepostet habe, in Java umsetzen?

Habe mit linearen Funktionen noch nicht programmiert - zumindest nicht absichtlich ;-)

Das ist das gleiche Problem, wie bei Deinem Damenproblem, Du musst Dir überlegen durch welche Komponenten eine lineare Funktion repräsentiert ist und Du kannst dies z.B. sehr allgemein halten und wenn Du es sehr detailliert machen willst als eigene OOP Struktur entwerfen (theoretisch brauchst Du dies hier aber nicht, zur Übung wäre es aber sinnvoll). Sprich was muss eine lineare Funktion alles an Eigenschaften und Methoden haben, damit Du sie eben der mathematischen Repräsentation verwenden kannst.

Nichts lieber als das. Allerdings bin ich durch die Schule genötigt diesen Quark zu nutzen :-(. Insofern wäre ich froh, wenn wir damit, so schwer es auch sein mag, weiterarbeiten könnten.

In realen Projekten hast Du so etwas nicht, d.h. gewöhne Dich nicht daran. Der Algorithmus (!) kann ohne diese SuM Funktionen entworfen werden und genau das solltest Du tun. Je weniger Overhead Du in einem Algorithmus hast um so effizienter wird er. Die graphische Darstellung kannst Du meinetwegen mit SuM machen, aber im Moment sollst Du nur den Algorithmus entwerfen!

Soll es ja nicht. Also doch eine Liste? Du verwirrst mich :-D :-D

Du brauchst eine Liste, aber in dieser werden keine Koordinaten gespeichert.

Mh, okay. Aber wie realisiere ich das ganze in OOP? Meinst Du damit rekursiv?

OOP hat nichts mit Rekursion zu tun und soweit bist Du nicht. Bevor Du überhaupt das Backtracking entwerfen kannst, setzte das vereinfachte Beispiel um, d.h. zwei Schachbretter (bzw. n Bretter) und auf jedem Brett n Damen so positioniert, dass auf keinem Feld mehr als zwei Damen stehen können.

Ich würde gerne die GUI am Ende machen, ist das okay?

Am Ende ja und wenn Du vorher das ganze ordentlich aufgebaut hast, dann ist die GUI mit wenigen Codezeilen gemacht.

Nun, da die erste Position der Dame generiert wird, oder nicht? Mit "alleDamensetzen" meinte ich eben die Prozedur, eine zweite Dame an eine bestimmte Stelle zu setzen und wenn diese kollidiert, diese auf eine andere Position zu verschieben (sollte ich das auch zufällig machen oder eher strukturiert?).

Wieso prüft eine "externe Funktion" ob eine Kollision mit einer anderen Dame existiert. Jede Dame kann selbst prüfen, ob sie mit einer anderen in Kollision steht

Nun, da die Methoden nicht mehr zum Hauptprogramm oder zur Dame gehören, oder?

Wieso gehört die Kollisionserkennung nicht zum Hauptprogramm und nicht zur Dame?

Klar :-). Hier nochmal die Frage: Wie mache ich das Schachbrett objektorientiert? Rekursiv?

OOP != Rekursion !!

Was ist denn ein Schachbrett in der Realität?

Okay, die Main-Methode soweit klar. Ich könnte ja zusätzlich noch bei der Kollision abfragen, ob die Damenposition bereits belegt ist indem ich die gesetzte Position der Dame mit der neuen vergleiche.

Das muss gar nicht explizit geprüft werden, wenn Du Kollisionserkennung richtig ist, dann schließt sie automatisch aus, dass eine Dame auf das gleiche Feld einer anderen gesetzt werden kann

Wie kann ich den prüfen, wenn beispielsweise 6 (von 8) Damen platziert sind, ob die 7te nicht mit einer der anderen sechs kollidiert? Ich meine, ich könnte mir die letzte Dame (und ihre Position) in einer Variable merken, aber alle sechs Damen (und ihre Positionen?)

Da liegt auch noch eine gedankliche Lücke.

Eine, genau eine, Liste brauchst Du, aber nicht für die Koordinaten !!

Dieser Ansatz ist wieder ein sequentieller und der ist gerade bei Java falsch !

Du musst das OOP Paradigma beherrschen, d.h. bilde die Realität genauso in Klassen, Methoden und Properties ab, dass der Code möglichst nahe an der Realität ist. Dein Ansatz wird so nicht funktionieren, denn OOP funktioniert nicht zwingend sequentiell.

Bearbeitet 3. Juli 2012 von flashpixx

[Ne0Nebul0sa]

Die main-Methode ist der Einstiegspunkt für die JRE. Noch einmal als Anmerkung, kann eine Dame ohne Schachbrett existieren, also ist dies sinnvoll? Damit kannst Du die Frage auch selbst beantworten.

Rein theoretisch kann sie das. Aber es würde, für mich jedenfalls, keinen Sinn machen. Zumindest im Schachspiel ;-)

Insofern brauche ich ein Schachbrett (..und damit eine Klasse Brett?). Die muss ja nicht unbedingt optisch, also durch eine Gui dargestellt werden.

Wie lasse ich aber Schachbrett und Dame miteinader kommunizieren? Also wie weiß die Dame, wo sie steht, wenn nicht durch Koordinaten?

Ja Du kannst doch auch z.B. wenn der König im Schach stehen würde ihn nicht auf dieses Feld setzen

Okay. :-)

Das ist das gleiche Problem, wie bei Deinem Damenproblem, Du musst Dir überlegen durch welche Komponenten eine lineare Funktion repräsentiert ist

...

Durch einen Steigungseinheit und einer Schnittpunktkonstante, wenn ich die einzelnen Komponenten so nennen darf. Rein mathematisch ist mir das klar. Aber ich kann es einfach nicht auf Java anwenden :-(

und Du kannst dies z.B. sehr allgemein halten und wenn Du es sehr detailliert machen willst als eigene OOP Struktur entwerfen (theoretisch brauchst Du dies hier aber nicht, zur Übung wäre es aber sinnvoll). Sprich was muss eine lineare Funktion alles an Eigenschaften und Methoden haben, damit Du sie eben der mathematischen Repräsentation verwenden kannst.

In diesem Fall reicht mir die leichtere Variante. Die Aufwändige mache ich lieber später.

Aber ich kann es einfach nicht übertragen. Mir scheint einfach ein Teil des Gehirns zu fehlen, der dafür zunständig ist. Tut mir Leid :-(

Ich komme einfach damit nicht weiter.

Soweit klar. Zunächst wird eine Dame zufällig gesetzt.

Den Algorithmus würde ich wie folgt gestalten:

Es wird eine zweite Dame probeweise an eine Stelle gezogen (zufällig oder strukturiert? - ich würde allerdings die zufällige Variante bevorzugen, da somit alle Lösungen ausgegeben werden können, was bei der strukturierten nicht der Fall wäre) und dann geschaut, ob sie mit der ersten kollidiert. Ist dies nicht der Fall wird sie gesetzt. Danach wird eine dritte Dame an eine zufällige Position gezogen und es wird mit der ersten und der zweiten auf Kollision geprüft. ..und immer so weiter.. Falls eine Dame nicht an die Stelle passt wird sie auf eine neue Position gesetzt und die Prozedur beginnt von vorne (rekursiv ;-)).

Sollte es vorkommen, dass keine Position für die Dame verfügbar ist, wird die zuletzt gesetzte Dame wieder angewählt (die andere Dame wird erst einmal beiseite gelegt) und auf eine neue Position mit der Kollisionsfrage gesetzt. Dabei sollte diese natürlich nicht gleich der letzten Position sein. Dies geschiet solange, bis alle Damen erfolgreich gesetzt wurden.

Wie gesagt: Ich würde es in (for-/while-)-Schlangen machen. Aber wäre das dann OOP?

Was dann?

Das ist mir auch klar. Aber in diesem Fall ist es doch kombinierbar, oder nicht?

Ich brauche de fakto das Programm bis Donnerstag, und falls ich es nicht mit Dir rechtzeitig schaffe muss ich ein fertiges Programm von irgendwo nehmen. Das ist aber nicht mein eigentliches Ziel. Das wäre nur eine Notlösung :-/.

Sprich zwei Bretter mit, wie in diesem Fall, jew. zwei Damen ? Ich hatte das Beispiel mit 8 Damen auf einem 8x8 Brett und da fiel auf, dass die Damen in "Springer-Abständen" (dh. wie ein Springer "läuft") positioniert waren.

..oder was meinst Du konkret?

Nun gut :-)

Das habe ich in einem ersten Entwurf somit in die Klasse Dame gepackt. So in Ordnung?

Dann finde ich, dass sie zur Dame gehören sollte ;-)

Jop. Ähm.. Ich denke es ist ein Schachbrett :bimei. Sorry, aber die Frage setzte solch eine Antwort doch voraus

Stimmt, da die einzelnen linearen Funktionen das Feld ebenfalls "blockieren".

Mhnm okay. Das mag sein, und ich schätze deine Kritik, aber sei so lieb und zeige mir doch, wie es richtig geht, denn im Moment suche ich die Nadel im Heuhaufen und bemühe mich, aber tappe im Dunkeln :-(

Das erscheint mir logisch, aber nicht umsonst sagen mir viele, dass ich viel zu komplex denke und einfache Zusammenhänge unnötig beschreibe (in den Naturwissenschaften). Im Sprachlichen Gebiet bin ich i.d.R. deutlich präziser.

Ne0

[Ne0Nebul0sa]

Sorry für den Doppelpost, allerdings kann ich meinen letzten Post nicht mehr editieren.

Ich habe mit meinem bisherigen Wissensstand versucht einen neuen Anlauf zu starten für das nDamen Problem. Wo ich mir nicht sicher war, schlichtweg nicht weiter kam oder einfach kommentieren wollte habe ich Hinweise hinterlassen.

Teils habe ich deshalb auch Pseudocode benutzt (insgesamt liegt eine Art Mischcode (Pseudocode) vor).

Bestimmte Zeilen sind von ihrer Syntax nicht korrekt (zb. "this.xy();", obwohl die Methode nicht in der eigenen Klasse steht) oder enthalten kleinere Fehler. Mir geht es aber erst einmal nur um den Inhalt.

..Ich hoffe, dass Du mir nicht wieder meine Illusion von einem Erfolg nimmst, sonst wirds langsam sehr demotivierend für mich

Hier meine drei Klassen: Hauptprogramm, Dame, Brett:

Klasse Dame:

/**

 * @author 

 * @version 

 */

public class Damen

{

    // Bezugsobjekte

    Dame aktuelleDame;

    // Attribute


    // Konstruktor

    public Damen(Dame paktuelleDame)

    {

        zaktuelleDame = paktuelleDame;

    }


    // Dienste

    public boolean waagerecht()

    {

        if()

        {

            return true;

        }

        else

        {

            return false;

        }

    }


    public boolean senkrecht()

    {

        if()

        {

            return true;

        }

        else

        {

            return false;

        }

    }


    public boolean diagonal1()

    {

        if()

        {

            return true;

        }

        else

        {

            return false;

        }

    }


    public boolean diagonal2()

    {

        if()

        {

            return true;

        }

        else

        {

            return false;

        }

    }


    public Kollision()

    {

        boolean zKollision;


        if(this.waagerecht() || this.senkrecht() || this. diagonal1() || this.diagonal2() )

        {

           zKollision = true; 

        }

        else 

        {

           zKollision = false;

        }

    }


    public boolean vorherigeDame()

    {

        return zaktuelleDame;

    }

}

Klasse Hauptprogramm

import sum.werkzeuge.*;

/**

 * @author 

 * @version 

 */

public class Hauptprogramm

{

    // Bezugsobjekte

    Rechner hatRechner;

    // Attribute


    // Konstruktor

    public Hauptprogramm()

    {

        hatRechner = new Rechner();

    }


    // Dienste

    public static void main(String[] argc) {


     Brett x = new Brett(2);

     Brett y = new Brett(8);


     System.out.println("Ausgabe Brett 1:\n"+x);

     System.out.println("Ausgabe Brett 2:\n"+y);

    }


    public boolean alleDamengesetzt()

    {

        if() //Funktion DameSetzen n-mal ausgefuehrt? Variable uebergeben

        {

            return true;

        }

        else

        {

            return false;

        }

    }


    public void DameSetzen()

    {

        //aktuelle Dame setzen;

        naechsteDame = null; //Variable leeren , benoetigt?

    }


    public void Backtracking()

    {

        //fuer 8 Felder; Variable muss uebergeben werden

        ersteDame = new Dame(hatRechner.ganzeZufallszahl(1,8),hatRechner.ganzeZufallszahl(1,8));

        do

        {

            if(naechsteDame == null) //keine Dame ausgewaehlt -- pruefe ob nicht die vorherige Dame aufgerufen wurde

            {

                naechsteDame = new Dame(hatRechner.ganzeZufallszahl(1,8),hatRechner.ganzeZufallszahl(1,8));

            }

            this.Kollision();

            if(zKollision = true) //wie wird geprueft, ob die alle anderen Damen kollidieren?

            {

                if() //noch nichtalle Versuche gemacht

                {

                    naechsteDame = naechsteDame(hatRechner.ganzeZufallszahl(1,8),hatRechner.ganzeZufallszahl(1,8));    

                }

                else

                {

                    this.vorherigeDame(); //vorherige Dame aufrufen -- was passiert mit "naechsteDame"?

                    this.Backtracking(); //Prozedur von vorne beginnen und pruefen; rekursiv

                }

            } 

            else

            {

                Damesetzen();

            }

        }while(this.alleDamengesetzt());

    }



}

Klasse Brett:

/**

 * @author 

 * @version 

 */

public class Brett

{

    // Bezugsobjekte


    // Attribute


    // Konstruktor

    public Brett(int pFelder)

    {

        zFelder = pFelder;

    }


    // Dienste

    public void erzeugeSchachbrett()

    {

        int zCounter = 0;

        while(zCounter < zFelder)

        {

            //erzeuge ein neues Feld

            zCounter++;

        }

    }

}

[flashpixx]

Rein theoretisch kann sie das. Aber es würde, für mich jedenfalls, keinen Sinn machen. Zumindest im Schachspiel ;-). Insofern brauche ich ein Schachbrett (..und damit eine Klasse Brett?).

OOP soll möglichst nahe an die Realität angelehnt werden, also wäre eben eine Dame ohne Brett nicht möglich ( siehe http://de.wikipedia.org/wiki/Assoziation_(UML) ). Eine Klasse Brett ist sicherlich in Ordnung, man kann das natürlich auch allgemeiner machen.

Die muss ja nicht unbedingt optisch, also durch eine Gui dargestellt werden.

Wie lasse ich aber Schachbrett und Dame miteinader kommunizieren? Also wie weiß die Dame, wo sie steht, wenn nicht durch Koordinaten?

Du brauchst Koordinaten, aber Du musst 2 Fragen klären, wie stellst Du sicher, dass die Dame immer auf gültigen Koordinaten steht, d.h. also nicht außerhalb des Bretts und wer speichert die Koordinaten, das Brett oder die Dame oder irgendetwas anderes.

Durch einen Steigungseinheit und einer Schnittpunktkonstante, wenn ich die einzelnen Komponenten so nennen darf. Rein mathematisch ist mir das klar. Aber ich kann es einfach nicht auf Java anwenden :-(

Joah das ist doch so alles richtig. Naja was ist denn die Steigung und die Konstante, sind doch eigentlich nur Zahlen und diese Werten in eine bestimmte Form gebracht f(x) = m*x+b. x wollen wir flexibel einsetzen können

In diesem Fall reicht mir die leichtere Variante. Die Aufwändige mache ich lieber später.

Aber ich kann es einfach nicht übertragen. Mir scheint einfach ein Teil des Gehirns zu fehlen, der dafür zunständig ist. Tut mir Leid :-(

Naja, also um lineare Funktionen OOP-like zu verwenden reicht eine Klasse. Ich meine nur mal so als Gedanke, Du musst Dir ja irgendwie überlegen, wie Du die Steigung und die Konstante berechnest. Das ist Teil der linearen Funktion, d.h. Du kannst in Deine Klasse eben etwas Code setzen, das Dir z.B. aus zwei Punkten die Funktion aufstellt, d.h. Du gibst dann an die Methode einfach zwei Koordinatenpaare und bekommst ein Objekt "linearFunction" und dann kannst Du einfach "linearFunction.getValue(5)" machen und bekommst, dann den Wert für Y, wenn Du als X=5 einsetzt.

Wobei wir beim nächsten Punkt sind, wie Du auch die Koordinaten verwaltest !?

Den Algorithmus würde ich wie folgt gestalten:

Es wird eine zweite Dame probeweise an eine Stelle gezogen (zufällig oder strukturiert? - ich würde allerdings die zufällige Variante bevorzugen, da somit alle Lösungen ausgegeben werden können, was bei der strukturierten nicht der Fall wäre) und dann geschaut, ob sie mit der ersten kollidiert. Ist dies nicht der Fall wird sie gesetzt. Danach wird eine dritte Dame an eine zufällige Position gezogen und es wird mit der ersten und der zweiten auf Kollision geprüft. ..und immer so weiter.. Falls eine Dame nicht an die Stelle passt wird sie auf eine neue Position gesetzt und die Prozedur beginnt von vorne (rekursiv ;-)).

Ja das passt so. Es ist nicht rekursiv, sondern iterativ, soviel zum fachlichen. Das hier kannst Du als Struktogramm darstellen, aber es wird nachher nur eine einzelne Methode.

Sollte es vorkommen, dass keine Position für die Dame verfügbar ist, wird die zuletzt gesetzte Dame wieder angewählt (die andere Dame wird erst einmal beiseite gelegt) und auf eine neue Position mit der Kollisionsfrage gesetzt. Dabei sollte diese natürlich nicht gleich der letzten Position sein. Dies geschiet solange, bis alle Damen erfolgreich gesetzt wurden.

Dieser Fall ist erst beim Backtracking relevant. Wenn Du Brett mit NxN Feldern hast, dann kannst <= N Damen definitiv positionieren.

Wie gesagt: Ich würde es in (for-/while-)-Schlangen machen. Aber wäre das dann OOP?

Du brauchst schon Schleifen, aber diese haben im Hauptprogramm nichts zu suchen.

Das ist mir auch klar. Aber in diesem Fall ist es doch kombinierbar, oder nicht?

OOP und Rekursion sind zwei "Strukturansätze". OOP ist ein Programmierparadigma und Rekursion in diesem Fall eine Entwurfsstruktur für einen Algorithmus. Die Frage ist ähnlich zu der Frage ob ich einen Obstsalat mit Äpfeln machen kann.

Sprich zwei Bretter mit, wie in diesem Fall, jew. zwei Damen ? Ich hatte das Beispiel mit 8 Damen auf einem 8x8 Brett und da fiel auf, dass die Damen in "Springer-Abständen" (dh. wie ein Springer "läuft") positioniert waren.

Nein 2 Bretter beliebiger Größe mit n verschiedenen Damen, d.h. wenn ein Brett 8x8 stehen dort 8 Damen drauf, wenn es 200x200 eben 200 Damen

Das habe ich in einem ersten Entwurf somit in die Klasse Dame gepackt. So in Ordnung?

Dann finde ich, dass sie zur Dame gehören sollte ;-)

Ja, das passt

Jop. Ähm.. Ich denke es ist ein Schachbrett :bimei. Sorry, aber die Frage setzte solch eine Antwort doch voraus

*g* naja ich geb' mal den Hinweis darauf, aus was besteht denn das Schachbrett und wie beschreibe ich jede Position auf dem Brett, jetzt sollte es klingeln.....

Mhnm okay. Das mag sein, und ich schätze deine Kritik, aber sei so lieb und zeige mir doch, wie es richtig geht, denn im Moment suche ich die Nadel im Heuhaufen und bemühe mich, aber tappe im Dunkeln :-(

Naja aber Du zeigst doch gerade, dass Du langsam in die Richtung läuft, langsam aber es wird....

Das erscheint mir logisch, aber nicht umsonst sagen mir viele, dass ich viel zu komplex denke und einfache Zusammenhänge unnötig beschreibe (in den Naturwissenschaften).

Mein Tipp: Programmieren ist wie eine mathematische Funktion (naja rein formal liegt hinter einer Programmiersprache auch nur formale Logik). Beschränke Dich auf das Wesentliche. Hab Dir noch eine PN geschrieben

[Ne0Nebul0sa]

OOP soll möglichst nahe an die Realität angelehnt werden, also wäre eben eine Dame ohne Brett nicht möglich ( siehe http://de.wikipedia.org/wiki/Assoziation_(UML) ). Eine Klasse Brett ist sicherlich in Ordnung, man kann das natürlich auch allgemeiner machen.

Gut, das liegt nahe - Hatte ich ja bereits geschlussfolgert. Okay, inwiefern allgemeiner? Also das keine explizite Klasse Brett existiert, sondern eine Oberklasse, wie z.B. bei einer Ameise mit der Oberklasse Tier? - Das also hier lediglich beispielhaft die Klasse "Tier" existiere?

Du brauchst Koordinaten, aber Du musst 2 Fragen klären, wie stellst Du sicher, dass die Dame immer auf gültigen Koordinaten steht, d.h. also nicht außerhalb des Bretts und wer speichert die Koordinaten, das Brett oder die Dame oder irgendetwas anderes.

Indem ich von vornherein festlege, dass die Dame sich nur in den angegebenen Längen und Breiten bewegen darf und das Brett dementsprechend groß gestalte?

Die Koordinaten sollte die jeweilige Dame speichern, oder? Dann könnte sie beim Aufrufen direkt ihre Koordinaten mitgeben und jeweils angeben, ob eine Kollision existiert.

Joah das ist doch so alles richtig. Naja was ist denn die Steigung und die Konstante, sind doch eigentlich nur Zahlen und diese Werten in eine bestimmte Form gebracht f(x) = m*x+b. x wollen wir flexibel einsetzen können

Wunderbar. Das sollte ja mit der von Dir genannten Methode gehen.

Naja, also um lineare Funktionen OOP-like zu verwenden reicht eine Klasse. Ich meine nur mal so als Gedanke, Du musst Dir ja irgendwie überlegen, wie Du die Steigung und die Konstante berechnest. Das ist Teil der linearen Funktion, d.h. Du kannst in Deine Klasse eben etwas Code setzen, das Dir z.B. aus zwei Punkten die Funktion aufstellt, d.h. Du gibst dann an die Methode einfach zwei Koordinatenpaare und bekommst ein Objekt "linearFunction" und dann kannst Du einfach "linearFunction.getValue(5)" machen und bekommst, dann den Wert für Y, wenn Du als X=5 einsetzt.

Natürlich, logisch. Darauf hätte ich wirklich selber kommen können. Naja.. gut.. Haken wir das ab.

Mal schauen, ob ich das später auch programmieren kann

Ja das passt so. Es ist nicht rekursiv, sondern iterativ, soviel zum fachlichen. Das hier kannst Du als Struktogramm darstellen, aber es wird nachher nur eine einzelne Methode.

Wenn ich die Methode in der Methode selbst erneut aufrufe (s. erster Entwurf), dann ist es doch rekursiv, oder nicht?

Dieser Fall ist erst beim Backtracking relevant. Wenn Du Brett mit NxN Feldern hast, dann kannst <= N Damen definitiv positionieren.

Okay.

Du brauchst schon Schleifen, aber diese haben im Hauptprogramm nichts zu suchen.

Dann bin ich auf deinen Ansatz gespannt, obwohl ich in meinem Entwurf (immerhin) nur noch eine nutze :-).

OOP und Rekursion sind zwei "Strukturansätze". OOP ist ein Programmierparadigma und Rekursion in diesem Fall eine Entwurfsstruktur für einen Algorithmus. Die Frage ist ähnlich zu der Frage ob ich einen Obstsalat mit Äpfeln machen kann.

Ah okay. Für mich gehören Äpfel immer in einen Obstsalat, womit sich für mich auch die Frage nach den "Strukturansätzen" geklärt hätte - obwohl ich glaube, dass es nicht so einfach zu übertragen ist

Nein 2 Bretter beliebiger Größe mit n verschiedenen Damen, d.h. wenn ein Brett 8x8 stehen dort 8 Damen drauf, wenn es 200x200 eben 200 Damen

Ja, okay. Meintest Du, dass ich jetzt selbst das nDamen Problem nachstellen sollte mit Papier und Stift oder worauf möchtest Du hinaus?

*g* naja ich geb' mal den Hinweis darauf, aus was besteht denn das Schachbrett und wie beschreibe ich jede Position auf dem Brett, jetzt sollte es klingeln.....

Aus Nummern und Buchstaben, in Programmierfall nur Zahlen (Nummern). Diese geben die eindeutige Position der Dame an.

Naja aber Du zeigst doch gerade, dass Du langsam in die Richtung läuft, langsam aber es wird....

Schön :-)

Mein Tipp: Programmieren ist wie eine mathematische Funktion (naja rein formal liegt hinter einer Programmiersprache auch nur formale Logik). Beschränke Dich auf das Wesentliche. Hab Dir noch eine PN geschrieben

Na, wenn das (für mich) mal so einfach wäre. Dabei ist, Du wirst es kaum glauben, Mathe ein für mich eher gutes Fach (Naja, sagen wir Durchschnitt ).

Ja, danke, die PN habe ich gelesen.

[Gast runtimeterror]

Ohne jetzt alles in Frage stellen zu wollen (danke an euch Beide für's Nicht-aufgeben ) hätte ich beim Überfliegen der Diskussion doch ein paar grundsätzliche Anmerkungen:

Soll das Problem objektorientiert gelöst werden? Dann fehlt erstmal die statische Struktur (Klassendiagramm/-beschreibung). Ohne diese sollte die Algorithmierung nicht angegangen werden.

Erstmal super, dass du dir Gedanken über die Problemlösung gemacht hast! - Dann hat man eine gemeinsame Diskussionsgrundlage.

Mittlerweile ist allerdings der erste Code fertig, ohne dass zwischenzeitig ein vollständiger Pseudocode zu finden war.

Auch findet sich die immer wiederkehrende Frage, wie man eine diagonale Bedrohung erkennt. Das ist definitiv ein absolutes Detailproblem, welches ich erst angehen würde, wenn der grundsätzliche Ablauf geklärt ist.

Insbesondere ist hier das Top-Down-Verfahren zu empfehlen. Allein die Frage, ob du alle oder nur eine mögliche Lösung ausgeben willst sollte geklärt werden. Beschreibe erstmal umgangssprachlich, wie du das Problem lösen willst. Dann wird das im nächsten Schritt präzisiert. Dein so strukturierter Text geht dadurch nach und nach (und vor allem nachvollziehbar) in gültigen Pseudocode über. Den Schritt mit dem Struktogramm darfst du gerne weglassen - die sind (leider entgegen der Lehrkörpermeinung) für OOP unbrauchbar.

Das klingt jetzt zwar erstmal aufwändig, aber wenn ich mir die Dauer der Diskussion ansehe, denke ich dass es auch jetzt noch der richtige Weg ist. Ich würde gerne unterstützen, weiß aber gar nicht mehr an welchen Baustellen alles geschraubt werden muss. Oder um es mal fies zu formulieren: Wenn das oben beschriebene Vorgehen überflüssig sein sollte, dann sollte es ja jetzt ein leichtes sein einen implementierbaren Pseudocode runterzuschreiben

Dass die GUI eine völlig andere Baustelle ist, hat flashpixx ja schon geschrieben. Was auf der Konsole nicht funktioniert, klappt auch mit mehr Farbe nicht besser

Exkurs: Was das "Damen bedrohen sich diagonal"-Problem angeht: Als weiterführenden Hinweis zur "linearen Funktion": Welche Steigung hat eine Gerade die zwei Damen schneidet, die sich diagonal bedrohen? Formuliere das mal mathematisch und vereinfache das - es lohnt sich

Schöne Grüße,

Kai (der ein Programm für das Damenproblem rumliegen hat, für die ein Entwickler weggeschlossen gehört )

[flashpixx]

Ich habe das ganze einmal als Blogeintrag inkl Quellcode beschrieben Damenproblem | flashpixx.de

Vieles davon hat Ne0Nebul0sa in ähnlicher Weise umgesetzt. Ich habe in diesem Beispiel sowohl den klassischen Backtracking Ansatz programmiert, wie auch einen heuristischen / zufallsbasierten Ansatz gewählt. Man kann die Vorteile bei großen Brettern mit vielen Figuren erkennen. Die Theorie, dass dies genauso funktioniert, wie Backtracking bzw. in Kombination auch das richtige macht, möchte ich hier nicht im Detail ausführen, da dies dann doch recht komplex wird.

Ob man nun Top-Down oder Bottom-Up als Design Grundlage anwendet ist wohl jedem selbst überlassen. Ich denke Top-Down mit dem Bellmannprinzip kombiniert ist wohl die beste Wahl.

Bezüglich dem Struktogramm würde ich nicht zwingend sagen, dass sie "überflüssig" sind, denn die einzelne Methode kann als Struktogramm beschrieben werden, was durchaus sinnvoll sein kann. Ansonsten stimme ich damit überein, dass hier die Lehrer leider auch versuchen alte Diagrammemodellierungen in OOP zu pressen, was man häufig sieht, dann schief geht.

[Ne0Nebul0sa]

Hi Kai - ich hoffe, dass ich Dich so nennen darf, denn das macht die Diskussion ein wenig lockerer ;-),

Danke Dir für Deine einführenden Worte. Das Projekt sollte natürlich OOP umgesetzt werden.

Mittlerweile ist allerdings der erste Code fertig, ohne dass zwischenzeitig ein vollständiger Pseudocode zu finden war.

Ich hatte einen halbwegs vollständigen Peusocode gepostet und mein erster Entwurf war doch noch recht weit weg vom endgültigen Produkt.

Auch findet sich die immer wiederkehrende Frage, wie man eine diagonale Bedrohung erkennt. Das ist definitiv ein absolutes Detailproblem, welches ich erst angehen würde, wenn der grundsätzliche Ablauf geklärt ist.

Dank flashpixx und einer langen Nacht nun passé, bzw. abgehakt. Wichtige Gedanken und den Quellcode hat flashpixx ja veröffentlicht, sodass das Problem nun für jedermann lösbar sein sollte.

Allein die Frage, ob du alle oder nur eine mögliche Lösung ausgeben willst sollte geklärt werden.

Interessante Frage. Explizit gab es dafür keine Vorgabe [...](s. Nachtrag).

Nachtrag: Die bessere Formulierung wäre vielleicht: Eine aller möglichen Lösungen ausgeben zu lassen, denn die Positionen der Damen werden nicht statisch (fest) vergeben, sondern in jedem Programmlauf heuristisch generiert. Insofern trifft

nur eine mögliche Lösung ausgeben

zu.

Beschreibe erstmal umgangssprachlich, wie du das Problem lösen willst. Dann wird das im nächsten Schritt präzisiert. Dein so strukturierter Text geht dadurch nach und nach (und vor allem nachvollziehbar) in gültigen Pseudocode über. Den Schritt mit dem Struktogramm darfst du gerne weglassen - die sind (leider entgegen der Lehrkörpermeinung) für OOP unbrauchbar.

Exakt diesen Ablauf haben wir auch versucht und, soweit ich das beurteilen kann, erfolgreich gemeistert. Wie flashpixx schon sagte: Ein Struktogramm kann, muss aber nicht, hilfreich sein. Gerade für Anfänger halte ich das Lösungsprinzip für nicht schlecht, da viele damit eine Programmierungsgrundlage besitzen, da viele einfach drauf los programmieren wollen (huch, spreche ich da etwa aus Erfahrung ?).

Nichtdestoweniger sollte der generelle Ablauf und auch die objektorientierte Umsetzung mit UML-Diagrammen (sofern ich das richtig verstanden habe) umgesetzt werden (,was auch Bestandteil meines Informatikunterrichts ist).

Das klingt jetzt zwar erstmal aufwändig, aber wenn ich mir die Dauer der Diskussion ansehe, denke ich dass es auch jetzt noch der richtige Weg ist. Ich würde gerne unterstützen, weiß aber gar nicht mehr an welchen Baustellen alles geschraubt werden muss. Oder um es mal fies zu formulieren: Wenn das oben beschriebene Vorgehen überflüssig sein sollte, dann sollte es ja jetzt ein leichtes sein einen implementierbaren Pseudocode runterzuschreiben

Danke dafür. Allerdings kommt Deine Hilfe wohl "zu spät", denn mein Programm ist bereits, zumindest iterativ, umgesetzt worden. Flashpixx hat sogar beide Varianten.

Insofern: Danke für Deine Hilfe

Dass die GUI eine völlig andere Baustelle ist, hat flashpixx ja schon geschrieben. Was auf der Konsole nicht funktioniert, klappt auch mit mehr Farbe nicht besser

Das ist mir auch klar geworden. Leider, das kann ich im Nachhinein sagen, ist die grafische Umsetzung in meinem Unterricht meist der erste umgesetzte Bereich. Es wird leider erst danach mit dem eigentlichen Programmieren begonnen...

Exkurs: Was das "Damen bedrohen sich diagonal"-Problem angeht: Als weiterführenden Hinweis zur "linearen Funktion": Welche Steigung hat eine Gerade die zwei Damen schneidet, die sich diagonal bedrohen? Formuliere das mal mathematisch und vereinfache das - es lohnt sich

Danke, ja, Flashpixx hat den selben Ansatz gewählt

..und, in der Tat, es hat sich gelohnt!

Schöne Grüße,

Kai (der ein Programm für das Damenproblem rumliegen hat, für die ein Entwickler weggeschlossen gehört )

Danke, schöne Grüße zurück.

Wir beide haben ja jezt auch zwei Programme rumliegen. Wenn Du magst, poste doch mal Dein Programm, dann haben wir einen regelrechten Auswahlpool, der späteren Interessenten eine Betrachtung des Problems aus vielen Perspektiven bietet.

Nun zu Flashpixx: Gute Anmerkung, allerdings solltest Du erwähnen, dass mein Programm überhaupt erst durch eine lange Programmierungsnacht mit Dir entstehen konnte. Zudem hat es uns beide, aber vor allem Dich, viele Nerven gekostet.

Deshalb: Nochmals vielen Dank dafür - und lasse Dir dein Prestige ruhig zuschreiben, das hast Du in diesem Fall wirklich verdient!

Viele Grüße

Alex aka Ne0

Bearbeitet 7. Juli 2012 von Ne0Nebul0sa
s. Nachtrag

[Gast runtimeterror]

Hoi,

wie gewünscht meine (strukturiert programmierte) Lösung - der Code ist so hässlich wie schnell (findet alle 92 Lösungen in deutlich unter einer Sekunde):

public class EightQueens {


	static final long[] attackList;

	static int solutionCounter = 0;


	static {

		attackList = new long[64];


		int index1 = 0;

		for (int y1 = 0; y1 < 8; y1++) {

			for (int x1 = 0; x1 < 8; x1++, index1++) {

				int index2 = 0;

				for (int y2 = 0; y2 < 8; y2++) {

					for (int x2 = 0; x2 < 8; x2++, index2++) {

						if (!attacks(x1, y1, x2, y2)) continue;

						attackList[index1] |= 1L << index2;

					}

				}

			}

		}

	}


	public static void main(String... args) {

		placeQueen(0L, 0L, 0, 0);

	}


	private static final boolean attacks(int x1, int y1, int x2, int y2) {

		return (y1 == y2) || (x1 == x2) || (Math.abs(y2 - y1) == Math.abs(x2 - x1));

	}


	private static final void placeQueen(final long attacks, final long placing, final int startIndex, final int queenCount) {


		if (queenCount >= 8) {

			dumpBoard(placing);

			return;

		}


		for (int feldIndex = startIndex; feldIndex < 64; feldIndex++) {

			final long mask = 1L << feldIndex;

			// Wird die neue Dame von den bestehenden bedroht?

			if ((attacks & mask) != 0) continue;

			// Werden die bestehenden Damen von der neuen bedroht?

			if ((placing & attackList[feldIndex]) != 0) continue;

			// Mit platzierter Dame rekursiv weiter

			placeQueen(attacks | attackList[feldIndex], placing | mask, feldIndex + 1, queenCount + 1);

		}

	}


	private static final void dumpBoard(long placing) {

		System.out.println("Lösung #" + ++solutionCounter);

		int index = 0;

		for (int y = 0; y < 8; y++) {

			System.out.println("+---+---+---+---+---+---+---+---+");

			for (int x = 0; x < 8; x++, index++) {

				System.out.print((placing & (1L << index)) != 0 ? "| X " : "|   ");

			}

			System.out.println("|");

		}

		System.out.println("+---+---+---+---+---+---+---+---+");

		System.out.println();

	}


}

Viel Spaß damit,

Kai

PS: auf Wunsch erklär den auch

[flashpixx]

wie gewünscht meine (strukturiert programmierte) Lösung - der Code ist so hässlich wie schnell (findet alle 92 Lösungen in deutlich unter einer Sekunde):

Das ist das klassische Backtracking. Interessant ist dies, wenn das Brett sehr groß wird und mit vielen Damen besetzt werden soll, in diesem Fall würde ich dann von einem solchen Ansatz abraten, da er nicht mehr effizient berechnet werden kann.

[Gast runtimeterror]

Ich hatte ja auch keinen neuen Lösungsalgorithmus angekündigt. Das ist halt die klassische Backtracking-Lösung mit ein paar Optimierungen auf die übliche Feldgröße 8x8 (für größere Bretter sind andere Implementierungen sinnvoller).

Falls nur eine einzige Lösung gesucht ist, würde ich es mit einer simulierten Abkühlung versuchen.

Gruß,

Kai

[flashpixx]

Falls nur eine einzige Lösung gesucht ist, würde ich es mit einer simulierten Abkühlung versuchen.

Es spielt keien Rolle, welche Suchheuristik man verwendet, denn es gilt No-free-Lunch-Theoreme