Java solving Knights tour takes very long

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

Your algorithm is correct. But your loesbar() method should not call spring(...), else your algorithm spends twice the time each step.

Also the sequence of steps to try is not optimal for finding a single solution.
This question had the same issue: https://stackoverflow.com/questions/20783702/knights-tour-baktracking-lasts-too-long

Using a different sequence of steps finds a first solution more quickly:

    private final int xDelta[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
private final int yDelta[] = { 1, 2, 2, 1, -1, -2, -2, -1 };

An explanation is given here: https://stackoverflow.com/questions/21511683