Thread: 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;
    }
}

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.

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.