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