Objective

The Knight’s Tour problem is a classic example of backtracking in computer science.
The objective is to move a knight on a chessboard so that it visits every square exactly once.
This program uses backtracking to find one possible solution to the Knight’s Tour problem on an 8×8 chessboard.

Code

#include 
#include 

#define N 8

int move_x[] = {2, 1, -1, -2, -2, -1, 1, 2};
int move_y[] = {1, 2, 2, 1, -1, -2, -2, -1};

void printSolution(int board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) { printf("%2d ", board[i][j]); } printf("\n"); } } bool isSafe(int x, int y, int board[N][N]) { return (x >= 0 && x < N && y >= 0 && y < N && board[x][y] == -1);
}

bool solveKTUtil(int x, int y, int movei, int board[N][N]) {
    if (movei == N * N) {
        return true;
    }

    for (int k = 0; k < 8; k++) {
        int next_x = x + move_x[k];
        int next_y = y + move_y[k];
        if (isSafe(next_x, next_y, board)) {
            board[next_x][next_y] = movei;
            if (solveKTUtil(next_x, next_y, movei + 1, board)) {
                return true;
            }
            board[next_x][next_y] = -1; // backtrack
        }
    }
    return false;
}

bool solveKT() {
    int board[N][N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            board[i][j] = -1; // Initialize the chessboard
        }
    }

    // Starting position
    board[0][0] = 0;

    if (!solveKTUtil(0, 0, 1, board)) {
        printf("Solution does not exist");
        return false;
    } else {
        printSolution(board);
    }
    return true;
}

int main() {
    solveKT();
    return 0;
}
        

Program Structure

The program consists of the following key components:

• Constants and Variables: Defines the size of the chessboard and movement vectors for the knight.
• Function printSolution: Displays the chessboard with the knight’s path.
• Function isSafe: Checks if a position is valid for the knight to move.
• Function solveKTUtil: Implements the backtracking algorithm to find the knight’s tour.
• Function solveKT: Initializes the board and starts the tour from the first square.
• main Function: Entry point of the program that calls solveKT.

How to Run the Program

1. 1. Copy the provided C code into a text editor and save it as knights_tour.c.
   2. Open a terminal (or command prompt).
   3. Navigate to the directory where the file is saved.
   4. Compile the program using a C compiler (like gcc):

gcc knights_tour.c -o knights_tour

1. 1. Run the executable:

./knights_tour

1. The program will display the knight’s tour path on the chessboard.