Basic Knight tour algorithm

Question

I am new to programming and wanted to solve Knights Tour problem as practice. So I gave it a go. I just learned the concept of recursion and was trying to use it to solve this problem for a 4X4 board. My code is:

public class Knight_tour{

private static boolean[][] chessboard = new boolean[4][4];


public static void Knight_tour(int x,int y) {


    if(((x < 0) || (x >= 4) || (y <0) || (y >= 4))){
       //do nothing
    }else{
        if(chessboard[x][y] == true){

           //if it is already visited, then, do nothing.
        }
        if(chessboard[x][y] != true) {
           //If it is not visited then find more points like this.
         chessboard[x][y]=true;
         System.out.println(x +" "+ y);

         Knight_tour(x+2, y+1);
         Knight_tour(x+1, y-2);
         Knight_tour(x+1, y+2);
         Knight_tour(x-1, y+2);
         Knight_tour(x-2, y-1);
         Knight_tour(x-2, y+1);
         Knight_tour(x-1, y-2);
         Knight_tour(x+2, y-1);  

        }
}        

}        

public static void main(String[] args){
           Knight_tour(0, 1);

    }
}

Now when I run this for I get the following output:

0 1

2 2

3 0

1 1

3 2

1 3

2 1

3 3

1 2

2 0

0 0

3 1

2 3

0 2

1 0

0 3

This gives me the box position on the board in the order that it is visited. MY questions are:

1. The point 0,0 goes to 3,1 and the second last point is 1,0 it goes from that to 0,3. Its not supposed to do that , I tried to figure this out but I could not. Can anyone please help me out with this and tell me how and why this is happening.

2. Can this be even solved like this? I mean I am sure there are a number of complicated and more complex algorithms for , but I just wanted something to practice recursion on.I learned the DFS algorithm, and kinda felt, this required the same thing .In case it cant be , can anyone point me in the right direction(A simple method to get this working, It does not need it to be optimized for speed or anything).

Thanks.

Answer 1

You have a few issues here:

1. Your program has a single representation of the visited squares, and you never reset these when you hit a dead-end and back-track.
2. You output every visited square as you go, regardless of whether or not you later find the path is a dead-end and you need to back out.
3. You do not identify when you have actually successfully completed a tour. The only reason your program stops is that some combination of failed tours mark every square as visited and then your program ends when no further moves are possible.

You need to go and think about your algorithm, and perhaps read up on other people's solutions.

Answer 2

Just because you print out a 0,0 then 3,1 doesn't mean that 3,1 was visited directly from 0,0. All you know is that 3,1 was visited at some time after 0,0.

Here's a modified version of your program which demonstrates this by printing out which square each square was visited from:

public class Knight_tour{

private static boolean[][] chessboard = new boolean[4][4];


public static void Knight_tour(int x,int y, int fromX, int fromY) {


    if(((x < 0) || (x >= 4) || (y <0) || (y >= 4))){
       //do nothing
    }else{
        if(chessboard[x][y] == true){

           //if it is already visited, then, do nothing.
        }
        if(chessboard[x][y] != true) {
           //If it is not visited then find more points like this.
         chessboard[x][y]=true;
         System.out.println(x +" "+ y + " (visited from " + fromX + ", " + fromY + ")");

         Knight_tour(x+2, y+1, x, y);
         Knight_tour(x+1, y-2, x, y);
         Knight_tour(x+1, y+2, x, y);
         Knight_tour(x-1, y+2, x, y);
         Knight_tour(x-2, y-1, x, y);
         Knight_tour(x-2, y+1, x, y);
         Knight_tour(x-1, y-2, x, y);
         Knight_tour(x+2, y-1, x, y);  

        }
}        

}        

public static void main(String[] args){
           Knight_tour(0, 1, 0, 1);

    }
}

Output:

0 1 (visited from 0, 1)
2 2 (visited from 0, 1)
3 0 (visited from 2, 2)
1 1 (visited from 3, 0)
3 2 (visited from 1, 1)
1 3 (visited from 3, 2)
2 1 (visited from 1, 3)
3 3 (visited from 2, 1)
1 2 (visited from 3, 3)
2 0 (visited from 1, 2)
0 0 (visited from 1, 2)
3 1 (visited from 1, 2)
2 3 (visited from 3, 1)
0 2 (visited from 2, 3)
1 0 (visited from 0, 2)
0 3 (visited from 1, 1)