Knight Tour Problem
The Knight's Tour Problem is a classic chess puzzle where the goal is to find a sequence of moves for a knight on an N x N chessboard such that the knight visits every square exactly once. The knight moves in an L-shape: two squares in one direction (either horizontally or vertically) followed by one square in a perpendicular direction.
This problem has captured the interest of mathematicians and computer scientists for centuries due to its complexity and its connections to graph theory and algorithms. Solving the Knight's Tour Problem involves finding a Hamiltonian path (a path that visits every vertex exactly once) on a graph representing the chessboard, with knights' moves as edges.
Problem Statement
Given an N x N chessboard and a starting position for the knight, the task is to find a sequence of valid moves that covers all cells of the chessboard exactly once.
Example
Let's consider a 5 x 5 chessboard with the knight starting from position (0, 0). Here's how one possible solution might look:
17 8 15 6 23
16 5 18 7 14
9 22 13 24 19
4 11 20 3 10
21 2 25 12 1Idea to Solve
To solve the Knight's Tour Problem, we can use a backtracking approach. The idea is to explore all possible paths the knight can take on the chessboard, while keeping track of the visited cells. If we find a path that covers all cells, we've solved the problem. If not, we backtrack and try a different path.
Algorithm
- Initialize the chessboard grid with all cells marked as unvisited (0).
- Start from the initial position (0, 0) and mark it as visited (1).
- Define arrays
x_axisandy_axisto represent the possible moves of the knight. - Implement a recursive function
knightTourSolutionthat takes the current position(x, y), the current step number, the grid, and the move arrays as parameters. - In the
knightTourSolutionfunction: a. Check if the current step number is equal to the total number of cells on the chessboard. If so, return 1 (solution found). b. Iterate through all possible moves of the knight using thex_axisandy_axisarrays. c. For each valid move, check if the new position is within the bounds of the chessboard and has not been visited. d. If the move is valid, mark the new position as visited with the current step number. e. Recursively call theknightTourSolutionfunction with the new position and an incremented step number. f. If the recursive call returns 1 (solution found), return 1. g. If the recursive call returns 0, backtrack by marking the current position as unvisited (0) and continue trying other moves. - In the
knightTourfunction: a. Initialize the grid and mark the starting position as visited. b. Call theknightTourSolutionfunction with the starting position and step number 2. c. If theknightTourSolutionfunction returns 1, print the solution by calling theprintResultfunction. d. If theknightTourSolutionfunction returns 0, print "No Solution."
Code Solution
// C program for
// Knight Tour Problem
#include <stdio.h>
#define N 8
// Print calculated knight tour solution
void printResult(int grid[N][N])
{
// Execute loop through by row
for (int x = 0; x < N; x++)
{
// Execute loop through by column
for (int y = 0; y < N; y++)
{
printf(" %d", grid[x][y]);
}
printf("\n");
}
}
// Check that given place are valid for knight tour or not
int isSafe(int r, int c, int grid[N][N])
{
// Check following condition
// (r >= 0 && r < N) Check valid row and
// (c >= 0 && c < N) Check valid col and
// (grid[r][c] == 0) When locations are not visited
return ((r >= 0 && r < N) && (c >= 0 && c < N) && grid[r][c] == 0);
}
int knightTourSolution(int x, int y, int location,
int grid[N][N], int x_axis[], int y_axis[])
{
if ((N *N) == location)
{
// When result are exist
return 1;
}
int local_x = 0;
int local_y = 0;
for (int i = 0; i < N; i++)
{
// Get new location
local_x = x + x_axis[i];
local_y = y + y_axis[i];
if (isSafe(local_x, local_y, grid))
{
// Set new value to x and y axis
grid[local_x][local_y] = location;
if (knightTourSolution(local_x, local_y,
location + 1, grid, x_axis, y_axis) == 1)
{
// When solution found, then stop backtracking process
return 1;
}
else
{
// Reset location
grid[local_x][local_y] = 0;
}
}
}
return 0;
}
// Handles the request to find knight tour solution
void knightTour()
{
// Define all move position of x axis
// Total 8 possible directions
int x_axis[] = {
2 , 1 , -1 , -2 , -2 , -1 , 1 , 2
};
// Define all move position of y axis
// Total 8 possible directions
int y_axis[] = {
1 , 2 , 2 , 1 , -1 , -2 , -2 , -1
};
// Use to collect knight tour solution
int grid[N][N];
// UnSet initial all position of resultant grid
for (int x = 0; x < N; x++)
{
for (int y = 0; y < N; y++)
{
grid[x][y] = 0;
}
}
// Set first move (0,0) location
grid[0][0] = 1;
if (knightTourSolution(0, 0, 2, grid, x_axis, y_axis) == 1)
{
// When solution exist
printResult(grid);
}
else
{
printf("No Solution\n");
}
}
int main(int argc, char const *argv[])
{
// Test
knightTour();
return 0;
}input
1 38 55 34 31 18 9 0
56 51 32 37 10 35 30 17
39 2 49 54 33 28 19 8
50 57 52 27 36 11 16 29
63 40 3 48 53 24 7 20
58 47 60 43 26 21 12 15
41 62 45 4 23 14 25 6
46 59 42 61 44 5 22 13/*
Java Program for
Knight Tour Problem
*/
public class KnightTour
{
public int n;
public KnightTour()
{
n = 8;
}
// Print calculated knight tour solution
public void printResult(int[][] grid)
{
// Execute loop through by row
for (int x = 0; x < n; x++)
{
// Execute loop through by column
for (int y = 0; y < n; y++)
{
System.out.print("\t" + grid[x][y]);
}
System.out.print("\n");
}
}
// Check that given place are valid for knight tour or not
public boolean isSafe(int r, int c, int[][] grid)
{
// Check following condition
// (r >= 0 && r < n) Check valid row and
// (c >= 0 && c < n) Check valid col and
// (grid[r][c] == 0) When locations are not visited
return ((r >= 0 && r < n) && (c >= 0 && c < n) && grid[r][c] == 0);
}
// Finding the recursively knight tour solution
public boolean knightTourSolution(int x, int y, int location,
int[][] grid, int[] x_axis, int[] y_axis)
{
if ((n * n) + 1 == location)
{
// When result are exist
return true;
}
int local_x = 0;
int local_y = 0;
for (int i = 0; i < n; i++)
{
// Get new location
local_x = x + x_axis[i];
local_y = y + y_axis[i];
if (isSafe(local_x, local_y, grid))
{
// Set new value to x and y axis
grid[local_x][local_y] = location;
if (knightTourSolution(local_x, local_y,
location + 1, grid, x_axis, y_axis))
{
// When solution found, then stop backtracking process
return true;
}
else
{
// Reset location
grid[local_x][local_y] = 0;
}
}
}
return false;
}
// Handles the request to find knight tour solution
public void knightTourVist()
{
// Define all move position of x axis
// Total 8 possible directions
int[] x_axis = {
2 , 1 , -1 , -2 , -2 , -1 , 1 , 2
};
// Define all move position of y axis
// Total 8 possible directions
int[] y_axis = {
1 , 2 , 2 , 1 , -1 , -2 , -2 , -1
};
// Use to collect knight tour solution
int[][] grid = new int[n][n];
// UnSet initial all position of resultant grid
for (int x = 0; x < n; x++)
{
for (int y = 0; y < n; y++)
{
grid[x][y] = 0;
}
}
// Set first move (0,0) location
grid[0][0] = 1;
if (knightTourSolution(0, 0, 2, grid, x_axis, y_axis))
{
// When solution exist
printResult(grid);
}
else
{
System.out.print("no Solution\n");
}
}
public static void main(String[] args)
{
KnightTour task = new KnightTour();
// Test
task.knightTourVist();
}
}input
1 60 39 34 31 18 9 64
38 35 32 61 10 63 30 17
59 2 37 40 33 28 19 8
36 49 42 27 62 11 16 29
43 58 3 50 41 24 7 20
48 51 46 55 26 21 12 15
57 44 53 4 23 14 25 6
52 47 56 45 54 5 22 13// Include header file
#include <iostream>
#define N 8
using namespace std;
/*
C++ Program for
Knight Tour Problem
*/
class KnightTour
{
public:
int n;
KnightTour()
{
this->n = 8;
}
// Print calculated knight tour solution
void printResult(int grid[N][N])
{
// Execute loop through by row
for (int x = 0; x < this->n; x++)
{
// Execute loop through by column
for (int y = 0; y < this->n; y++)
{
cout << "\t" << grid[x][y];
}
cout << "\n";
}
}
// Check that given place are valid for knight tour or not
bool isSafe(int r, int c, int grid[N][N])
{
// Check following condition
// (r >= 0 && r < n) Check valid row and
// (c >= 0 && c < n) Check valid col and
// (grid[r][c] == 0) When locations are not visited
return ((r >= 0 && r < this->n) && (c >= 0 && c < this->n) && grid[r][c] == 0);
}
// Finding the recursively knight tour solution
bool knightTourSolution(int x, int y, int location, int grid[N][N], int x_axis[], int y_axis[])
{
if ((this->n *this->n) + 1 == location)
{
// When result are exist
return true;
}
int local_x = 0;
int local_y = 0;
for (int i = 0; i < this->n; i++)
{
// Get new location
local_x = x + x_axis[i];
local_y = y + y_axis[i];
if (this->isSafe(local_x, local_y, grid))
{
// Set new value to x and y axis
grid[local_x][local_y] = location;
if (this->knightTourSolution(local_x, local_y, location + 1, grid, x_axis, y_axis))
{
// When solution found, then stop backtracking process
return true;
}
else
{
// Reset location
grid[local_x][local_y] = 0;
}
}
}
return false;
}
// Handles the request to find knight tour solution
void knightTourVist()
{
// Define all move position of x axis
// Total 8 possible directions
int x_axis[] = {
2 , 1 , -1 , -2 , -2 , -1 , 1 , 2
};
// Define all move position of y axis
// Total 8 possible directions
int y_axis[] = {
1 , 2 , 2 , 1 , -1 , -2 , -2 , -1
};
// Use to collect knight tour solution
int grid[N][N];
// UnSet initial all position of resultant grid
for (int x = 0; x < this->n; x++)
{
for (int y = 0; y < this->n; y++)
{
grid[x][y] = 0;
}
}
// Set first move (0,0) location
grid[0][0] = 1;
if (this->knightTourSolution(0, 0, 2, grid, x_axis, y_axis))
{
// When solution exist
this->printResult(grid);
}
else
{
cout << "no Solution\n";
}
}
};
int main()
{
KnightTour *task = new KnightTour();
// Test
task->knightTourVist();
return 0;
}input
1 60 39 34 31 18 9 64
38 35 32 61 10 63 30 17
59 2 37 40 33 28 19 8
36 49 42 27 62 11 16 29
43 58 3 50 41 24 7 20
48 51 46 55 26 21 12 15
57 44 53 4 23 14 25 6
52 47 56 45 54 5 22 13// Include namespace system
using System;
/*
Csharp Program for
Knight Tour Problem
*/
public class KnightTour
{
public int n;
public KnightTour()
{
this.n = 8;
}
// Print calculated knight tour solution
public void printResult(int[,] grid)
{
// Execute loop through by row
for (int x = 0; x < this.n; x++)
{
// Execute loop through by column
for (int y = 0; y < this.n; y++)
{
Console.Write("\t" + grid[x,y]);
}
Console.Write("\n");
}
}
// Check that given place are valid for knight tour or not
public Boolean isSafe(int r, int c, int[,] grid)
{
// Check following condition
// (r >= 0 && r < n) Check valid row and
// (c >= 0 && c < n) Check valid col and
// (grid[r,c] == 0) When locations are not visited
return ((r >= 0 && r < this.n) && (c >= 0 && c < this.n)
&& grid[r,c] == 0);
}
// Finding the recursively knight tour solution
public Boolean knightTourSolution(int x, int y, int location,
int[,] grid, int[] x_axis, int[] y_axis)
{
if ((this.n * this.n) + 1 == location)
{
// When result are exist
return true;
}
int local_x = 0;
int local_y = 0;
for (int i = 0; i < this.n; i++)
{
// Get new location
local_x = x + x_axis[i];
local_y = y + y_axis[i];
if (this.isSafe(local_x, local_y, grid))
{
// Set new value to x and y axis
grid[local_x,local_y] = location;
if (this.knightTourSolution(local_x, local_y,
location + 1, grid, x_axis, y_axis))
{
// When solution found, then stop backtracking process
return true;
}
else
{
// Reset location
grid[local_x,local_y] = 0;
}
}
}
return false;
}
// Handles the request to find knight tour solution
public void knightTourVist()
{
// Define all move position of x axis
// Total 8 possible directions
int[] x_axis = {
2 , 1 , -1 , -2 , -2 , -1 , 1 , 2
};
// Define all move position of y axis
// Total 8 possible directions
int[] y_axis = {
1 , 2 , 2 , 1 , -1 , -2 , -2 , -1
};
// Use to collect knight tour solution
int[,] grid = new int[this.n,this.n];
// UnSet initial all position of resultant grid
for (int x = 0; x < this.n; x++)
{
for (int y = 0; y < this.n; y++)
{
grid[x,y] = 0;
}
}
// Set first move (0,0) location
grid[0,0] = 1;
if (this.knightTourSolution(0, 0, 2, grid, x_axis, y_axis))
{
// When solution exist
this.printResult(grid);
}
else
{
Console.Write("no Solution\n");
}
}
public static void Main(String[] args)
{
KnightTour task = new KnightTour();
// Test
task.knightTourVist();
}
}input
1 60 39 34 31 18 9 64
38 35 32 61 10 63 30 17
59 2 37 40 33 28 19 8
36 49 42 27 62 11 16 29
43 58 3 50 41 24 7 20
48 51 46 55 26 21 12 15
57 44 53 4 23 14 25 6
52 47 56 45 54 5 22 13/*
Kotlin Program for
Knight Tour Problem
*/
class KnightTour
{
var n: Int;
constructor()
{
this.n = 8;
}
// Print calculated knight tour solution
fun printResult(grid: Array < Array < Int >> ): Unit
{
var x: Int = 0;
while (x < this.n)
{
var y: Int = 0;
while (y < this.n)
{
print("\t" + grid[x][y]);
y += 1;
}
print("\n");
x += 1;
}
}
// Check that given place are valid for knight tour or not
fun isSafe(r: Int, c: Int, grid: Array < Array < Int >> ): Boolean
{
// Check following condition
// (r >= 0 && r < n) Check valid row and
// (c >= 0 && c < n) Check valid col and
// (grid[r][c] == 0) When locations are not visited
return ((r >= 0 && r < this.n) && (c >= 0 && c < this.n) && grid[r][c] == 0);
}
// Finding the recursively knight tour solution
fun knightTourSolution(x: Int, y: Int, location: Int, grid: Array < Array < Int >> , x_axis: Array < Int > , y_axis: Array < Int > ): Boolean
{
if ((this.n * this.n) + 1 == location)
{
// When result are exist
return true;
}
var local_x: Int ;
var local_y: Int ;
var i: Int = 0;
while (i < this.n)
{
// Get new location
local_x = x + x_axis[i];
local_y = y + y_axis[i];
if (this.isSafe(local_x, local_y, grid))
{
// Set new value to x and y axis
grid[local_x][local_y] = location;
if (this.knightTourSolution(local_x, local_y, location + 1, grid, x_axis, y_axis))
{
// When solution found, then stop backtracking process
return true;
}
else
{
// Reset location
grid[local_x][local_y] = 0;
}
}
i += 1;
}
return false;
}
// Handles the request to find knight tour solution
fun knightTourVist(): Unit
{
// Define all move position of x axis
// Total 8 possible directions
val x_axis: Array < Int > = arrayOf(2, 1, -1, -2, -2, -1, 1, 2);
// Define all move position of y axis
// Total 8 possible directions
val y_axis: Array < Int > = arrayOf(1, 2, 2, 1, -1, -2, -2, -1);
// Use to collect knight tour solution
// UnSet initial all position of resultant grid
val grid: Array < Array < Int >> = Array(this.n)
{
Array(this.n)
{
0
}
};
// Set first move (0,0) location
grid[0][0] = 1;
if (this.knightTourSolution(0, 0, 2, grid, x_axis, y_axis))
{
// When solution exist
this.printResult(grid);
}
else
{
print("no Solution\n");
}
}
}
fun main(args: Array < String > ): Unit
{
val task: KnightTour = KnightTour();
// Test
task.knightTourVist();
}input
1 60 39 34 31 18 9 64
38 35 32 61 10 63 30 17
59 2 37 40 33 28 19 8
36 49 42 27 62 11 16 29
43 58 3 50 41 24 7 20
48 51 46 55 26 21 12 15
57 44 53 4 23 14 25 6
52 47 56 45 54 5 22 13/*
Scala Program for
Knight Tour Problem
*/
class KnightTour(var n: Int)
{
def this()
{
this(8);
}
// Print calculated knight tour solution
def printResult(grid: Array[Array[Int]]): Unit = {
// Execute loop through by row
var x: Int = 0;
while (x < n)
{
// Execute loop through by column
var y: Int = 0;
while (y < n)
{
print("\t" + grid(x)(y));
y += 1;
}
print("\n");
x += 1;
}
}
// Check that given place are valid for knight tour or not
def isSafe(r: Int, c: Int, grid: Array[Array[Int]]): Boolean = {
// Check following condition
// (r >= 0 && r < n) Check valid row and
// (c >= 0 && c < n) Check valid col and
// (grid[r][c] == 0) When locations are not visited
return ((r >= 0 && r < n) && (c >= 0 && c < n) && grid(r)(c) == 0);
}
// Finding the recursively knight tour solution
def knightTourSolution(x: Int, y: Int, location: Int, grid: Array[Array[Int]], x_axis: Array[Int], y_axis: Array[Int]): Boolean = {
if ((n * n) + 1 == location)
{
// When result are exist
return true;
}
var local_x: Int = 0;
var local_y: Int = 0;
var i: Int = 0;
while (i < n)
{
// Get new location
local_x = x + x_axis(i);
local_y = y + y_axis(i);
if (isSafe(local_x, local_y, grid))
{
// Set new value to x and y axis
grid(local_x)(local_y) = location;
if (knightTourSolution(local_x, local_y, location + 1, grid, x_axis, y_axis))
{
// When solution found, then stop backtracking process
return true;
}
else
{
// Reset location
grid(local_x)(local_y) = 0;
}
}
i += 1;
}
return false;
}
// Handles the request to find knight tour solution
def knightTourVist(): Unit = {
// Define all move position of x axis
// Total 8 possible directions
var x_axis: Array[Int] = Array(2, 1, -1, -2, -2, -1, 1, 2);
// Define all move position of y axis
// Total 8 possible directions
var y_axis: Array[Int] = Array(1, 2, 2, 1, -1, -2, -2, -1);
// Use to collect knight tour solution
// UnSet initial all position of resultant grid
var grid: Array[Array[Int]] = Array.fill[Int](n, n)(0);
// Set first move (0,0) location
grid(0)(0) = 1;
if (knightTourSolution(0, 0, 2, grid, x_axis, y_axis))
{
// When solution exist
printResult(grid);
}
else
{
print("no Solution\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: KnightTour = new KnightTour();
// Test
task.knightTourVist();
}
}input
1 60 39 34 31 18 9 64
38 35 32 61 10 63 30 17
59 2 37 40 33 28 19 8
36 49 42 27 62 11 16 29
43 58 3 50 41 24 7 20
48 51 46 55 26 21 12 15
57 44 53 4 23 14 25 6
52 47 56 45 54 5 22 13/*
Node JS Program for
Knight Tour Problem
*/
class KnightTour
{
constructor()
{
this.n = 8;
}
// Print calculated knight tour solution
printResult(grid)
{
// Execute loop through by row
for (var x = 0; x < this.n; x++)
{
// Execute loop through by column
for (var y = 0; y < this.n; y++)
{
process.stdout.write("\t" + grid[x][y]);
}
process.stdout.write("\n");
}
}
// Check that given place are valid for knight tour or not
isSafe(r, c, grid)
{
// Check following condition
// (r >= 0 && r < n) Check valid row and
// (c >= 0 && c < n) Check valid col and
// (grid[r][c] == 0) When locations are not visited
return ((r >= 0 && r < this.n) && (c >= 0 && c < this.n) && grid[r][c] == 0);
}
// Finding the recursively knight tour solution
knightTourSolution(x, y, location, grid, x_axis, y_axis)
{
if ((this.n * this.n) + 1 == location)
{
// When result are exist
return true;
}
var local_x = 0;
var local_y = 0;
for (var i = 0; i < this.n; i++)
{
// Get new location
local_x = x + x_axis[i];
local_y = y + y_axis[i];
if (this.isSafe(local_x, local_y, grid))
{
// Set new value to x and y axis
grid[local_x][local_y] = location;
if (this.knightTourSolution(local_x, local_y, location + 1, grid, x_axis, y_axis))
{
// When solution found, then stop backtracking process
return true;
}
else
{
// Reset location
grid[local_x][local_y] = 0;
}
}
}
return false;
}
// Handles the request to find knight tour solution
knightTourVist()
{
// Define all move position of x axis
// Total 8 possible directions
var x_axis = [2, 1, -1, -2, -2, -1, 1, 2];
// Define all move position of y axis
// Total 8 possible directions
var y_axis = [1, 2, 2, 1, -1, -2, -2, -1];
// Use to collect knight tour solution
// UnSet initial all position of resultant grid
var grid = Array(this.n).fill(0).map(() => new Array(this.n).fill(0));
// Set first move (0,0) location
grid[0][0] = 1;
if (this.knightTourSolution(0, 0, 2, grid, x_axis, y_axis))
{
// When solution exist
this.printResult(grid);
}
else
{
process.stdout.write("no Solution\n");
}
}
}
function main()
{
var task = new KnightTour();
// Test
task.knightTourVist();
}
main();input
1 60 39 34 31 18 9 64
38 35 32 61 10 63 30 17
59 2 37 40 33 28 19 8
36 49 42 27 62 11 16 29
43 58 3 50 41 24 7 20
48 51 46 55 26 21 12 15
57 44 53 4 23 14 25 6
52 47 56 45 54 5 22 13Time Complexity
The time complexity of this solution depends on the branching factor of the recursive tree and the number of positions to explore. In the worst case, the knight may have 8 possible moves at each step. The total number of positions to explore is N^2. Therefore, the worst-case time complexity is O(8^(N^2)).
However, due to the nature of backtracking and the constraints of the knight's movement, the actual number of positions explored is much less than this upper bound. In practice, the algorithm is feasible for relatively small chessboard sizes.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment