Skip to main content

Knight Tour Problem

Here given code implementation process.

// 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




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