Knight's Tour: JAVA

The Knight's Tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving according to the rules of chess, must visit each square once.

There are several billion solutions to the problem, of which about 122,000,000 have the knight finishing on the same square on which it begins. When this occurs the tour is said to be closed.

Your assignment is to write a program that gives a solution to the Knight's Tour problem recursively.

The problem I'm having with my code is trying to backtrack. I made it so that once it finds a move that it can use, it places the number of the move that was used. For example, I have move 1 as move 2 left, 1 down. Before moving 2 left and 1 down, it makes the current spot into 1 to represent that move 1 was used to get to the next spot. I made it like this so that I can use those numbers to know how to get backwards if there are no more spots it can get to. I think the problem is with the 8th move when I'm trying to backtrack. It can't check to see if theres another path it can take since there are no more moves it can use. I tried to make it so that it goes back another step if it reaches this point but I'm getting a StackOverflowError and I don't know how to fix it. (Sorry if my code is really messy. I'm still pretty new and bad at this.)

public class Tour {

public static void main(String[] args){

Tour.tour();

for(int boardY = 0; boardY

for(int boardX = 0; boardX

System.out.print(board[boardX][boardY] + " ");

}

System.out.println();

System.out.println();

}

}

public static final int boardSize = 8;

public static final int empty = 0;

private static int board[][] = new int[boardSize][boardSize];

public static void tour(){

int moves = 0;

tour(0,0,moves,1);

}

private static void tour(int x, int y, int moves, int moveNum){

if (moves

if (board[x][y] == 0){

board[x][y] = moveNum;

moves++;

}

if((x + 2)

x = x + 2;

y = y + 1;

tour(x,y,moves,1);

}

else if(moves

move2(x,y,moves);

}

}

}

private static void move2(int x, int y, int moves){

if(moves

if((x + 1)

x = x + 1;

y = y + 2;

tour(x,y,moves,2);

}

else if(moves

move3(x,y,moves);

}

}

}

private static void move3(int x, int y, int moves){

if(moves

if((x - 1) >= 0 && (y + 2)

x = x - 1;

y = y + 2;

tour(x,y,moves,3);

}

else if(moves

move4(x,y,moves);

}

}

}

private static void move4(int x, int y, int moves){

if(moves

if((x - 2) >= 0 && (y + 1)

x = x - 2;

y = y + 1;

tour(x,y,moves,4);

}

else if(moves

move5(x,y,moves);

}

}

}

private static void move5(int x, int y, int moves){

if(moves

if((x - 2) >= 0 && (y - 1) >= 0 && board[x - 2][y - 1] == 0){

x = x - 2;

y = y - 1;

tour(x,y,moves,5);

}

else if(moves

move6(x,y,moves);

}

}

}

private static void move6(int x, int y, int moves){

if(moves

if((x - 1) >= 0 && (y - 2) >= 0 && board[x - 1][y - 2] == 0){

x = x - 1;

y = y - 2;

tour(x,y,moves,6);

}

else if(moves

move7(x,y,moves);

}

}

}

private static void move7(int x, int y, int moves){

if(moves

if((x + 1) = 0 && board[x + 1][y - 2] == 0){

x = x + 1;

y = y - 2;

tour(x,y,moves,7);

}

else if(moves

move8(x,y,moves);

}

}

}

private static void move8(int x, int y, int moves){

if(moves

if((x + 2) = 0 && board[x + 2][y - 1] == 0){

x = x + 2;

y = y - 1;

tour(x,y,moves,8);

}

else{

backTrack(x,y,moves);

}

}

}

private static void backTrack(int x, int y, int moves){

if(board[x][y] == 1){

board[x][y] = 0;

x = x - 2;

y = y - 1;

move2(x,y,moves-1);

}

else if(board[x][y] == 2){

board[x][y] = 0;

x = x - 1;

y = y - 2;

move3(x,y,moves-1);

}

else if(board[x][y] == 3){

board[x][y] = 0;

x = x + 1;

y = y - 2;

move4(x,y,moves-1);

}

else if(board[x][y] == 4){

board[x][y] = 0;

x = x + 2;

y = y - 1;

move5(x,y,moves-1);

}

else if(board[x][y] == 5){

board[x][y] = 0;

x = x + 2;

y = y + 1;

move6(x,y,moves-1);

}

else if(board[x][y] == 6){

board[x][y] = 0;

x = x + 1;

y = y + 2;

move7(x,y,moves-1);

}

else if(board[x][y] == 7){

board[x][y] = 0;

x = x - 1;

y = y + 2;

move8(x,y,moves-1);

}

else if(board[x][y] == 8){

board[x][y] = 0;

x = x - 2;

y = y + 1;

backTrack(x,y,moves-1);

}

}

}

Knight's Tour