The Knight’s Tour problem is a classic example of backtracking algorithms. The objective is to move a knight on a chessboard such that it visits every square exactly once.

Program Structure

The program is structured as follows:

• Constants: Dimensions of the chessboard and the possible moves of the knight.
• Functions:
  • isSafe: Checks if a move is within the bounds of the chessboard.
  • printSolution: Prints the solution path.
  • solveKT: Main function that implements the backtracking algorithm to solve the problem.

Code

#include <iostream>
#include <vector>

using namespace std;

// Chessboard dimensions
const int N = 8;

// Possible moves for a knight
int knightMoves[8][2] = {
    {2, 1}, {1, 2}, {-1, 2}, {-2, 1},
    {-2, -1}, {-1, -2}, {1, -2}, {2, -1}
};

// Function to check if (x, y) is a valid move
bool isSafe(int x, int y, vector<vector<int> >& board) {
    return (x >= 0 && x < N && y >= 0 && y < N && board[x][y] == -1);
}

// Function to print the solution
void printSolution(const vector<vector<int> >& board) {
    for (const auto& row : board) {
        for (const auto& cell : row) {
            cout << cell << " ";
        }
        cout << endl;
    }
}

// Main function to solve Knight's Tour problem
bool solveKTUtil(int x, int y, int movei, vector<vector<int> >& board) {
    if (movei == N * N) {
        return true; // All squares are visited
    }

    // Try all next moves from the current coordinate x, y
    for (int k = 0; k < 8; k++) {
        int next_x = x + knightMoves[k][0];
        int next_y = y + knightMoves[k][1];
        if (isSafe(next_x, next_y, board)) {
            board[next_x][next_y] = movei; // Mark as visited
            if (solveKTUtil(next_x, next_y, movei + 1, board)) {
                return true;
            }
            board[next_x][next_y] = -1; // Backtrack
        }
    }
    return false; // No further moves possible
}

// Function to solve the Knight's Tour problem
void solveKT() {
    vector<vector<int> > board(N, vector<int>(N, -1));
    board[0][0] = 0; // Starting position

    if (!solveKTUtil(0, 0, 1, board)) {
        cout << "Solution does not exist" << endl;
    } else {
        printSolution(board);
    }
}

// Main function
int main() {
    solveKT();
    return 0;
}

How It Works

The program initializes a chessboard and starts the knight at position (0, 0). It uses backtracking to explore all possible moves of the knight:

1. Check if the next move is valid using the isSafe function.
2. If valid, mark the square as visited and move to that position.
3. If all squares are visited, the function returns true.
4. If a move leads to a dead end, backtrack by marking the square as unvisited and try the next move.

Output

The output will be an 8×8 grid showing the sequence of moves made by the knight:

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