Java Springerproblem - Problem

evilf · 8. Juni 2012

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:

Code:

/**
 * <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:

Code:

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:

Code:

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:

Code:

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:

Code:

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");
  }
}

maxwell-cs · 8. Juni 2012

welchen zweck haben die vorkommnisse von

Code:

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

?

außerdem: variablen x, y, xx, yy zu nennen ist nicht sehr geschickt. x_source und x_destination z.b. wären schon verständlicher.

was genau ist die bedeutung der variable fehler?

evilf · 8. Juni 2012

Ich habe diesen Teil eingebaut, da es sonst Probleme beim Backtracking gab, wenn die Schleife ans allerletzte Feld gekommen ist.
Da ging das Programm nur bis etwa 42.

fehler wird hochgezählt, wenn durch Backtracking ein Schritt zurückgenommen wird, damit beim nächsten Durchlauf dieser Schritt übersprungen wird.

maxwell-cs · 8. Juni 2012

ich sehe dennoch nicht, warum das nötig ist und was es bezweckt.

generell ist der code imo aber auch nicht sehr gut verständlich und geschickt geschrieben. warum hast du das nicht einfach rekursiv implementiert? und jedes mal alle felder durchzugehen, um die erreichbaren felder zu finden, ist natürlich auch alles andere als schön...

edit: habs aus langeweile mal grad rekursiv in c++ programmiert. ist recht wenig code. kannst dir ja einige tipps aus der implementierung holen oder im notfall alles auf java portieren, mir ists gleich

wenn was nicht klar ist, kannst ja einfach nachfragen.

springer.h:

Code:

#ifndef SPRINGER_H_
#define SPRINGER_H_

#include <cstdlib>

class FieldIndex;

class Field {
public:
   Field(unsigned int w, unsigned int h);
   ~Field();
   const int width;
   const int height;
   bool status(FieldIndex idx);
   void setStatus(FieldIndex idx, bool val);
   bool isValid(FieldIndex idx);
private:
   bool **data;
};

class FieldIndex {
public:
   int column;
   int row;
   FieldIndex(int c, int r);
   FieldIndex();
   FieldIndex operator+(const FieldIndex &other);
};

class SpringerFinder{
public:
   FieldIndex new_relative_positions[8];
   Field field;
   const unsigned int width;
   const unsigned int height;
   FieldIndex *path;
   SpringerFinder(unsigned int w, unsigned int h);
   ~SpringerFinder();
   bool visit(FieldIndex idx, int remaining_slots);
   void printPath();
};

#endif /*SPRINGER_H_*/

springer.cpp:

Code:

#include <iostream>
#include "springer.h"

using namespace std;

Field::Field(unsigned int w, unsigned int h)
:
   width(w),
   height(h)
{
   data = new bool*[width];
   for (int i = 0; i < width; ++i){
      data[i] = new bool[height];
      for (int j = 0; j < height; ++j){
         data[i][j] = false;
      }
   }
}

Field::~Field(){
   for (int i = 0; i < width; ++i){
      delete[] data[i];
   }
   delete[] data;
}

bool Field::status(FieldIndex idx){
   return data[idx.column][idx.row];
}

void Field::setStatus(FieldIndex idx, bool val) {
   data[idx.column][idx.row] = val;
}

bool Field::isValid(FieldIndex idx){
   return ((idx.column >= 0) 
   && (idx.column < width)
   && (idx.row >= 0)
   && (idx.row < height)
   && (!status(idx)));
}

FieldIndex::FieldIndex(int c, int r) 
:
   column(c),
   row(r)
{}

FieldIndex::FieldIndex() 
{}

FieldIndex FieldIndex::operator+(const FieldIndex &other) {
   FieldIndex result;
   result.column = column + other.column;
   result.row = row + other.row;
   return result;
}

SpringerFinder::SpringerFinder(unsigned int w, unsigned int h)
:
   field(w, h),
   width(w),
   height(h)
{
   int counter = 0;
   for (int i = -2; i < 3; ++i) {
      if (i == 0) {
         continue;
      }
      int j = 3 - abs(i);
      new_relative_positions[counter++] = FieldIndex(i, -j);
      new_relative_positions[counter++] = FieldIndex(i, j);
   }
   path = new FieldIndex[width * height];
}

SpringerFinder::~SpringerFinder() {
   delete[] path;
}

bool SpringerFinder::visit(FieldIndex idx, int remaining_slots) {
   field.setStatus(idx, true);
   path[width * height - remaining_slots] = idx;
   if (remaining_slots == 1) {
      return true;
   }
   for (int i = 0; i < 8; ++i) {
      FieldIndex new_position = idx + new_relative_positions[i];
      if (!field.isValid(new_position)) {
         continue;
      }
      if (visit(new_position, remaining_slots - 1)) {
         return true;
      }
   }
   field.setStatus(idx, false);
   return false;
}

void SpringerFinder::printPath() {
   for (unsigned int i = 0; i < width * height; ++i){
      cout << i << ": " << path[i].column << " " << path[i].row << endl;
   }
}

int main() {
   int width = 8;
   int height = 8;
   SpringerFinder s(width, height);
   s.visit(FieldIndex(0, 0),  width * height);
   s.printPath();
   return 0;
}

Suche

Java Springerproblem - Problem

evilf

Cadet 4th Year

maxwell-cs

Lt. Junior Grade

evilf

Cadet 4th Year

maxwell-cs

Lt. Junior Grade

Ähnliche Themen