Need of backtracking in Knight’s tour

Question

Why we need backtracking for The Knight’s tour problem? Can we do it by using only recursion? i have tried to do it but it give wrong answer and i am not able to figure out where code or logic goes wrong.

import java.util.*;
public class Solution {

    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int[][] ans=new int[8][8];
        for(int d=0;d<8;d++){
            for(int e=0;e<8;e++){
                ans[d][e]=-1;
            }
        }
        int[] x={2,1,-2,1,-1,-2,-1,2};
        int[] y={1,2,1,-2,-2,-1,2,-1};
        func(x,y,ans,7,7,1);
    }

    public static void func(int[] x,int[] y,int[][] ans,int i,int j,int count){
        if(count==64){
            for(int d=0;d<8;d++){
                for(int e=0;e<8;e++){
                    System.out.print(ans[d][e]+" ");
                }
                System.out.println();
            }
        }
        if(ans[i][j]!=-1){
            return;
        }
        else{
            ans[i][j]=count;
            for(int u=0;u<8;u++){
                if(i+x[u]>=0 && i+x[u]< 8 && j+y[u]>=0 && j+y[u]<8){
                    func(x,y,ans,i+x[u],j+y[u],count+1);
                }
            }
        }
        return;
    }
}

Answer 1

The need for back-tracking in the knights tour problem is critical. The fact that you have not implemented your back-tracking in your code is the main reason why it does not work.

To fix it you must at least clear the position at the end of your method. I.e when you do ans[i][j] = count you must balance that with a ans[i][j] = -1 to clear that square - you are not doing this.

That is not the only problem with your code but it is the main one.

Alternatives to back-tracking exist. You can create a new board at ever recursion level which is a copy of the current board but that is generally considered wasteful of memory.

Here's the code I ended up with:

// The board size.
private static final int SIZE = 8;
// Contents of board squares when empty.
private static final int EMPTY = -1;
// The 8 possible x,y moves for the knight.
private static final int[] x = {2, 1, -2, 1, -1, -2, -1, 2};
private static final int[] y = {1, 2, 1, -2, -2, -1, 2, -1};

public static void printBoard(int[][] board) {
    // Print out the board.
    for (int d = 0; d < SIZE; d++) {
        for (int e = 0; e < SIZE; e++) {
            System.out.print(board[d][e] + " ");
        }
        System.out.println();
    }

}

public static boolean knightsMove(int[][] board, int i, int j, int count) {
    boolean finished = false;
    // Only step onto empty squares that are on the board.
    if (i >= 0 && i < SIZE && j >= 0 && j < SIZE && board[i][j] == EMPTY) {
        // Mark my route.
        board[i][j] = count;
        // Count up.
        count += 1;
        // Are we done?
        if (count > SIZE * SIZE) {
            System.out.println("=== Solution ===");
            // Print the solution.
            printBoard(board);
            // Finished now.
            return true;
        }
        if (count == SIZE * SIZE) {
            // Nearly there - print something to show progress.
            System.out.println("=== Try === (" + i + "," + j + ")=" + count);
            // Print the current state.
            printBoard(board);
        }
        // Look around to try all moves from here.
        for (int u = 0; u < x.length && !finished; u++) {
            // Try the next place.
            finished = knightsMove(board, i + x[u], j + y[u], count);
        }
        // Clear my trail - you missed this.
        board[i][j] = EMPTY;
    } else {
        // Cannot go there.
        return false;
    }
    return finished;
}

public static void knightsMove() {
    int[][] board = new int[SIZE][SIZE];
    // Clear to EMPTY.
    for (int d = 0; d < board.length; d++) {
        for (int e = 0; e < board[d].length; e++) {
            board[d][e] = EMPTY;
        }
    }
    // Start at (7,7) with count 1.
    knightsMove(board, 7, 7, 1);
}

Be patient - it takes a long time to complete - as you would expect. On my PC it takes about 20 minutes to get to:

=== Solution ===
29 42 51 60 27 22 17 24 
50 59 28 41 52 25 20 15 
43 30 61 26 21 16 23 18 
62 49 58 53 40 19 14 7 
57 44 31 48 33 8 3 10 
36 63 34 39 54 11 6 13 
45 56 37 32 47 2 9 4 
64 35 46 55 38 5 12 1

I made the following changes:

1. Added comments - you should always comment your code.
2. Made your x and y arrays static - they do not need to be parameters.
3. Made all of the checks (on board AND empty) in one place.
4. Print the board on near-misses, just to keep you entertained.
5. Used a static final EMPTY to indicate empty.
6. Return a boolean result when finished to stop the search there.
7. Added backtracking.
8. Used better names such as board and knightsMove.
9. Used constant SIZE for board size.
10. Probably some minor tweaks.

Please do not use this code for your homework - you will learn much more by doing this yourself and understanding why each part works.

Answer 2

Recursion is when a function/method calls itself. Your func method calls itself, therefore your program uses recursion. (BTW: identifiers should be informative. Calling a function function says nothing; tour would be better).

Backtracking is when you explore a branching problem by trying one branch after the other, and checking the next branch only once you finish with the current one. Your program does that, therefore it is using backtracking.

Backtracking can also be implemented with a stack and a loop, like so:

 State initialState = new State(); // empty board, no moves
 Stack<State> stack = new Stack<State>();
 stack.add(initialState);
 while ( ! stack.isEmpty()) {
      State current = stack.pop();
      for (State next : current.getSuccesorStates()) {
           if (next.isLegal()) {
                 stack.add(next);
           }
      }
 }

This does not use recursion. However, it is more frequent to do this by recursion (which uses the program stack), as in your code.

So: your problem requires backtracking to solve it. It does not require recursion, although you are using it.

Extra credit: your code fails because you should un-mark cells when you are done visiting them. That way, when you try the next branch (which does not jump there), the cell is free to jump on. See the //MISSING annotation.

    if(ans[i][j]!=-1){
        return;
    }
    else{
        ans[i][j]=count;
        for(int u=0;u<8;u++){
            if(i+x[u]>=0 && i+x[u]< 8 && j+y[u]>=0 && j+y[u]<8){
                func(x,y,ans,i+x[u],j+y[u],count+1);
            }
        }
    }
    // MISSING: un-mark last marking, so that other branches can be explored
    ans[i][j]=-1
    return;