I am programming a solution to the Knights Tour problem using a heuristic to evaluate potential moves, and choose the "most difficult" one. I run into a problem where it makes up to the fourth move and then will not move forward or backward to a diffent move. The farthest it gets is:
1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 2 -1 -1 -1
-1 -1 -1 -1 4
-1 -1 3 -1 -1
I am working on a 5 x 5 board for now, before ramping up to an 8 x 8 ultimately. I just wanted to see it work on a small scale first. I know there are valid moves, I am just unsure if its the heuristic comparison that is going wrong, or if it is something else entirely that I am not seeing.
package csne2;
import java.util.Scanner;
public class KnightsTour
{
private final static int BOARD_LENGTH = 5; //The length of the board
private final static int MAX_MOVES = BOARD_LENGTH * BOARD_LENGTH;
private static int board[][]; //The simulated board
private static int[][] hueristic = new int[][]
{
{2, 3, 4, 3, 2},
{3, 4, 6, 4, 3},
{4, 6, 8, 6, 4},
{3, 4, 6, 4, 3},
{2, 3, 4, 3, 2}
};
//List of possible moves for the knight
private final static int xMove[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
private final static int yMove[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
System.out.printf("Enter starting row (0-7): ");
int row = in.nextInt();
System.out.printf("Enter starting column (0-7): ");
int col = in.nextInt();
solveTour(row, col);
in.close();
}
/**
* Helper method to determine if a square is safe for the knight
*
* @param row the row the knight is on
* @param col the column the knight is on
* @return true if the square is safe for the knight
*/
private static boolean isSafe(int row, int col)
{
return ((row >= 0 && row < BOARD_LENGTH)
&& (col >= 0 && col < BOARD_LENGTH)
&& (board[row][col] == -1));
}
/**
* Helper method to print the tour solution to the console
*/
private static void printTour()
{
for (int r = 0; r < BOARD_LENGTH; r++)
{
for (int c = 0; c < BOARD_LENGTH; c++)
{
System.out.print(board[r][c] + " ");
}
System.out.printf("\n");
}
}
/**
* Solves the knight's tour using backtracking
*
* @param sRow the starting row
* @param sCol the starting column
*/
public static void solveTour(int sRow, int sCol)
{
initializeBoard();
board[sRow][sCol] = 1;
if (solveTour(sRow, sCol, 2))
{
printTour();
}
else
{
System.out.printf("No Solution!%n");
printTour();
}
}
private static void initializeBoard()
{
board = new int[BOARD_LENGTH][BOARD_LENGTH];
//Make all of board -1 because have not visited any square
for (int r = 0; r < BOARD_LENGTH; r++)
{
for (int c = 0; c < BOARD_LENGTH; c++)
{
board[r][c] = -1;
}
}
}
/**
* Helper method that solve the tour
*
* @param row the current row
* @param col the current column
* @param kthMove the current move
* @return true if there is a solution to the knight's tour
*/
private static boolean solveTour(int row, int col, int kthMove)
{
//Base case
int nextRow = row;
int nextCol = col;
if(kthMove > MAX_MOVES)
{
return true;
}
int[] possXMoves = new int[5];
int[] possYMoves = new int[5];
int nextMove = 7;
for(int i = 0; i < MAX_MOVES; i++)
{
for (int j = 0; j < xMove.length; j++)
{
if(isSafe(row + xMove[j], col + yMove[j]))
{
possXMoves[j] = row + xMove[j];
possYMoves[j] = col + yMove[j];
}
else
{
possXMoves[j] = row;
possYMoves[j] = col;
}
}
for(int k = 0; k < 8; k++)
{
if(nextMove > hueristic[possXMoves[j]][possYMoves[j]])
{
if(isSafe(possXMoves[j], possYMoves[j]))
{
nextMove = hueristic[possXMoves[j]][possYMoves[j]];
nextRow = possXMoves[j];
nextCol = possYMoves[j];
}
}
}
hueristic[nextRow][nextCol] = 7;
if(isSafe(nextRow, nextCol))
{
board[nextRow][nextCol] = kthMove;
if (solveTour(nextRow, nextCol, kthMove + 1 ))
{
return true;
}
else
{
board[nextRow][nextCol] = -1;
heuristic[nextRow][nextCol] = nextMove;
}
}
}
return false;
}
}
EDIT : FINAL WORKING CODE
package csne2;
import java.util.Scanner;
public class KnightsTour
{
private final static int BOARD_LENGTH = 5; //The length of the board
private final static int MAX_MOVES = BOARD_LENGTH * BOARD_LENGTH;
private static int board[][]; //The simulated board
private static int[][] hueristic = new int[][]
{
{2, 3, 4, 3, 2},
{3, 4, 6, 4, 3},
{4, 6, 8, 6, 4},
{3, 4, 6, 4, 3},
{2, 3, 4, 3, 2}
};
private static int highestHeuristicNumPlusOne = 9;
//List of possible moves for the knight
private final static int xMove[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
private final static int yMove[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
System.out.printf("Enter starting row (0-7): ");
int row = in.nextInt();
System.out.printf("Enter starting column (0-7): ");
int col = in.nextInt();
solveTour(row, col);
in.close();
}
/**
* Helper method to determine if a square is safe for the knight
*
* @param row the row the knight is on
* @param col the column the knight is on
* @return true if the square is safe for the knight
*/
private static boolean isSafe(int row, int col)
{
return ((row >= 0 && row < BOARD_LENGTH)
&& (col >= 0 && col < BOARD_LENGTH)
&& (board[row][col] == -1));
}
/**
* Helper method to print the tour solution to the console
*/
private static void printTour()
{
for (int r = 0; r < BOARD_LENGTH; r++)
{
for (int c = 0; c < BOARD_LENGTH; c++)
{
System.out.print(board[r][c] + " ");
}
System.out.printf("\n");
}
}
/**
* Solves the knight's tour using backtracking
*
* @param sRow the starting row
* @param sCol the starting column
*/
public static void solveTour(int sRow, int sCol)
{
initializeBoard();
board[sRow][sCol] = 1;
if (solveTour(sRow, sCol, 2))
{
printTour();
}
else
{
System.out.printf("No Solution!%n");
printTour();
}
}
private static void initializeBoard()
{
board = new int[BOARD_LENGTH][BOARD_LENGTH];
//Make all of board -1 because have not visited any square
for (int r = 0; r < BOARD_LENGTH; r++)
{
for (int c = 0; c < BOARD_LENGTH; c++)
{
board[r][c] = -1;
}
}
}
/**
* Helper method that solve the tour
*
* @param row the current row
* @param col the current column
* @param kthMove the current move
* @return true if there is a solution to the knight's tour
*/
private static boolean solveTour(int row, int col, int kthMove)
{
//Base case
int nextRow = row;
int nextCol = col;
if(kthMove > MAX_MOVES)
{
return true;
}
int[] possXMoves = new int[xMove.length];
int[] possYMoves = new int[yMove.length];
int nextMove = highestHeuristicNumPlusOne;
for(int i = 0; i < MAX_MOVES; i++)
{
for (int j = 0; j < xMove.length; j++)
{
if(isSafe(row + xMove[j], col + yMove[j]))
{
possXMoves[j] = row + xMove[j];
possYMoves[j] = col + yMove[j];
}
else
{
possXMoves[j] = row;
possYMoves[j] = col;
}
if(nextMove > hueristic[possXMoves[j]][possYMoves[j]])
{
if(isSafe(possXMoves[j], possYMoves[j]))
{
nextMove = hueristic[possXMoves[j]][possYMoves[j]];
nextRow = possXMoves[j];
nextCol = possYMoves[j];
}
}
}
if(isSafe(nextRow, nextCol))
{
board[nextRow][nextCol] = kthMove;
if (solveTour(nextRow, nextCol, kthMove + 1 ))
{
return true;
}
else
{
board[nextRow][nextCol] = -1;
}
}
}
return false;
}
}
All help appreciated, I will try to clarify anything asked of me.
There are many problems in solveTour method