Springer-Problem

[KSG9|sebastian]

folgende bedingung liefert wohl imer "true"

if(!eckPunkteErreicht() 
                    && feldExist(x, y, listeWege) 
                  && feldFrei(x, y, listeWege))

problem ist wohl auch, dass du ja nicht zwangsweise einen eckpunkt erreichen musst mit einem springer, sondern auch eins links/eins rechts davon landen kannst, dann macht er immer weiter.

Poste mal bitte den Code der methoden feldExists() und feldFrei()

 

[naufrage]

hmmm... aber dazu soll doch das back-tracking helfen, dass irgendwann doch alle vier ecken durchlaufen sind...?!?

habe schon versucht, die bedingung !eckPunkteErreicht() aus der zweiten if-Schleige herauszunehmen, das macht aber keinen unterschieed.

hier also der code von den Methoden und auch Danke, für deine Mühe

     public boolean eckPunkteErreicht()
     {
       boolean erreicht = false;
       if(schachbrett[0][0] == true && schachbrett[anzZeilen-1][anzSpalten-1] == true
          && schachbrett[0][anzSpalten-1] == true && schachbrett[anzZeilen-1][0] == true)
          erreicht = true;
          return erreicht;



      public boolean feldFrei(int x, int y, int index)
      {
        boolean frei = false;
        if(schachbrett[(x + springerZuegeX[index])][(y + springerZuegeY[index])] == false)
        frei = true;
        return frei;
      }



       public void geheFeldWeiter(int x, int y, int index)
       {
          posX = x + springerZuegeX[index];
          posY = y + springerZuegeY[index];
       }



       public boolean feldExist(int x, int y, int index)
       {
          boolean exist = false;
          if  ((x + springerZuegeX[index]) >= 0
            && (x + springerZuegeX[index]) < anzZeilen
            && (y + springerZuegeY[index]) >= 0
            && (y + springerZuegeY[index]) < anzSpalten)
            exist = true;
            return exist;
       }

 

[meez]

wär das Problem nicht eher etwas für Prolog?..

 

[KSG9|sebastian]

Ich denke mal du hast folgendes Problem:

Du kommst mit dem Springer auf Punkt(4/4)an
Dann kann der Springer in alle acht Richtungen weiter, d.h. der Springer geht auf Punkt(6/5). Dann fängt wie while-Schleife wieder an. Jetzt kommt das Problem: Die Bedinung ergibt wieder, dass 8 Felder theoretisch zu besetzen sind, unter anderem AUCH das Feld(4/4), also das worauf der Springer einen Zug früher war.

Also, um zu verhindern dass die Funktion da noch einmal aufgerufen wird musst du ne Bedingung einbauen wie z.B.

if(feldInListe(x, y)){
    //nix machen
}
else{
    //in liste eintragen und algo neu aufrufen
}


function feldInListe(int x, int y){
    for(int i=0;i<obj.size();i++){
        if(obj.get(0).x == x && obj.get(0).y == y){
            return true;
        }
    }
    return false;
}

Die Funktion feldInListe musst du halt noch n kleines bissl ändern, ich weis nicht mehr genau wie du die Werte in dem Object liste speicherst...!

 

[DrZoidberg]

Hier ist eine alternative Lösung.

public class Springer {
    final static int zeilen=8, spalten=8;
    
    static int[][] feld=new int[spalten][zeilen];
    static int zug_nr=0;
    
    final static int[][] steps={ { 1, 2, 2, 1, -1, -2, -2, -1 }, {2, 1, -1, -2, -2 , -1, 1, 2} };
    
    public static void main(String[] args) {
        findSolution(0,0);
    }
    
    public static void findSolution(int start_x, int start_y) {
        if(start_x>=spalten || start_x<0 || start_y>=zeilen || start_y<0) return;
        if(feld[start_x][start_y]!=0) return;
        zug_nr++;
        feld[start_x][start_y]=zug_nr;
        if(zug_nr==spalten*zeilen) printSolution();
        else {
            for(int i=0; i<steps[0].length; i++) {
                int x=start_x+steps[0][i];
                int y=start_y+steps[1][i];
                findSolution(x, y);
            }
        }
        zug_nr--;
        feld[start_x][start_y]=0;
    }
    
    public static void printSolution() {
        for(int y=0; y<zeilen; y++) {
            for(int x=0; x<spalten; x++) {
                if(feld[x][y]<10) System.out.print(" ");
                System.out.print(feld[x][y]+" ");
            }
            System.out.println();
        }
        System.out.println();
        System.out.println();
    }
}

 

[KSG9|sebastian]

if(zug_nr==spalten*zeilen) printSolution();

hust..das ist so nach dem motto "Höre auf wenn der Speicher voll ist". Aber das löst das Problem, dass manche Felder doppelt vorkommen nicht, oder irre ich mich? Ich hab nur kurz drüber gelesen..aber meiner Meinung nach können trotzdem noch Felder doppelt vorkommen und das Problem an deiner Lösung ist auch noch, dass es nicht sicher ist, dass alle Möglichkeiten abgedeckt werden!

 

[DrZoidberg]

if(zug_nr==spalten*zeilen) printSolution();

hust..das ist so nach dem motto "Höre auf wenn der Speicher voll ist".

Nein. Das ist nach dem Motto "Höre auf, wenn du sämtliche Felder des Schachbretts einmal angesprungen hast." Und das ist genau das was gesucht ist.
Die Variablen spalten und zeilen geben die Dimensionen des Schachbrettes an. In der Regel 8x8.
Beim Springer Problem geht es darum, jedes Feld genau ein mal anzuspringen. Und das heisst man muss genau 64 (also 8 x 8 ) Züge machen.

Aber das löst das Problem, dass manche Felder doppelt vorkommen nicht, oder irre ich mich? Ich hab nur kurz drüber gelesen..aber meiner Meinung nach können trotzdem noch Felder doppelt vorkommen und das Problem an deiner Lösung ist auch noch, dass es nicht sicher ist, dass alle Möglichkeiten abgedeckt werden!

Nein. Es können keine Felder doppelt vorkommen. Das Array in meinem Programm repräsentiert das Schachbrett. Deshalb ist es auch 8 x 8 groß.
Bei meiner Lösung werden mit Sicherheit sämtliche Möglichkeiten abgedeckt.

 

[KSG9|sebastian]

Ich zitiere mich mal

Du kommst mit dem Springer auf Punkt(4/4)an
Dann kann der Springer in alle acht Richtungen weiter, d.h. der Springer geht auf Punkt(6/5), zum Beispiel. Dann fängt deine Schleife an die Funktion wieder aufzurufen, mit allen nächste Möglichen Feldern. Und zu den Feldern gehört auch der Punkt(4/4).

Somit wird der Punkt(4/4) zum 2. Mal in dein Array geschrieben. Ich habe nichts gefunden dass verhindern würde dass sowas passiert, aber ich bin offen für ne Belehrung.

 

[KSG9|sebastian]

So, hier kommt mal meine Lösung.

public class Springer { 
    private final static int zeilen=8;
    private final static int spalten=8; 
    
    private static int[][] feld=new int[spalten][zeilen]; 
    private Vector positionen = new Vector();
    private int zug_nr=0; 
    
    final static int[][] schritte={ { 1, 2, 2, 1, -1, -2, -2, -1 }, {2, 1, -1, -2, -2 , -1, 1, 2} }; 
    
    public static void main(String[] args) { 
        felderArbeiten(0,0); 
    } 
    
    public static void felderArbeiten(int x, int y) { 

        if(_x >= spalten || x<0 || y >= zeilen || y<0) return; 
        if(feld[x][y]!=0) return; 
        if(feldInListe(x,y) return; //Diese Bedingung hier ist wichtig
        zug_nr++; 
        feld[x][y]=zug_nr; 

        if(zug_nr == spalten*zeilen) ausgabe(); 
        else { 
            for(int i=0; i<schritte[0].length; i++) { 
                int neues_x=x+schritte[0][i]; 
                int neues_y=y+schritte[1][i]; 
                neuePos(new Pos(x, y));
                felderArbeiten(neues_x, neues_y); 
            } 
        } 
        feld[x][y]=0; 
    } 
    
    public static void ausgabe() { 
        //ausgeben
    } 
    public static void neuePos(Pos p){
        positionen.add(p);
    }
    public void feldInListe(int x, int y){
        for(int i=0;i<positionen.size();i++){
            if( (((Pos)positionen.get(i)).x == x) && (((Pos)positionen.get(i)).y == y) ){
                return true;
            }
        }
        return false;
    }
}

 

[DrZoidberg]

Ich zitiere mich mal

Du kommst mit dem Springer auf Punkt(4/4)an
Dann kann der Springer in alle acht Richtungen weiter, d.h. der Springer geht auf Punkt(6/5), zum Beispiel. Dann fängt deine Schleife an die Funktion wieder aufzurufen, mit allen nächste Möglichen Feldern. Und zu den Feldern gehört auch der Punkt(4/4).

Somit wird der Punkt(4/4) zum 2. Mal in dein Array geschrieben. Ich habe nichts gefunden dass verhindern würde dass sowas passiert, aber ich bin offen für ne Belehrung.

Doch. Für den Fall ist schon gesorgt.

...
    public static void findSolution(int start_x, int start_y) {
        if(start_x>=spalten || start_x<0 || start_y>=zeilen || start_y<0) return;
        if(feld[start_x][start_y]!=0) return;  //Genau hier!
...

Deine geänderte Variante funktioniert übrigens nicht da du vergessen hast die Einträge wieder aus dem Vector zu entfernen. Ausserdem sind deine Erweiterungen völlig unnötig und bewirken nichts (ausser das Programm zu verlangsamen).

 

[KSG9|sebastian]

1) stimmt, die abfrage hab ich übersehen
2) warum sollte ich die einträge wieder löschen? ich hab es so verstanden, dass er die einträge zum schluss in nem vector haben will..

 

[Guest]

1) stimmt, die abfrage hab ich übersehen
2) warum sollte ich die einträge wieder löschen? ich hab es so verstanden, dass er die einträge zum schluss in nem vector haben will..

Weil er Back-tracking verwendet.
Falsche Lösungsansätze müssen wieder gelöscht werden.
Das geschieht in der Regel am Ende der rekursiven Methode.

 

[naufrage]

tut mir leid jungs, musste den algorithmus rausnehmen,
er kam in meinem seminar heute schon doppelt vor, wurde ziemlich dreist kopiert...
WER MACHT SOWAS????? und warum?

aber:
ich habe meinen zum laufen gebracht :lol:
die methode, das Feld als unbesetzt zu markieren muss ganz ans ende, vor beenden der methode, die rekursiv aufgerufen wird.

wenn ihr möchtet, schicke ich euch den kompletten code zu, dann sagt mir eure mail adressen!
es ist sehr interessant, was dabei rauskommt, alleine für ein 5*5 feld gibt es über 3000 loesungen :!:

gruß in die nacht

 

[Guest]

tut mir leid jungs, musste den algorithmus rausnehmen,
er kam in meinem seminar heute schon doppelt vor, wurde ziemlich dreist kopiert...
WER MACHT SOWAS????? und warum?

Welcher Algorithmus kam dort vor?
Meinen hatte ich doch erst vor ein paar Stunden gepostet.

Ist allerdings auch der Standardalgorithmus für dieses Problem
bzw. eine Abwandlung davon.

 

[Guest]

na, es war der, den ich ursprünglich gepostet hatte.