Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: Something wrong with my Knight's Tour solution

1. ## Something wrong with my Knight's Tour solution

I am required to make a recursive backtracking solution to the Knight's Tour problem using and 8x8 board and a starting location which is manually picked. I believe the problem lies in the recursive method solveTour() but i am not sure. The output is producing -1's in seemingly random locations and also skipping numbers entirely. I cannot figure out what exactly is wrong. Any help would be appreciated.

My code:
```
import java.awt.Point;

import java.util.Scanner;

/**
* The Knight's Tour using backtracking
*
* @author Tyler Weaver
*/
public class TheKnigthsTour {

private final static int BOARD_LENGTH = 8;      //The length of the board
private static int board[][];                   //The simulated board

//List of possible moves for the knight
private static final Point[] MOVES = new Point[]{new Point(-2, -1),
new Point(-2, 1), new Point(2, -1), new Point(2, 1), new Point(-1, -2),
new Point(-1, 2), new Point(1, -2), new Point(1, 2)};

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);
}

/**
* 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.printf("%-8d", 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) {
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;
}
}

board[sRow][sCol] = 1;

if (solveTour(sRow, sCol, 2)) {
printTour();
} else {
System.out.printf("No Solution!%n");
}
}

/**
* 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
if (kthMove >= BOARD_LENGTH * BOARD_LENGTH) {
return true;
}

for (Point p : MOVES) {
int nextRow = row + (int) p.x;
int nextCol = col + (int) p.y;

if (isSafe(nextRow, nextCol)) {
board[nextRow][nextCol] = kthMove;

kthMove = kthMove + 1;

if (solveTour(nextRow, nextCol, kthMove)) {
return true;
} else {
board[nextRow][nextCol] = -1;
}
}
}

return false;
}
}```

2. ## Re: Something wrong with my Knight's Tour solution

Can you copy the console's contents that shows the program's input and output showing what you are talking about and pasted it here?

3. ## Re: Something wrong with my Knight's Tour solution

Originally Posted by Norm
Can you copy the console's contents that shows the program's input and output showing what you are talking about and pasted it here?
Sure Thing. Sorry for not posting it earlier. The output for the input position (0,0) is:

```
1       24      3       26      5       28      7       30
-1      17      40      -1      42      31      44      -1
23      2       25      4       27      6       29      8
18      38      16      41      32      43      57      45
15      22      13      -1      11      51      9       -1
-1      19      37      34      48      59      46      56
36      14      21      12      52      10      50      63
20      -1      35      -1      -1      47      54      -1
```

I am sorry the numbers are not exactly aligned. I am unsure how to align these numbers properly.

4. ## Re: Something wrong with my Knight's Tour solution

how to align these numbers properly.
Post them inside of code tags to keep formatting.

I see about 10 -1s. What numbers are missing? Try to find out why they are missing.
Add some println stateements that print out the values of variables when kthMove has the value of the first of the missing numbers.

5. ## Re: Something wrong with my Knight's Tour solution

Originally Posted by Norm
Post them inside of code tags to keep formatting.

I see about 10 -1s. What numbers are missing? Try to find out why they are missing.
Add some println stateements that print out the values of variables when kthMove has the value of the first of the missing numbers.
Thanks for the tip!

Also, the first number to be missing appears to be 33. It goes straight from 32 to 34. I added a print statement for the kthMove to see how it is throughout the the recursive call but it does not seem to miss a single number. It repeats the numbers a few times which is expected because it is recursive, but it does not miss a single number.

I am confused as to why it misses numbers then. It seems like the problem lies in my 'if' statements. I may be completely wrong, but i will try to move things around.

EDIT: My if statement seems to be the problem, except when i tried to move the 'else' around i got an Index out of bounds error (-2). I truly do not know what else i should move around in my code. My nextRow and nextCol variables also seem to be working correctly. As is my isSafe method.

6. ## Re: Something wrong with my Knight's Tour solution

first number to be missing appears to be 33.
Does it assign the value of 33 to a square? Which square: (row,col)? Does the code later overwrite that square's 33 with a -1?

7. ## Re: Something wrong with my Knight's Tour solution

It assigns 33 to (1, 3). In that spot is a -1 which must mean that it did not work out (The recursive call returned false). So instead of subtracting 1 from the kthMove it moved on straight to 34? That makes sense since i do not subtract kthMove anywhere. So i should subtract it if it returns false which means i should place it directly in the 'else' statement.? Thank you very much for walking me through it! I will try it out!

I am confused as to why it only does that for certain numbers though such as 33 and not another number such as 34 or 35.