Hey so i gotta code an algorithm for the Springerproblem (https://upload.wikimedia.org/wikipedia/commons/8/86/Knight%27s_tour.svg)
My code is currently endlessly running at a field of 6x6
We got a Junit class to test it. a field of 3x3 with the starting positions of x=1 and y=1 is working just fine.
public class Springerproblem {
private final int xDelta[] = {1,-1,1,-1,2,-2,2,-2};
private final int yDelta[] = {2,2,-2,-2,1,1,-1,-1};
/**
* Datenstruktur zum Abspeichern der Springerzuege
*/
private int[][] springerFeld;
private int n0;
/**
* Gibt ein zweidimensionales, quadratisches int-Array zurueck.
* n ist die Schachbrettbreite.
* Der Springer startet an Position (x,y) mit 0<=x,y<n.
* Auf den jeweiligen Postionen des Arrays sind die Positionen des
* Springers eingetragen. Die erste Position traegt die 1.
* Wenn sich das Problem nicht loesen laesst, so wird eine
* NoSolutionException geworfen.
*/
public int[][] springer(int n, int x, int y) throws NoSolutionException{
springerFeld = new int[n][n]; //erzeuge neues Spielfeld
this.n0 = n; // übernehme n
if (spring(x, y, 1)) { //rekursionsende wird im Stack als letztes abgebaut zugNr ist dabei 1 also die Startposition
return springerFeld;
}
else {
throw new NoSolutionException();
}
}
private boolean spring(int x, int y, int zugnummer) {
springerFeld[x][y] = zugnummer;//Zugnummer ist am Anfang 1
if(zugnummer == n0*n0) { //dann ist es am Zeil und teilt methode springer mit dass es fertig ist
return true;
}
for(int i = 0; i < xDelta.length; i++) {
int newX = x + xDelta[i]; //neue Position x
int newY = y + yDelta[i]; // neue Position y
if(loesbar(newX, newY, zugnummer+1)) { // wenn die nächste Position frei ist
springerFeld[newX][newY] = zugnummer+1; // füge sie zum weg hinzu
if(spring(newX, newY, zugnummer+1)) { //rekursionsaufruf mit der nächsten Position
return true;
}
// backtracking
}
}
springerFeld[x][y] = 0;
return false;
}
private boolean loesbar(int x, int y, int zugnummer) {
if(0 <= x && x < n0 && 0 <= y && y< n0 && springerFeld[x][y] == 0 && spring(x, y, zugnummer+1)) {
return true;
}
return false;
}
}
Also the method names etc. cannot be changed
