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)
	{
		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	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.

New Comment