Anfang des Damenproblems

[Beginner?]

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

Dann erkläre mal Zeile 49:

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

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

return true;

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

 

[kirax]

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

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

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

 

[Beginner94]

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

 

[icarus2]

Dann erkläre mal Zeile 49:

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

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

return true;

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

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

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

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

 

[Beginner94]

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

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

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

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

 

[kirax]

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

Ich geh das mal einzeln nacheinander durch

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

 

[Beginner94]

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

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

 

[Beginner94]

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

 

[Beginner94]

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

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

Hier ist der vollständige Code

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

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

 

[kirax]

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

 

[Beginner94]

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

 

[Beginner94]

Sry, ich meine zeile 35 und nicht 13

 

[goto94]

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

 

[kirax]

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

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

 

[Beginner94]

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

 

[goto94]

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

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

 

[kirax]

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

Nimm meinen Rat an und lerne Deutsch

 

[Beginner94]

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

 

[goto94]

Nimm meinen Rat an und lerne Deutsch

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

 

[nrg]

sagt wer oder was?

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

 

[goto94]

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

was denkt sich welcher teil?

 

[Andi_CH]

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

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

 

[nrg]

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

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

 

[Beginner94]

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

 

[nrg]

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

 

[Beginner94]

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

 

[goto94]

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

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

 

[nrg]

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

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

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

 

[goto94]

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

 

[Beginner94]

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

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

 

[goto94]

Andere Methoden

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

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

 

[kirax]

BT ist aber einfacher...

 

[Beginner94]

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