CODEWITHSUNDEEP
javaknights-tour
rxbxi
rxbxi

Reputation: 15

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

Upvotes: 0

Views: 161

Answers (1)

tkruse
tkruse

Reputation: 10685

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: Knights tour backtracking 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: Knight's tour backtrack implementation choosing the step array

Upvotes: 1

Related Questions