Knight's Tour Problem in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
int n=5, x[8]={2,1,-1,-2,-2,-1,1,2}, y[8]={1,2,2,1,-1,-2,-2,-1}, board[5][5];
int tour(int r, int c, int move) {
    if(r<0||c<0||r>=n||c>=n||board[r][c]) return 0;
    board[r][c] = move;
    if(move == n*n) return 1;
    for(int i=0;i<8;i++)
        if(tour(r+x[i], c+y[i], move+1)) return 1;
    board[r][c]=0;
    return 0;
}
int main() {
    tour(0,0,1);
    for(int i=0;i<n;i++,puts(""))
        for(int j=0;j<n;j++) printf("%2d ", board[i][j]);
}

C Output

Input:  
Board size = 5×5, Start = (0,0)

Output:  
 1 12  7 22  3  
 8 23  2 13 18  
11  6 17  4 21  
24  9 14 19  0  
 5 10 25 16 15

C++ Program

#include <iostream>
using namespace std;
int n=5, board[5][5], dx[8]={2,1,-1,-2,-2,-1,1,2}, dy[8]={1,2,2,1,-1,-2,-2,-1};
bool tour(int x, int y, int move) {
    if(x<0||y<0||x>=n||y>=n||board[x][y]) return false;
    board[x][y] = move;
    if(move == n*n) return true;
    for(int i=0;i<8;i++)
        if(tour(x+dx[i], y+dy[i], move+1)) return true;
    board[x][y] = 0;
    return false;
}
int main() {
    tour(2,2,1);
    for(int i=0;i<n;i++,cout<<'\n')
        for(int j=0;j<n;j++) cout<<board[i][j]<<" ";
}

C++ Output

Input:  
Board size = 5×5, Start = (2,2)
 
Output:  
13 32  3 20 15  
 4 19 14 33  2  
31 12  1 16 21  
18  5 36 11 34  
 9 30 17 22 35

JAVA Program

public class Main {
    static int n=5,[][] board = new int[n][n];
    static int[] dx = {2,1,-1,-2,-2,-1,1,2}, dy = {1,2,2,1,-1,-2,-2,-1};
    static boolean tour(int x, int y, int move) {
        if(x<0||y<0||x>=n||y>=n||board[x][y]>0) return false;
        board[x][y] = move;
        if(move == n*n) return true;
        for(int i=0;i<8;i++)
            if(tour(x+dx[i], y+dy[i], move+1)) return true;
        board[x][y]=0;
        return false;
    }
    public static void main(String[] args) {
        tour(0,0,1);
        for(int[] row : board) {
            for(int val : row) System.out.printf("%2d ", val);
            System.out.println();
        }
    }
}

JAVA Output

Input:  
Board size = 5×5, Start = (0,0)

Output:  
 1 14 25  6  3  
24  7  2 13 26  
15  0 27  4  5  
 8 23 12 19 28  
17 16  9 22 11

Python Program

n = 5
board = [[0]*n for _ in range(n)]
dx = [2,1,-1,-2,-2,-1,1,2]
dy = [1,2,2,1,-1,-2,-2,-1]
def tour(x,y,move):
    if x<0 or y<0 or x>=n or y>=n or board[x][y]: return False
    board[x][y] = move
    if move == n*n: return True
    for i in range(8):
        if tour(x+dx[i], y+dy[i], move+1): return True
    board[x][y] = 0
    return False
tour(0,0,1)
for row in board: print(row)

Python Output

Input:  
Board size = 5×5, Start = (0,0)

Output:  
[1, 18, 31, 12, 3]  
[32, 13, 2, 17, 30]  
[19, 10, 33, 4, 11]  
[14, 5, 16, 29, 24]  
[9, 20, 7, 6, 15]

In-Depth Explanation

Example

The knight begins at (0,0) in the C program and goes through all 25 squares of a 5×5 chessboard using its L-shaped move.

Each number indicates the step number when the knight arrived at that square.

Real-Life Analogy

Imagine a delivery drone confined to taking L-shaped jumps in a city grid.

It has to drop off once to each house, without repeating the same location.

This exercise assists in the simulation of how the drone (knight) may plan such a journey.

Why It Matters

The Knight's Tour is more than just an entertaining puzzle — it's a timeless problem in:

Backtracking algorithms

Robot path planning

Game AI and simulations

Hamiltonian path detection

It provides a sense of mastering the attempt of all possibilities and backing out when a path fails.

Learning Insights

This exercise provides insight into:

Effective use of backtracking

Verification of constraints and edge cases

Using recursion effectively to search many states

Strategic trial-and-error programming

It's a sophisticated idea that develops strong problem-solving and recursion techniques.

Interview & Real-World Application

In interviews, this is questioned under:

Backtracking puzzle problems

Hamiltonian path-based grid pathfinding

Game simulation and tile movement

Real-world applications:

Planning knight-like robotic arm jumps

Chess-based puzzle solving

Move prediction and AI navigation rules

The Knight's Tour is a lovely combination of recursion, movement logic, and problem-solving that shows how to move about complex spaces with rules. It's essential in learning backtracking and shows up in numerous AI movement simulations and robotic pathfinding scenarios. With high-performance, simple-to-comprehend implementations in C, C++, Java, and Python, this tutorial enables students to develop solid problem-solving skills, thoroughly comprehend recursion, and solve backtracking problems easily in coding interviews and real-world applications.