Anfang des Damenproblems

B

Beginner?

Gast
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:
Code:
            if(Math.abs( f[i]-f[k] ) == k - i | f[i] == f[k]){

Da du alle anderen Zeilen außer diese kommentiert hast und
Code:
return true;
zu kommentieren relativ sinnlos ist, denke ich, dass sie nicht mal von dir stammt ^^
 

kirax

Bekanntes Mitglied
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.
 
B

Beginner94

Gast
Euer battle ist noch etwas zu hoch für mich^^
mein kompliment an beide lösungen ist, dass ich sie nicht verstehe :D
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

Top Contributor
Dann erkläre mal Zeile 49:
Code:
            if(Math.abs( f[i]-f[k] ) == k - i | f[i] == f[k]){

Da du alle anderen Zeilen außer diese kommentiert hast und
Code:
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?
 
B

Beginner94

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

Java:
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

Bekanntes Mitglied
"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 :)
Java:
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 );
        }
    }
 
B

Beginner94

Gast
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 :D
 
B

Beginner94

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

Beginner94

Gast
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
Java:
if( istBedroht(zeile, spalte) == true )

Hier ist der vollständige Code

Java:
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

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

Beginner94

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

Beginner94

Gast
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!
 
G

goto94

Gast
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 :p nimm den rat an und lerne html
 
B

Beginner94

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

Andi_CH

Top Contributor
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.
 
B

Beginner94

Gast
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

Top Contributor
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)
 
Zuletzt bearbeitet:
B

Beginner94

Gast
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?
 
G

goto94

Gast
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

Top Contributor
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
 
G

goto94

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

Beginner94

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

goto94

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

Beginner94

Gast
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?
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Konstruktor-Aufruf im Konstruktor, aber nicht am Anfang? Java Basics - Anfänger-Themen 4
K Wie kann ich ein Element an den Anfang setzten ? Java Basics - Anfänger-Themen 1
berserkerdq2 Warum macht man in IJVM am Anfang Bipush 0? Java Basics - Anfänger-Themen 1
M Java Anfang Java Basics - Anfänger-Themen 13
L Anfang von Programmtext Java Basics - Anfänger-Themen 11
T Netzwerkprogrammierung Anfang Java Basics - Anfänger-Themen 9
J am Anfang eines String ein Leerzeichen löschen Java Basics - Anfänger-Themen 6
N Anfang eine Array Schleife finden Java Basics - Anfänger-Themen 18
F Interface JTextField am Anfang unsichtbar o_o Java Basics - Anfänger-Themen 3
H Tetris anfang Java Basics - Anfänger-Themen 6
V Bin eigentlich noch VOR dem Anfang .... Java Basics - Anfänger-Themen 9
X Best Practice SUCHE ein gutes Javabuch! (kein Anfang von 0) Java Basics - Anfänger-Themen 5
D ListIterator auf Anfang zurücksetzen Java Basics - Anfänger-Themen 2
S Video2Brain Java7 gut fürn Anfang? Java Basics - Anfänger-Themen 8
M Komplett anfang in Java Java Basics - Anfänger-Themen 9
O Erste Schritte Aller Anfang ist schwer ! Bitte um Unterstützung Java Basics - Anfänger-Themen 6
M Aller anfang ist schwer :D Hilfe! Java Basics - Anfänger-Themen 18
S Erste Schritte Von Anfang an ! Java Basics - Anfänger-Themen 6
J Variablen Letzte berechnete variable am anfang Ausgeben ? Java Basics - Anfänger-Themen 4
H Problem beim Anfang von Java (Java Editor) Java Basics - Anfänger-Themen 2
E Listen vereinen, wenn Elemente am Anfang/Ende übereinstimmen Java Basics - Anfänger-Themen 2
J Bufferedreader nich von anfang an. Java Basics - Anfänger-Themen 14
Z TableCellRenderer anfang so richtig? Java Basics - Anfänger-Themen 13
M JTextPane an den Anfang springen Java Basics - Anfänger-Themen 8
Povlsen84 String - Zeichen am Anfang entfernen Java Basics - Anfänger-Themen 11
P Ein Programm vorzeitig beenden und wieder an den Anfang springen. Java Basics - Anfänger-Themen 7
K Befehl um am Anfang einer Methode zu kommen? Java Basics - Anfänger-Themen 9
A Filereader - An den Anfang des File springen Java Basics - Anfänger-Themen 2
G Einfacher Anfang mit Hibernate Java Basics - Anfänger-Themen 4
P Buffered Reader an Anfang setzen Java Basics - Anfänger-Themen 4
A Aus switch case an den Anfang? Java Basics - Anfänger-Themen 7
B so ziemlich am anfang Java Basics - Anfänger-Themen 11
G datei -> zeile am anfang einfügen/löschen Java Basics - Anfänger-Themen 4
K Ganz am Anfang - Java + Datenbank Java Basics - Anfänger-Themen 6
G Aller anfang is schwer. Java Basics - Anfänger-Themen 4
C Java-Anfang main void public? Java Basics - Anfänger-Themen 5
T Grundlagen ganz am Anfang Java Basics - Anfänger-Themen 12
R An den Anfang einer While-Schleife springen Java Basics - Anfänger-Themen 2
D wieso ist die combobox nicht von anfang an aktiviert? Java Basics - Anfänger-Themen 4
A Iterator auf anfang setzen Java Basics - Anfänger-Themen 5
G in txt file text nicht am ende sondern am anfang anhängen! Java Basics - Anfänger-Themen 12
A ganz am Anfang Java Basics - Anfänger-Themen 15
K Zum Anfang einer ArrayList springen Java Basics - Anfänger-Themen 4
J TextArea auf Anfang setzen Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Neue Themen


Oben