Knight's Tour code runs into infinite loop, does not reach a solution

Question

My Recursive Backtracking approach to Knight's Tour runs into an infinite loop. At first, I thought the problem might be taking this much time in general but some solutions do it in an instant. Please tell what is wrong with my code.

package io.github.thegeekybaniya.InterviewPrep.TopTopics.Backtracking;

import java.util.Arrays;

public class KnightsTour {
    private static int counter=0;

    public static void main(String[] args) {

        knightsTour(8);
    }

    private static void knightsTour(int i) {
        int[][] board = new int[i][i];
        for (int[] arr :
                board) {
            Arrays.fill(arr, -1);

        }
        board[0][0] = 0;
        knightsTour(board,0,1);

    }

    private static boolean knightsTour(int[][] board, int cellno, int stepno) {
        if (stepno == board.length * board.length) {
            printBoard(board);
            return true;
        }

        int[][] dirs = {
                {1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}
        };
        int row = cellno / board.length, col = cellno % board.length;
        for (int i = 0; i < dirs.length; i++) {
            int r = dirs[i][0] + row;
            int c = dirs[i][1] + col;
            if (isSafe(board, r, c)&&board[r][c]==-1) {
                int ncell = r * board.length + c;
                board[r][c] = stepno;
                if (knightsTour(board, ncell, stepno + 1)) {
                    return true;
                } else {
                    board[r][c] = -1;
                }
            }
        }


        return false;
    }

    private static boolean isSafe(int[][] board, int r, int c) {

        return r >= 0 && c >= 0 && r < board.length && c < board.length;
    }

    private static void printBoard(int[][] board) {
        System.out.println(++counter);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                System.out.print(board[i][j]+" ");

            }
            System.out.println();
        }
    }

}

Answer 1

There's no bug in your code, it's just that the brute force approach is slow because the search space is enormous. You can speed up the search by implementing Warnsdorf's Rule. This is a heuristic for choosing the next move, where you always try the move that results in the fewest available moves for the next move after that. It can be done in a couple of simple loops:

int row = cellno / board.length, col = cellno % board.length;

// find move with fewest moves available for the next move:
int minMovesAvailable = 8;
int minMovesDir = 0;
for (int i = 0; i < dirs.length; i++) {
    int r = dirs[i][0] + row;
    int c = dirs[i][1] + col;
    if (isSafe(board, r, c)&&board[r][c]==-1)
    {
        board[r][c] = stepno;
        int movesAvailable = 0;
        for (int j = 0; j < dirs.length; j++) {
            int r2 = dirs[j][0] + r;
            int c2 = dirs[j][1] + c;
            if (isSafe(board, r2, c2)&&board[r2][c2]==-1)
            {
                movesAvailable++;
            }
        }
        board[r][c] = -1;
        if(movesAvailable < minMovesAvailable)
        {
            minMovesAvailable = movesAvailable;
            minMovesDir = i;
        }
    }
}

// now recurse this move first:
// int r = dirs[minMovesDir][0] + row;
// int c = dirs[minMovesDir][1] + col;