Springerproblem - Problem

[evilf]

Hey,

bin gerade dabei, für ein Schulprojekt das Springerproblem zu realisieren.
Mein Fehler ist, dass das Backtracking immer an einer bestimmten Stelle stehen bleibt (Schritt 57).
Könntet ihr bitte mal drüber schauen? Bin im Moment echt ratlos & Montag ist bereits Abgabe :/

Schon mal vielen Dank im Voraus

Hier die Klassen:

Stack:

/**
 * <p>Materialien zu den zentralen
 * Abiturpruefungen im Fach Informatik ab 2012 in 
 * Nordrhein-Westfalen.</p>
 * <p>Klasse Stack</p>
 * <p>Objekte der Klasse Stack (Keller, Stapel) verwalten beliebige
 * Objekte nach dem Last-In-First-Out-Prinzip, d.h. das zuletzt
 * abgelegte Objekt wird als erstes wieder entnommen.</p>
 * 
 * <p>NW-Arbeitsgruppe: Materialentwicklung zum Zentralabitur im Fach Informatik</p>
 * 
 * @version 2010-10-20
 */
public class Stack {
    private Node head;

    // Node
    private class Node {
        private Object content = null;
        private Node nextNode = null;

        public Node(Object pObject) {
            content = pObject;
            nextNode = null;
        }

        public void setNext(Node pNext) {
            nextNode = pNext;
        }

        public Node getNext() {
            return nextNode;
        }

        public Object getContent() {
            return content;
        }
    } // Ende Node

    // Stack
    /**
     * Ein leerer Stapel wird erzeugt.
     */   
    public Stack() { 
         head = null;
    }

    /**
     * Die Anfrage liefert den Wert true, wenn der Stapel 
     * keine Objekte enthaelt, sonst liefert sie den Wert false.
     * @return true, falls der Stapel leer ist, sonst false.
     */
    public boolean isEmpty() {
        return (head == null);
    }

    /**
     * Das Objekt pObject wird oben auf den Stapel gelegt. 
     * Falls pObject gleich null ist, bleibt der Stapel unveraendert.
     * @param pObject ist das einzufuegende Objekt.
     */
    public void push(Object pObject) {
        if (pObject != null) {
            Node lNode = new Node(pObject);
            lNode.setNext(head);
            head=lNode;
        }
    }

    /**
     * Das zuletzt eingefuegte Objekt wird von dem Stapel entfernt. 
     * Falls der Stapel leer ist, bleibt er unveraendert.
     */
    public void pop() {
        if (!isEmpty())
            head = head.getNext();
    }

    /**
     * Die Anfrage liefert das oberste Stapelobjekt. 
     * Der Stapel bleibt unveraendert. 
     * Falls der Stapel leer ist, wird null zurueck gegeben.
     * @return Inhaltsobjekt
     */     
    public Object top() {
        if (!this.isEmpty())
            return head.getContent();
        else
            return null;
    }

}

Feld:

public class Feld {

  private boolean besetzt;
  private boolean besucht;
  private boolean farbe;
  private int zeile;
  private int spalte;

  public Feld() {
    besetzt = false;
    besucht = false;
    zeile = 0;
    spalte = 0;
  }

  public Feld(int x, int y) {
    besetzt = false;
    besucht = false;
    zeile = x;
    spalte = y;
  }
  
  public void setSpringer(boolean b) {
    besetzt = b;
    besucht = true;
  }
  
  public void backtrack() {
    besucht = false;
  }
  
  public boolean isBesetzt() {
    return besetzt;
  }
  
  public boolean isBesucht() {
    return besucht;
  }
  
  public void setBesucht(boolean b) {
    besucht = b;
  }
  
  public int getX() {
    return zeile;
  }
  
  public int getY() {
    return spalte;
  }
}

Springer:

import java.awt.Dimension;

public class Springer {

  private int zeile;
  private int spalte;
  private Dimension position;

  public Springer() {
    zeile = 0;
    spalte = 0;
  }
  
  public Springer(int x, int y) {
    zeile = x;
    spalte = y;
  }
  
  public Springer(Dimension d) {
    position = d;
  }
  
  public void setX(int x) {
    zeile = x;
  }
  
  public void setY(int y) {
    spalte = y;
  }
  
  public void setPosition(Dimension d) {
    position = d;
  }
  
  public int getX() {
    return zeile;
  }
  
  public int getY() {
    return spalte;
  }
  
  public Dimension getPosition() {
    return position;
  }
}

Springerproblem:

public class Schachbrett {

  private int zeilen;
  private int spalten;
  private int größe;
  private Feld[][] felder;
  private Springer springer;
  private Stack zugliste = new Stack();
  private int fehler = 0;
  private int zugnummer = 1;
  private FeldGUI gui;

  public Schachbrett() {
    gui = new FeldGUI("mySpringerproblemX");
    zeilen = 8;
    spalten = 8;
    größe = 8;
    felder = new Feld[8][8];
    for (int i = 0; i < 8; i++) {
      for (int j = 0; j < 8; j++) {
        felder[i][j] = new Feld(i,j);
      }
    }
    springer = new Springer();
    felder[0][0].setBesucht(true);
    gui.showNumber(0,0,0);
    solve();
  }
  
  public Schachbrett(int n) {
    zeilen = n;
    spalten = n;
    größe = n;
    felder = new Feld[n][n];
  }
  
  private boolean jump() {
    int x = springer.getX();
    int y = springer.getY();
    for (int i = 0; i < zeilen; i++) {
      for (int j = 0; j < spalten; j++) {
        int xx = felder[i][j].getX();
        int yy = felder[i][j].getY();
        //int xx = x + felder[i][j].getX();
        //int yy = y + felder[i][j].getY();

        if (!felder[i][j].isBesucht()){


          if (x-xx==2 && y-yy==1 ||
              x-xx==2 && y-yy==-1 ||
              x-xx==1 && y-yy==2 ||
              x-xx==1 && y-yy==-2 ||
              x-xx==-1 && y-yy==2 ||
              x-xx==-1 && y-yy==-2 ||
              x-xx==-2 && y-yy==1 ||
              x-xx==-2 && y-yy==-1) {

            if (fehler > 0) {
              fehler--;
            } else {
              springer.setX(xx);
              springer.setY(yy);
              gui.showNumber(xx,yy,zugnummer);
              felder[i][j].setBesucht(true);
              System.out.println("x: "+x+ "  y: " +y +"  yy" +  yy + "  xx"+xx+ " i" +i +" j"+ j);
              zugliste.push(felder[i][j]);
              return true;
            }

          } else {
            if (xx == zeilen-1 && yy == spalten-1) {
              System.out.println("FUUUUUUUUUUUUUUUUUCK");
              zugnummer--;
              jumpBack();
            }
          }
        } /*else {
          if (xx == zeilen-1 && yy == spalten-1) {
            System.out.println("FUUUUUUUUUUUUUUUUUCK");
            zugnummer--;
            jumpBack();
          }
        }*/
      }
    }
    //jumpBack();
    return false;
  }

  private void jumpBack() {
    if(!zugliste.isEmpty())
    {
      ((Feld) zugliste.top()).setBesucht(false);
      int xx = ((Feld) zugliste.top()).getX();
      int yy = ((Feld) zugliste.top()).getY();
      gui.clearNumber(xx,yy);
      
      //if (xx == zeilen-1 && yy == spalten-1) {
      //  System.out.println("FUUUUUUUUUUUUUUUUUCK");
        //jumpBack();
      //}
      zugliste.pop();
      int x = ((Feld) zugliste.top()).getX();
      int y = ((Feld) zugliste.top()).getY();
      springer.setX(x);
      springer.setY(y);
      fehler++;
      System.out.println("FEHLER!!! " + fehler);
    }
  }

  public void solve() {
    zugnummer = 1;
    while (zugnummer < zeilen*spalten) {
      System.out.println(zugnummer);
      if (!jump()) {
        jumpBack();
        zugnummer--;
      } else {
        zugnummer++;
      }

      if(!zugliste.isEmpty())
      System.out.println( "x: "+( (Feld)zugliste.top()).getX()+ "  y: "+((Feld)zugliste.top()).getY() );
    }
  }
  
  public static void main(String [] args) {
    new Schachbrett();
  }
}

FeldGUI:

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.event.*;

public class FeldGUI extends JFrame implements ComponentListener {

  private JPanel schachFeld;
  private int spalte = 8;
  private int zeile = 8;
  private ImageIcon icon;

  JButton[][] brett = new JButton[spalte][zeile];
  int spaltePosStart = 220;
  int zeilePosStart = 50;
  int spaltePos = spaltePosStart;
  int zeilePos = zeilePosStart;
  boolean color = false;

  private Color white = Color.white;
  private Color black = Color.black;

  public FeldGUI (String title) {
    super (title);
    setDefaultCloseOperation(WindowConstants.DISPOSE_ON_CLOSE);
    int frameWidth = 1000; 
    int frameHeight = 700;
    setSize(frameWidth, frameHeight);
    Dimension d = Toolkit.getDefaultToolkit().getScreenSize();
    int x = (d.width - getSize().width) / 2;
    int y = (d.height - getSize().height) / 2;
    setLocation(x, y);
    Container cp = getContentPane();
    cp.setLayout(null);

    setResizable(true);
    setVisible(true);

    schachFeld = new JPanel();

    for (int i = 0; i < spalte; i++) {
      for (int j = 0; j < zeile; j++) {
        brett[i][j] = new JButton();

        if (color) {
          brett[i][j].setBackground(black);
          brett[i][j].setForeground(white);
        }
        else {
          brett[i][j].setBackground(white);
          brett[i][j].setForeground(black);
        }
        color = !color;
        brett[i][j].setSize(70,70);

        brett[i][j].setLocation(spaltePos,zeilePos);

        brett[i][j].setVisible(true);
        brett[i][j].setOpaque(true);
        zeilePos += 71;
        cp.add(brett[i][j]);
      }
      
      color = !color;
      spaltePos += 71;
      zeilePos = zeilePosStart;
      cp.repaint();
      
    }
    spaltePos = spaltePosStart;
    cp.addComponentListener(this);
  }
  
  public void componentHidden(ComponentEvent e) {

  }

  public void componentMoved(ComponentEvent e) {

  }

  public void componentResized(ComponentEvent e) {
    zeilePos = this.getHeight()/14;
    spaltePos = this.getWidth()*2/9;

    for (int i = 0; i < spalte; i++) {
      for (int j = 0; j < zeile; j++) {

        if (this.getHeight() < this.getWidth()) {
          brett[i][j].setSize(this.getHeight()/10,this.getHeight()/10);
        } else {
          brett[i][j].setSize(this.getWidth()/10,this.getWidth()/10);
        }
        
        brett[i][j].setLocation(spaltePos,zeilePos);
        zeilePos = zeilePos + brett[0][0].getHeight() + 1;

      }
      color = !color;
      spaltePos = spaltePos + brett[0][0].getWidth() + 1;
      zeilePos = this.getHeight()/14;
      repaint();

    }
    spaltePos = this.getWidth()*2/9;
  }

  public void componentShown(ComponentEvent e) {

  }
  
  public void showNumber(int x, int y, int zug) {
    brett[x][y].setText(""+zug);
  }
  
  public void clearNumber(int x, int y) {
    brett[x][y].setText("");
  }

  public static void main(String[] args) {
    new FeldGUI("FeldGUI");
  }
}

 

[Fant]

Dein Programm ist nicht gerade vorteilhaft aufgebaut, aber zunächst sollten wir uns darum kümmern, dass dein Backtracking-Algorithmus funktioniert...

Das Problem ist, dass du immer nur einen Schritt zurück gehst und dann den gleichen Schritt wieder gehst. Du solltest von jeder Position aus alle möglichen weiteren Wege überprüfen. Wenn keiner der Wege zum Ziel führt, dann gehst du wieder einen Schritt zurück. Das läuft auf rekursive Aufrufe hinaus. Mit einer einfachen while-Schleife wird das so nicht klappen.

Ich würde dir außerdem raten die Testdurchläufe mit einem 5x5- oder einem 6x6-Feld zu machen. 8x8 dauert mit Backtracking teilweise schon Stunden, wenn nicht gar Tage, bis eine Lösung gefunden wurde.