The Knight's Tour Problem (using Backtracking Algorithm)

The backtracking algorithm works by exploring all possible moves for the knight, starting from a given square, and backtracking to try different moves if it reaches a dead end.

Here's the basic outline of the backtracking algorithm to solve the Knight's tour problem:

1. Choose a starting square for the knight on the chessboard.
2. Mark the starting square as visited.
3. For each valid move from the current square, make the move and recursively repeat the process for the new square.
4. If all squares on the chessboard have been visited, we have found a solution. Otherwise, undo the last move and try a different move.
5. If all moves have been tried from the current square and we have not found a solution, backtrack to the previous square and try a different move from there.
6. If we have backtracked to the starting square and tried all possible moves without finding a solution, there is no solution to the problem.

We have given the full C++ program for Backtracking Algorithm to solve Knight's Tour Problem below:

#include 
#include 
using namespace std;

const int N = 8;
int board[N][N];
int moveCount = 0;

vector<pair<int, int>> validMoves(int row, int col) {
    vector<pair<int, int>> moves;
    int rowMoves[] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int colMoves[] = {1, 2, 2, 1, -1, -2, -2, -1};
    for (int i = 0; i < 8; i++) {
        int newRow = row + rowMoves[i];
        int newCol = col + colMoves[i];
        if (newRow >= 0 && newRow < N && newCol >= 0 && newCol < N && board[newRow][newCol] == 0) {
            moves.push_back(make_pair(newRow, newCol));
        }
    }
    return moves;
}

bool solve(int row, int col, int moveNum) {
    board[row][col] = moveNum;
    moveCount++;

    if (moveNum == N*N) {
        return true;
    }

    vector<pair<int, int>> moves = validMoves(row, col);
    for (pair<int, int> move : moves) {
        int newRow = move.first;
        int newCol = move.second;
        if (solve(newRow, newCol, moveNum+1)) {
            return true;
        }
    }

    board[row][col] = 0;
    moveCount--;
    return false;
}

int main() {
    int startRow = 0, startCol = 0;
    solve(startRow, startCol, 1);
    cout << "Number of moves: " << moveCount << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

Output:

Number of moves: 64
1 38 55 34 3 36 19 22 
54 47 2 37 20 23 4 17 
39 56 33 46 35 18 21 10 
48 53 40 57 24 11 16 5 
59 32 45 52 41 26 9 12 
44 49 58 25 62 15 6 27 
31 60 51 42 29 8 13 64 
50 43 30 61 14 63 28 7 

Check the image below before we explain the code:

In this implementation, we first define a function validMoves which takes the current row and column of the knight as input and returns a vector of pairs representing all the valid moves that the knight can make from that position.

The solve function is a recursive function that takes the current row and column of the knight, as well as the current move number, as input. We mark the current square as visited by setting board[row][column] it to the current move number, and then we recursively try all possible moves from the current position.

If we reach the last move, then we found a solution and return true. If no valid move is found from the current position, we backtrack by setting the current square to 0 and returning false.

In the main function, we start the solve function at a specified starting position and then output the number of moves it took to find a solution and print the final chessboard with the solution.

Time & Space Complexity for Backtracking

The backtracking algorithm used to solve the Knight's Tour problem has an exponential time complexity. The number of possible paths for the knight grows very quickly as the size of the chessboard increases, which means that the time taken to explore all possible paths grows exponentially.

The exact time complexity of the Knight's Tour Backtracking algorithm is O(8^(n^2)), where n is the size of the chessboard. This is because each move has a maximum of 8 possible directions, and we have to explore all possible moves until we find a solution.

The space complexity of the backtracking algorithm is O(n^2), where n is the size of the chessboard. So, we can say that the backtracking algorithm is efficient for smaller chessboards.

Warnsdorff's Rule

Warndorff's rule is a heuristic greedy algorithm used to solve this problem. It tries to move the knight to the square with the fewest valid moves, hoping that this will lead to a solution.

Here's an overview of how Warndorff's rule algorithm works:

1. Start with a random square on the chessboard.
2. From the current square, consider all possible moves and count the number of valid moves from each adjacent square.
3. Move to the square with the lowest number of valid moves. In case of a tie, move to the square with the lowest number of valid moves from its adjacent squares.
4. Repeat steps 2 and 3 until all squares on the chessboard have been visited.

Here is the pseudocode for Warndorff's rule algorithm:

initialize the chessboard
choose a random starting square
while there are unvisited squares:
    mark the current square as visited
    for each adjacent square to the current square:
        count the number of valid moves from that square
    move to the adjacent square with the lowest count

The time complexity of Warndorff's rule algorithm is O(n^2 log n), where n is the size of the chessboard. This is because we have to visit each square once, and for each square, we have to compute the number of valid moves from each adjacent square. The space complexity of the algorithm is O(n^2) since we need to store the chessboard and the current position of the knight.