Hallo zusammen,
ich habe ein kleines Problem mit meiner Implementierung des Algorithmus. Mein Algorithmus scheint für n,m = 5 zu funktionieren aber nicht für n,m = 6 geschweige denn darüber. Irgendwie bricht der Algorithmus nicht ab, und ich weiß nicht warum? Wenn ich mir das schrittweise debugge scheint alles so zu laufe, wie ich mir das vorstelle.
ich habe ein kleines Problem mit meiner Implementierung des Algorithmus. Mein Algorithmus scheint für n,m = 5 zu funktionieren aber nicht für n,m = 6 geschweige denn darüber. Irgendwie bricht der Algorithmus nicht ab, und ich weiß nicht warum? Wenn ich mir das schrittweise debugge scheint alles so zu laufe, wie ich mir das vorstelle.
Java:
public class SpringerTour
{
private int n,m;
private Position[] loesung;
private Position[] moeglZuege = {new Position (2,1),new Position (-2,1),
new Position (2,-1),new Position (-2,-1),new Position (1,2),
new Position (-1,2),new Position (1,-2),new Position (-1,-2),};
public SpringerTour(int n, int m){
this.n=n;this.m=m;
loesung=new Position [n*m];
loesung[0] = new Position(0,0);
}
public void behandleKnoten(){
behandleKnoten(0);
}
private void behandleKnoten(int ebene){
// wenn ich alle Felder besucht habe
if (ebene == n*m-1){
druckeLoesung();
}
else{
// für alle möglichen Züge
for(int j = 0; j<8;j++){
//bestimme die neue Position
Position neuePos = loesung[ebene].add(moeglZuege[j]);
// ist die neue Position zulaessig
if(pruefe(neuePos,loesung)){
// dann fuege sie der loesung hinzu und gehe eine Ebene weiter
loesung[ebene+1]=neuePos;
behandleKnoten(ebene+1);
}
}
// sollte kein Zug möglich sein von dieser Ebene, so entferne die Position aus der Loesung
loesung[ebene]=null;
}
}
private boolean pruefe(Position neuePos, Position[] a){
//schaue, ob die Koordinaten der neuen Position aufs Brett passen
if(neuePos.getX()>=0 && neuePos.getY()>=0 && neuePos.getX()<m && neuePos.getY()<n){
//schaue, ob die Koordinaten der neuen Position schon in der Loesung vorkommen
if(!Position.contains(neuePos,a)){
return true;
}
}
return false;
}
public void druckeLoesung(){
for (int i = 0 ; i<loesung.length;i++){
if(loesung[i]!=null){
System.out.println(loesung[i].toString());
}
else{
System.out.println("null");
}
}
}
public static void main(String [] argv) {
SpringerTour tour = new SpringerTour(5,5);
tour.behandleKnoten();
}
}
Java:
public class Position
{
// Instanzvariablen - ersetzen Sie das folgende Beispiel mit Ihren Variablen
private int x;
private int y;
private boolean visited;
/**
* Konstruktor für Objekte der Klasse Position
*/
public Position(int x ,int y)
{
// Instanzvariable initialisieren
this.x=x;this.y=y;
visited = false;
}
public void setPos(int x, int y)
{
// tragen Sie hier den Code ein
this.x=x;this.y=y;
}
public Position add(int dx, int dy){
int newx = x+dx;int newy=y+dy;
return new Position (newx,newy);
}
public Position add(Position zug){
int newx = x+zug.x;int newy=y+zug.y;
return new Position (newx,newy);
}
public void setVisited(boolean visited){
this.visited = visited;
}
public int[] getPos(){
int[] pos = new int[2];
pos[0] = x;
pos[1] = y;
return pos;
}
public boolean getVisited(){
return this.visited;
}
public boolean equals(Position other){
return other.getX() == this.x && other.getY() == this.y;
}
public String toString(){
return "("+ x +", " +y+", " +visited+ ")";
}
public static boolean contains(Position p, Position[] a){
for (int i = 0;i<a.length;i++){
if(a[i]!=null)
if (a[i].equals(p)) return true;
}
return false;
}
//Start GetterSetterExtension Source Code
/**GET Method Propertie x*/
public int getX(){
return this.x;
}//end method getX
//End GetterSetterExtension Source Code
//!
//Start GetterSetterExtension Source Code
/**GET Method Propertie y*/
public int getY(){
return this.y;
}//end method getY
//End GetterSetterExtension Source Code
//!
}
