Posted on by Kalkicode
Code Backtracking

# 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  1``````

## Idea 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

1. Initialize the chessboard grid with all cells marked as unvisited (0).
2. Start from the initial position (0, 0) and mark it as visited (1).
3. Define arrays `x_axis` and `y_axis` to represent the possible moves of the knight.
4. Implement a recursive function `knightTourSolution` that takes the current position `(x, y)`, the current step number, the grid, and the move arrays as parameters.
5. In the `knightTourSolution` function: 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 the `x_axis` and `y_axis` arrays. 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 the `knightTourSolution` function 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.
6. In the `knightTour` function: a. Initialize the grid and mark the starting position as visited. b. Call the `knightTourSolution` function with the starting position and step number 2. c. If the `knightTourSolution` function returns 1, print the solution by calling the `printResult` function. d. If the `knightTourSolution` function 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)
{
// Test
}
}``````

#### 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()
{
// Test
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)
{
// Test
}
}``````

#### 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
{
// Test
}``````

#### 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
}
}``````

#### 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()
{
// Test
}
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	13``````

## Time 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.

## Comment

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.

Categories
Relative Post