Posted on by Kalkicode
Code Backtracking

# Warnsdorff’s algorithm for knight’s tour problem

Warnsdorff’s algorithm are used to find all moves of single knight's tour. This algorithm is start with a random position of the cell in the [8X8] grid. And check whether the knight can be visit other all points in grid or not.

When knight is not visit to each cell, Then using of backtracking change the path of knight. If its solution is not possible then change starting position are repeat same process until solution are not found.

This algorithm work on random number selection so result can different. Here given code implementation process.

## Problem Statement

Given an N x N chessboard, the task is to find a sequence of moves for a knight such that it visits every square exactly once. The knight follows the rules of chess for its movements, i.e., it moves in an L-shape (two squares horizontally or vertically and then one square in the perpendicular direction).

## Pseudocode Algorithm with Explanation

``````
// Initialize the chessboard matrix with -1's
set_default(out)

// Get a random starting location
sx = random_number() % N
sy = random_number() % N
x = sx
y = sy

// Set the value of the first move
out[y * N + x] = 1

for i = 0 to (N * N) - 1:
if move_process(out, &x, &y) == 0:
return 0
end if
end for

// Check if the last position has a valid move back to the starting position
if neighbour(x, y, sx, sy) == 0:
return 0
end if

// Print the resulting knight's tour
print_result(out)
return 1
```
```

Let's go through the steps of the algorithm:

1. Initialize the chessboard matrix with -1's. This matrix will represent the knight's tour.
2. Choose a random starting location (sx, sy) on the chessboard.
3. Set the value of the first move at position (x, y) to 1.
4. Iterate (N * N) - 1 times to make the remaining moves:
• Use the move_process function to determine the next valid move based on Warnsdorff's heuristic.
• If there are no valid moves, return 0 to indicate that a valid knight's tour cannot be found.
• Update the knight's position (x, y) to the chosen move.
5. Check if the last position has a valid move back to the starting position. If not, return 0.
6. Print the resulting knight's tour.
7. Return 1 to indicate that a valid knight's tour has been found.

## Code Solution

``````// C program
// Knight Tour problem using Warnsdorff's Heuristics
#include <stdio.h>

#include <time.h>

#include <stdlib.h>

#define N 8
/*maintain the knight's position*/
static int move_cx[N]={1,1,2,2,-1,-1,-2,-2};
static int move_cy[N]={2,-2,1,-1,2,-2,1,-1};

/*Check whether move location is valid to chessboard*/
int is_valid_move(int x, int y)
{
if ((x >= 0 && y >= 0) && (x < N && y < N))
{
return 1;
}
return 0;
}
/*Checks whether a square is empty or not */
int is_empty(int out[], int x, int y)
{
if ((is_valid_move(x, y)) && (out[y * N + x] < 0))
{
return 1;
}
return 0;
}
/*Returns the number of empty squares */
int getcount(int out[], int x, int y)
{
int i, count = 0;
for (i = 0; i < N; ++i)
{
if (is_empty(out, (x + move_cx[i]), (y + move_cy[i])))
{
count++;
}
}
return count;
}
/* Calculates the minimum degree
And assigns the counter to that square */
int move_process(int out[], int * x, int * y)
{
int start, count, i, flag = -1, c, min = (N + 1), nx, ny;
start = rand() % N;
for (count = 0; count < N; ++count)
{
i = (start + count) % N;
nx = * x + move_cx[i];
ny = * y + move_cy[i];
if ((is_empty(out, nx, ny)))
{
c = getcount(out, nx, ny);
if (c < min)
{
flag = i;
min = c;
}
}
}
if (min == N + 1)
{
return 0;
}
nx = * x + move_cx[flag];
ny = * y + move_cy[flag];
//Assigns the counter
out[ny * N + nx] = out[( * y) * N + ( * x)] + 1;* x = nx;* y = ny;
return 1;
}
/* Displays the chessboard with all the legal knight's moves */
void print_result(int out[])
{
int i, j;
for (i = 0; i < N; ++i)
{
for (j = 0; j < N; ++j)
{
printf("%d\t", out[j * N + i]);
}
printf("\n");
}
}
/* Checks its neighbouring sqaures */
int neighbour(int x, int y, int start_x, int start_y)
{
int i;
for (i = 0; i < N; ++i)
{
if (((x + move_cx[i]) == start_x) && ((y + move_cy[i]) == start_y))
{
return 1;
}
}
return 0;
}
//Set default moves
void set_default(int out[])
{
//fill the chess board matrix with -1's
for (int i = 0; i < N * N; ++i)
{
out[i] = -1;
}
}
/* Display the legal moves using warnsdorff's heuristics */
int generate(int out[])
{
set_default(out);
int i, x, y, sx, sy;
//Get a random starting location
sx = rand() % N;
sy = rand() % N;
x = sx;
y = sy;
//Set the value of first moves
out[y * N + x] = 1;
for (i = 0; i < (N * N) - 1; ++i)
{
if (move_process(out, & x, & y) == 0)
{
return 0;
}
}
if (neighbour(x, y, sx, sy) == 0)
{
return 0;
}
//When get a valid solution
print_result(out);
return 1;
}
int main()
{
srand(time(NULL));
//used to store result
int out[N * N];
while (!generate(out));
return 0;
}``````

#### Output

``````39 8   27  24  33  10  29  14
26  23  38  9   28  13  32  11
7   40  25  34  37  46  15  30
22  35  42  47  56  31  12  45
41  6   51  36  61  44  55  16
50  21  48  43  54  57  62  1
5   52  19  60  3   64  17  58
20  49  4   53  18  59  2   63``````
``````// C++ program
// Knight Tour problem using Warnsdorff's Heuristics
#include<iostream>
#include <time.h>
#include <stdlib.h>
#define N 8
using namespace std;

/*maintain the knight's position*/
int  move_cx[] = {1,1,2,2,-1,-1,-2,-2};
int  move_cy[]  = {2,-2,1,-1,2,-2,1,-1};

class MyBacktracking
{
public:
int x;
int y;

MyBacktracking()
{
//Make default initial location
this->x = 0;
this->y = 0;

}
/*Check whether move location is valid to chessboard*/
bool is_valid_move(int x, int y)
{
if ((x >= 0 && y >= 0) && (x < N && y < N))
{
return true;
}
return false;
}
/*Checks whether a square is empty or not */
bool is_empty(int out[], int x, int y)
{
if ((this->is_valid_move(x, y)) && (out[y *N + x] < 0))
{
return true;
}
return false;
}
/*Returns the number of empty squares */
int getcount(int out[], int x, int y)
{
int i, count = 0;
for (i = 0; i < N; ++i)
{
if (this->is_empty(out, (x + move_cx[i]), (y + move_cy[i])))
{
count++;
}
}
return count;
}
/*Calculates the minimum degree
And assigns the counter to that square */
bool move_process(int out[])
{
int start, count, i, flag = -1, c, min = (N + 1), nx, ny;
start =  rand()% N;
for (count = 0; count < N; ++count)
{
i = (start + count) % N;
nx = this->x + move_cx[i];
ny = this->y + move_cy[i];
if ((this->is_empty(out, nx, ny)))
{
c = this->getcount(out, nx, ny);
if (c < min)
{
flag = i;
min = c;
}
}
}
if (min == N + 1)
{
return false;
}
nx = this->x + move_cx[flag];
ny = this->y + move_cy[flag];
//Assigns the counter
out[ny *N + nx] = out[(this->y) *N + (this->x)] + 1;
this->x = nx;
this->y = ny;
return true;
}
/*Displays the chessboard with all the legal knight's moves */
void print_result(int out[])
{
int i, j;
for (i = 0; i < N; ++i)
{
for (j = 0; j < N; ++j)
{
cout << out[j *N + i] << "\t";
}
cout << "\n";
}
}
/*Checks its neighbouring sqaures */
bool neighbour(int start_x, int start_y)
{
int i;
for (i = 0; i < N; ++i)
{
if (((this->x + move_cx[i]) == start_x) && ((this->y + move_cy[i]) == start_y))
{
return true;
}
}
return false;
}
//Set default moves
void set_default(int out[])
{
//fill the chess board matrix with -1's
for (int i = 0; i < N *N; ++i)
{
out[i] = -1;
}
}
/*Display the legal moves using warnsdorff's heuristics */
bool generate(int out[])
{
this->set_default(out);
int i, sx, sy;
//Get a random starting location
sx =  rand()% N;
sy =  rand()% N;
this->x = sx;
this->y = sy;
//Set the value of first moves
out[this->y *N + this->x] = 1;
for (i = 0; i < (N *N) - 1; ++i)
{
if (this->move_process(out) == false)
{
return false;
}
}
if (this->neighbour(sx, sy) == false)
{
return false;
}
//When get a valid solution
this->print_result(out);
return true;
}
};
int main()
{
srand(time(NULL));
MyBacktracking obj =  MyBacktracking();
int out[N*N];
while (!obj.generate(out));
return 0;
}``````

#### Output

``````33 36  13  62  49  38  11  58
14  43  34  37  12  59  50  39
35  32  61  48  63  52  57  10
44  15  42  53  60  47  40  51
31  54  45  64  41  56  9   20
16  25  28  55  46  19  6   3
27  30  23  18  1   4   21  8
24  17  26  29  22  7   2   5``````
``````// Java program
// Knight Tour problem using Warnsdorff's Heuristics
import java.util.Random;
class MyBacktracking
{
public int size;
public int x;
public int y;
/*maintain the knight's position*/
public static int[] move_cx = {1,1,2,2,-1,-1,-2,-2};
public static int[] move_cy = {2,-2,1,-1,2,-2,1,-1};
public MyBacktracking()
{
//Make default initial location
x = 0;
y = 0;
size = 8;
}
/*Check whether move location is valid to chessboard*/
public boolean is_valid_move(int x, int y)
{
if ((x >= 0 && y >= 0) && (x < this.size && y < size))
{
return true;
}
return false;
}
/*Checks whether a square is empty or not */
public boolean is_empty(int[] out, int x, int y)
{
if ((is_valid_move(x, y)) && (out[y * this.size + x] < 0))
{
return true;
}
return false;
}
/*Returns the number of empty squares */
public int getcount(int[] out, int x, int y)
{
int i, count = 0;
for (i = 0; i < size; ++i)
{
if (is_empty(out, (x + move_cx[i]), (y + move_cy[i])))
{
count++;
}
}
return count;
}
/* Calculates the minimum degree
And assigns the counter to that square */
public boolean move_process(int[] out)
{
int start, count, i, flag = -1, c, min = (size + 1), nx, ny;
start = (int)(Math.random() * ((size)));
for (count = 0; count < size; ++count)
{
i = (start + count) % size;
nx = this.x + move_cx[i];
ny = this.y + move_cy[i];
if ((is_empty(out, nx, ny)))
{
c = getcount(out, nx, ny);
if (c < min)
{
flag = i;
min = c;
}
}
}
if (min == size + 1)
{
return false;
}
nx = this.x + move_cx[flag];
ny = this.y + move_cy[flag];
//Assigns the counter
out[ny * this.size + nx] = out[(this.y) * this.size + (this.x)] + 1;
this.x = nx;
this.y = ny;
return true;
}
/* Displays the chessboard with all the legal knight's moves */
public void print_result(int[] out)
{
int i, j;
for (i = 0; i < this.size; ++i)
{
for (j = 0; j < this.size; ++j)
{
System.out.print(out[j * this.size + i] + "\t");
}
System.out.print("\n");
}
}
/* Checks its neighbouring sqaures */
public boolean neighbour(int start_x, int start_y)
{
int i;
for (i = 0; i < this.size; ++i)
{
if (((this.x + move_cx[i]) == start_x) && ((this.y + move_cy[i]) == start_y))
{
return true;
}
}
return false;
}
//Set default moves
public void set_default(int[] out)
{
//fill the chess board matrix with -1's
for (int i = 0; i < size * size; ++i)
{
out[i] = -1;
}
}
/* Display the legal moves using warnsdorff's heuristics */
public boolean generate(int[] out)
{
set_default(out);
int i, sx, sy;
//Get a random starting location
sx = (int)(Math.random() * ((size)));
sy = (int)(Math.random() * ((size)));
this.x = sx;
this.y = sy;
//Set the value of first moves
out[this.y * size + this.x] = 1;
for (i = 0; i < (size * size) - 1; ++i)
{
if (move_process(out) == false)
{
return false;
}
}
if (neighbour(sx, sy) == false)
{
return false;
}
//When get a valid solution
print_result(out);
return true;
}
public static void main(String[] args)
{
MyBacktracking obj = new MyBacktracking();
//Used to store results
int[] out = new int[obj.size * obj.size];
while (!obj.generate(out));
}
}``````

#### Output

``````26 35  6   51  28  33  8   57
5   52  27  34  7   56  29  32
36  25  60  55  50  31  58  9
53  4   47  38  59  62  49  30
24  37  54  61  48  39  10  63
3   46  21  40  43  64  13  16
20  23  44  1   18  15  42  11
45  2   19  22  41  12  17  14  ``````
``````// C# program
// Knight Tour problem using Warnsdorff's Heuristics
using System;
class MyBacktracking
{
public int size;
public int x;
public int y;
/*Maintain the knight's position*/
public static int[] move_cx = {
1,
1,
2,
2,
-1,
-1,
-2,
-2
};
public static int[] move_cy = {
2,
-2,
1,
-1,
2,
-2,
1,
-1
};
public MyBacktracking()
{
//Make default initial location
x = 0;
y = 0;
size = 8;
}
/*Check whether move location is valid to chessboard*/
public Boolean is_valid_move(int x, int y)
{
if ((x >= 0 && y >= 0) && (x < this.size && y < size))
{
return true;
}
return false;
}
/*Checks whether a square is empty or not */
public Boolean is_empty(int[] output, int x, int y)
{
if ((is_valid_move(x, y)) && (output[y * this.size + x] < 0))
{
return true;
}
return false;
}
/*Returns the number of empty squares */
public int getcount(int[] output, int x, int y)
{
int i, count = 0;
for (i = 0; i < size; i++)
{
if (is_empty(output, (x + move_cx[i]), (y + move_cy[i])))
{
count++;
}
}
return count;
}
/* Calculates the minimum degree
And assigns the counter to that square */
public Boolean move_process(int[] output)
{
int start, count, i, flag = -1, c, min = (size + 1), nx, ny;
Random rand = new Random();
start = rand.Next(0, size);
for (count = 0; count < size; count++)
{
i = (start + count) % size;
nx = this.x + move_cx[i];
ny = this.y + move_cy[i];
if ((is_empty(output, nx, ny)))
{
c = getcount(output, nx, ny);
if (c < min)
{
flag = i;
min = c;
}
}
}
if (min == size + 1)
{
return false;
}
nx = this.x + move_cx[flag];
ny = this.y + move_cy[flag];
//Assigns the counter
output[ny * this.size + nx] = output[(this.y) * this.size + (this.x)] + 1;
this.x = nx;
this.y = ny;
return true;
}
/* Displays the chessboard with all the legal knight's moves */
public void print_result(int[] output)
{
int i, j;
for (i = 0; i < this.size; i++)
{
for (j = 0; j < this.size; j++)
{
Console.Write(output[j * this.size + i] + "\t");
}
Console.Write("\n");
}
}
/* Checks its neighbouring sqaures */
public Boolean neighbour(int start_x, int start_y)
{
int i;
for (i = 0; i < this.size; i++)
{
if (((this.x + move_cx[i]) == start_x) && ((this.y + move_cy[i]) == start_y))
{
return true;
}
}
return false;
}
//Set default moves
public void set_default(int[] output)
{
//fill the chess board matrix with -1's
for (int i = 0; i < size * size; i++)
{
output[i] = -1;
}
}
/* Display the legal moves using warnsdorff's heuristics */
public Boolean generate(int[] output)
{
set_default(output);
int i, sx, sy;
Random rand = new Random();
//Get a random starting location
sx = rand.Next(0, size);
sy = rand.Next(0, size);
this.x = sx;
this.y = sy;
//Set the value of first moves
output[this.y * size + this.x] = 1;
for (i = 0; i < (size * size) - 1; i++)
{
if (move_process(output) == false)
{
return false;
}
}
if (neighbour(sx, sy) == false)
{
return false;
}
//When get a valid solution
print_result(output);
return true;
}
public static void Main(String[] args)
{
MyBacktracking obj = new MyBacktracking();
int[] output = new int[obj.size * obj.size];
while (!obj.generate(output));
}
}``````

#### Output

``````37 32  1   16  53  30  11  14
2   17  38  31  12  15  52  29
39  36  33  64  45  54  13  10
18  3   46  55  34  63  28  51
47  40  35  44  59  50  9   24
4   19  58  49  56  25  62  27
41  48  21  6   43  60  23  8
20  5   42  57  22  7   26  61``````
``````<?php
class MyBacktracking
{
public \$size;
public \$x;
public \$y;
/*maintain the knight's position*/
public \$move_cx =[] ;
public \$move_cy =[] ;

function __construct()
{
//Make default initial location
\$this->x = 0;
\$this->y = 0;
\$this->size = 8;
\$this->move_cx = array(1, 1, 2, 2, -1, -1, -2, -2);
\$this->move_cy = array(2, -2, 1, -1, 2, -2, 1, -1);
}
/*Check whether move location is valid to chessboard*/
public  function is_valid_move(\$x, \$y)
{
if ((\$x >= 0 && \$y >= 0) && (\$x < \$this->size && \$y < \$this->size))
{
return true;
}
return false;
}
/*Checks whether a square is empty or not */
public  function is_empty( & \$out, \$x, \$y)
{
if ((\$this->is_valid_move(\$x, \$y)) && (\$out[\$y *\$this->size + \$x] < 0))
{
return true;
}
return false;
}
/*Returns the number of empty squares */
public  function getcount( & \$out, \$x, \$y)
{
\$count = 0;
for (\$i = 0; \$i < \$this->size; ++\$i)
{
if (\$this->is_empty(\$out, (\$x + \$this->move_cx[\$i]), (\$y + \$this->move_cy[\$i])))
{
\$count++;
}
}
return \$count;
}
/*Calculates the minimum degree
And assigns the counter to that square */
public  function move_process( & \$out)
{
\$start=0;
\$count=0;
\$i=0;
\$flag = -1;
\$c=0;
\$min = (\$this->size + 1);
\$nx=0;
\$ny=0;
\$start = rand(0, \$this->size);
for (\$count = 0; \$count < \$this->size; ++\$count)
{
\$i = (\$start + \$count) % \$this->size;
\$nx = \$this->x + \$this->move_cx[\$i];
\$ny = \$this->y + \$this->move_cy[\$i];
if ((\$this->is_empty(\$out, \$nx, \$ny)))
{
\$c = \$this->getcount(\$out, \$nx, \$ny);
if (\$c < \$min)
{
\$flag = \$i;
\$min = \$c;
}
}
}
if (\$min == \$this->size + 1)
{
return false;
}
\$nx = \$this->x + \$this->move_cx[\$flag];
\$ny = \$this->y + \$this->move_cy[\$flag];
//Assigns the counter
\$out[\$ny *\$this->size + \$nx] = \$out[(\$this->y) *\$this->size + (\$this->x)] + 1;
\$this->x = \$nx;
\$this->y = \$ny;
return true;
}
/*Displays the chessboard with all the legal knight's moves */
public  function print_result( & \$out)
{
\$i;
\$j;
for (\$i = 0; \$i < \$this->size; ++\$i)
{
for (\$j = 0; \$j < \$this->size; ++\$j)
{
echo(\$out[\$j *\$this->size + \$i] ."\t");
}
echo("\n");
}
}
/*Checks its neighbouring sqaures */
public  function neighbour(\$start_x, \$start_y)
{
\$i;
for (\$i = 0; \$i < \$this->size; ++\$i)
{
if (((\$this->x + \$this->move_cx[\$i]) == \$start_x) && ((\$this->y + \$this->move_cy[\$i]) == \$start_y))
{
return true;
}
}
return false;
}
//Set default moves
public  function set_default( & \$out)
{
//fill the chess board matrix with -1's
for (\$i = 0; \$i < \$this->size *\$this->size; ++\$i)
{
\$out[\$i] = -1;
}
}
/*Display the legal moves using warnsdorff's heuristics */
public  function generate( & \$out)
{
\$this->set_default(\$out);
//Get a random starting location
\$sx = rand(0, \$this->size);
\$sy = rand(0, \$this->size);
\$this->x = \$sx;
\$this->y = \$sy;
//Set the value of first moves
\$out[\$this->y *\$this->size + \$this->x] = 1;
for (\$i = 0; \$i < (\$this->size *\$this->size) - 1; ++\$i)
{
if (\$this->move_process(\$out) == false)
{
return false;
}
}
if (\$this->neighbour(\$sx, \$sy) == false)
{
return false;
}
//When get a valid solution
\$this->print_result(\$out);
return true;
}
}

function main()
{
\$obj = new MyBacktracking();
//Used to store results
\$out = array_fill(0, \$obj->size *\$obj->size, 0);
while (!\$obj->generate(\$out));
}
main();``````

#### Output

``````30 11  28  35  32  13  40  63
27  36  31  12  39  62  33  14
10  29  38  61  34  49  64  41
37  26  55  52  59  42  15  50
56  9   60  19  54  51  48  1
25  6   53  58  47  20  43  16
8   57  4   23  18  45  2   21
5   24  7   46  3   22  17  44``````
``````class MyBacktracking
{

constructor()
{
//Make default initial location
this.x = 0;
this.y = 0;
this.size = 8;
/*maintain the knight's position*/
this.move_cx = [1, 1, 2, 2, -1, -1, -2, -2];
this.move_cy = [2, -2, 1, -1, 2, -2, 1, -1]

}
/*Check whether move location is valid to chessboard*/
is_valid_move(x, y)
{
if ((x >= 0 && y >= 0) && (x < this.size && y < this.size))
{
return true;
}
return false;
}
/*Checks whether a square is empty or not */
is_empty(out, x, y)
{
if ((this.is_valid_move(x, y)) && (out[y *this.size + x] < 0))
{
return true;
}
return false;
}
/*Returns the number of empty squares */
getcount(out, x, y)
{
var i = 0;
var count = 0;
for (i = 0; i < this.size; ++i)
{
if (this.is_empty(out, (x + this.move_cx[i]), (y + this.move_cy[i])))
{
count++;
}
}
return count;
}
/*Calculates the minimum degree
And assigns the counter to that square */
move_process(out)
{
var start = 0;
var count = 0;
var i = 0;
var flag = -1;
var c = 0;
var min = (this.size + 1);
var nx = 0;
var ny = 0;
start = parseInt((Math.random() *((this.size))));
for (count = 0; count < this.size; ++count)
{
i = (start + count) % this.size;
nx = this.x + this.move_cx[i];
ny = this.y + this.move_cy[i];
if ((this.is_empty(out, nx, ny)))
{
c = this.getcount(out, nx, ny);
if (c < min)
{
flag = i;
min = c;
}
}
}
if (min == this.size + 1)
{
return false;
}
nx = this.x + this.move_cx[flag];
ny = this.y + this.move_cy[flag];
//Assigns the counter
out[ny *this.size + nx] = out[(this.y) *this.size + (this.x)] + 1;
this.x = nx;
this.y = ny;
return true;
}
/*Displays the chessboard with all the legal knight's moves */
print_result(out)
{
var i;
var j;
for (i = 0; i < this.size; ++i)
{
for (j = 0; j < this.size; ++j)
{
process.stdout.write(out[j *this.size + i] + "\t");
}
process.stdout.write("\n");
}
}
/*Checks its neighbouring sqaures */
neighbour(start_x, start_y)
{
var i = 0;
for (i = 0; i < this.size; ++i)
{
if (((this.x + this.move_cx[i]) == start_x) && ((this.y + this.move_cy[i]) == start_y))
{
return true;
}
}
return false;
}
//Set default moves
set_default(out)
{
//fill the chess board matrix with -1's
for (var i = 0; i < this.size *this.size; ++i)
{
out[i] = -1;
}
}
/*Display the legal moves using warnsdorff's heuristics */
generate(out)
{
this.set_default(out);
var i = 0;
var sx = 0;
var sy = 0;
//Get a random starting location
sx = parseInt((Math.random() *((this.size))));
sy = parseInt((Math.random() *((this.size))));
this.x = sx;
this.y = sy;
//Set the value of first moves
out[this.y *this.size + this.x] = 1;
for (i = 0; i < (this.size *this.size) - 1; ++i)
{
if (this.move_process(out) == false)
{
return false;
}
}
if (this.neighbour(sx, sy) == false)
{
return false;
}
//When get a valid solution
this.print_result(out);
return true;
}
}

function main(args)
{
var obj = new MyBacktracking();
//Used to store results
var out = Array(obj.size *obj.size).fill(0);
while (!obj.generate(out));
}
main();``````

#### Output

``````19 42  15  44  27  50  13  46
16  1   18  49  14  45  28  51
41  20  43  26  61  52  47  12
2   17  64  39  48  59  54  29
21  40  25  60  53  62  11  58
6   3   38  63  24  55  30  33
37  22  5   8   35  32  57  10
4   7   36  23  56  9   34  31``````
``````import random
class MyBacktracking :

def __init__(self) :
# Make default initial location
self.x = 0
self.y = 0
self.size = 8
# maintain the knight's position
self.move_cx = [1, 1, 2, 2, -1, -1, -2, -2]
self.move_cy = [2, -2, 1, -1, 2, -2, 1, -1]

# Check whether move location is valid to chessboard

def is_valid_move(self, x, y) :
if ((x >= 0 and y >= 0) and(x < self.size and y < self.size)) :
return True

return False

# Checks whether a square is empty or not

def is_empty(self, out, x, y) :
if ((self.is_valid_move(x, y)) and(out[y * self.size + x] < 0)) :
return True

return False

# Returns the number of empty squares

def getcount(self, out, x, y) :
i = 0
count = 0
i = 0
while (i < self.size) :
if (self.is_empty(out, (x + self.move_cx[i]), (y + self.move_cy[i]))) :
count += 1

i += 1

return count

# Calculates the minimum degree
#       And assigns the counter to that square

def move_process(self, out) :
start = 0
count = 0
i = 0
flag = -1
c = 0
min = (self.size + 1)
nx = 0
ny = 0
start = random.randint(0,self.size-1)
count = 0
while (count < self.size) :
i = (start + count) % self.size
nx = self.x + self.move_cx[i]
ny = self.y + self.move_cy[i]
if ((self.is_empty(out, nx, ny))) :
c = self.getcount(out, nx, ny)
if (c < min) :
flag = i
min = c

count += 1

if (min == self.size + 1) :
return False

nx = self.x + self.move_cx[flag]
ny = self.y + self.move_cy[flag]
# Assigns the counter
out[ny * self.size + nx] = out[(self.y) * self.size + (self.x)] + 1
self.x = nx
self.y = ny
return True

# Displays the chessboard with all the legal knight's moves

def print_result(self, out) :
i =0
j = 0
while (i < self.size) :
j = 0
while (j < self.size) :
print(out[j * self.size + i] ,"\t", end = "")
j += 1

print("\n", end = "")
i += 1

# Checks its neighbouring sqaures

def neighbour(self, start_x, start_y) :
i = 0
while (i < self.size) :
if (((self.x + self.move_cx[i]) == start_x) and((self.y + self.move_cy[i]) == start_y)) :
return True

i += 1

return False

# Set default moves
def set_default(self, out) :
# fill the chess board matrix with -1's
i = 0
while (i < self.size * self.size) :
out[i] = -1
i += 1

# Display the legal moves using warnsdorff's heuristics

def generate(self, out) :
self.set_default(out)
i = 0
sx = 0
sy = 0
# Get a random starting location
sx = random.randint(0,self.size-1)
sy = random.randint(0,self.size-1)
self.x = sx
self.y = sy
# Set the value of first moves
out[self.y * self.size + self.x] = 1
while (i < (self.size * self.size) - 1) :
if (self.move_process(out) == False) :
return False

i += 1

if (self.neighbour(sx, sy) == False) :
return False

# When get a valid solution
self.print_result(out)
return True

def main() :
obj = MyBacktracking()
out = [0] * (obj.size * obj.size)
while (not obj.generate(out)) :
pass

if __name__ == "__main__": main()``````

#### Output

``````5  8   23  38  51  10  25  28
22  37  6   9   24  27  50  11
7   4   39  54  43  52  29  26
36  21  44  41  58  55  12  49
3   40  63  56  53  42  59  30
20  35  18  45  64  57  48  13
17  2   33  62  15  46  31  60
34  19  16  1   32  61  14  47``````
``````# Ruby Program
# Knight Tour problem using Warnsdorff's Heuristics
class MyBacktracking
# Define the accessor and reader of class MyBacktracking
attr_reader :size,  :x,  :y,  :move_cx,  :move_cy
attr_accessor :size,  :x,  :y,  :move_cx,  :move_cy
def initialize()

# Make default initial location
@x = 0
@y = 0
@size = 8
# maintain the knight's position
@move_cx = [1, 1, 2, 2, -1, -1, -2, -2]
@move_cy = [2, -2, 1, -1, 2, -2, 1, -1]
end
# Check whether move location is valid to chessboard

def is_valid_move(x, y)

if ((x >= 0 && y >= 0) && (x < @size && y < @size))

return true
end
return false
end
# Checks whether a square is empty or not

def is_empty(out, x, y)

if ((self.is_valid_move(x, y)) && (out[y * @size + x] < 0))

return true
end
return false
end
# Returns the number of empty squares

def getcount(out, x, y)

i = 0
count = 0
while (i < @size)

if (self.is_empty(out, (x + @move_cx[i]), (y + @move_cy[i])))

count += 1
end
i += 1
end
return count
end
# Calculates the minimum degree
# And assigns the counter to that square

def move_process(out)

start = 0
count = 0
i = 0
flag = -1
c = 0
min = (@size + 1)
nx = 0
ny = 0
r = Random.new
start = r.rand(0...@size)
while (count < @size)

i = (start + count) % @size
nx = @x + @move_cx[i]
ny = @y + @move_cy[i]
if ((self.is_empty(out, nx, ny)))

c = self.getcount(out, nx, ny)
if (c < min)

flag = i
min = c
end
end
count += 1
end
if (min == @size + 1)

return false
end
nx = @x + @move_cx[flag]
ny = @y + @move_cy[flag]
# Assigns the counter
out[ny * @size + nx] = out[(@y) * @size + (@x)] + 1
@x = nx
@y = ny
return true
end
# Displays the chessboard with all the legal knight's moves

def print_result(out)

i = 0
j = 0
while (i < @size)

j = 0
while (j < @size)

print(out[j * @size + i] ,"\t")
j += 1
end
print("\n")
i += 1
end
end
# Checks its neighbouring sqaures

def neighbour(start_x, start_y)

i = 0
while (i < @size)

if (((@x + @move_cx[i]) == start_x) && ((@y + @move_cy[i]) == start_y))

return true
end
i += 1
end
return false
end
# Set default moves
def set_default(out)

# fill the chess board matrix with -1's
i = 0
while (i < @size * @size)

out[i] = -1
i += 1
end
end
# Display the legal moves using warnsdorff's heuristics

def generate(out)

self.set_default(out)
i = 0
sx = 0
sy = 0
r = Random.new
# Get a random starting location
sx =  r.rand(0...@size)
sy = r.rand(0...@size)
@x = sx
@y = sy
# Set the value of first moves
out[@y * @size + @x] = 1
while (i < (@size * @size) - 1)

if (self.move_process(out) == false)

return false
end
i += 1
end
if (self.neighbour(sx, sy) == false)

return false
end
# When get a valid solution
self.print_result(out)
return true
end
end
def main()

obj = MyBacktracking.new()
out = Array.new(obj.size*obj.size) {0}
while (!obj.generate(out))
end
end
main()``````

#### Output

``````8  5   36  63  22  3   20  53
35  62  7   4   37  54  23  2
6   9   48  59  64  21  52  19
47  34  61  38  55  50  1   24
10  39  58  49  60  25  18  51
33  46  31  40  43  56  15  26
30  11  44  57  28  13  42  17
45  32  29  12  41  16  27  14
``````
``````;
class MyBacktracking(var size: Int,
var x: Int,
var y: Int,
var move_cx: Array[Int],
var move_cy: Array[Int])
{

def this()
{
/*maintain the knight's position*/
this(8,0,0, Array(1, 1, 2, 2, -1, -1, -2, -2),
Array(2, -2, 1, -1, 2, -2, 1, -1))
}
/*Check whether move location is valid to chessboard*/
def is_valid_move(x: Int, y: Int): Boolean = {
if ((x >= 0 && y >= 0) && (x < size && y < size))
{
return true;
}
return false;
}
/*Checks whether a square is empty or not */
def is_empty(out: Array[Int], x: Int, y: Int): Boolean = {
if ((is_valid_move(x, y)) && (out(y * size + x) < 0))
{
return true;
}
return false;
}
/*Returns the number of empty squares */
def getcount(out: Array[Int], x: Int, y: Int): Int = {
var i: Int = 0;
var count: Int = 0;
while (i < size)
{
if (is_empty(out, (x + move_cx(i)), (y + move_cy(i))))
{
count += 1;
}
i += 1;
}
return count;
}
/*Calculates the minimum degree
And assigns the counter to that square */
def move_process(out: Array[Int]): Boolean = {
var start: Int = 0;
var count: Int = 0;
var i: Int = 0;
var flag: Int = -1;
var c: Int = 0;
var min: Int = (size + 1);
var nx: Int = 0;
var ny: Int = 0;
val r = new scala.util.Random
start = r.nextInt((size)-1);
while (count < size)
{
i = (start + count) % size;
nx = x + move_cx(i);
ny = y + move_cy(i);
if ((is_empty(out, nx, ny)))
{
c = getcount(out, nx, ny);
if (c < min)
{
flag = i;
min = c;
}
}
count += 1;
}
if (min == size + 1)
{
return false;
}
nx = x + move_cx(flag);
ny = y + move_cy(flag);
//Assigns the counter
out(ny * size + nx) = out((y) * size + (x)) + 1;
x = nx;
y = ny;
return true;
}
/*Displays the chessboard with all the legal knight's moves */
def print_result(out: Array[Int]): Unit = {
var i: Int = 0;
var j: Int = 0;
while (i < size)
{
j = 0;
while (j < size)
{
print(" " + out(j * size + i) + "\t");
j += 1;
}
print("\n");
i += 1;
}
}
/*Checks its neighbouring sqaures */
def neighbour(start_x: Int, start_y: Int): Boolean = {
var i: Int = 0;
while (i < size)
{
if (((x + move_cx(i)) == start_x) && ((y + move_cy(i)) == start_y))
{
return true;
}
i += 1;
}
return false;
}
//Set default moves
def set_default(out: Array[Int]): Unit = {
//fill the chess board matrix with -1's
var i: Int = 0;
while (i < size * size)
{
out(i) = -1;
i += 1;
}
}
/*Display the legal moves using warnsdorff's heuristics */
def generate(out: Array[Int]): Boolean = {
set_default(out);
var i: Int = 0;
var sx: Int = 0;
var sy: Int = 0;
val r = new scala.util.Random
//Get a random starting location
sx = r.nextInt((size)-1);;
sy = r.nextInt((size)-1);;
x = sx;
y = sy;
//Set the value of first moves
out(y * size + x) = 1;
while (i < (size * size) - 1)
{
if (move_process(out) == false)
{
return false;
}
i += 1;
}
if (neighbour(sx, sy) == false)
{
return false;
}
//When get a valid solution
print_result(out);
return true;
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyBacktracking = new MyBacktracking();
var out: Array[Int] = Array.fill[Int](obj.size * obj.size)(0);
while (!obj.generate(out))
{};
}
}``````

#### Output

`````` 15     36  3   44  31  34  5   42
2   45  14  35  4   43  30  33
37  16  1   48  51  32  41  6
46  13  52  39  64  57  50  29
17  38  47  58  49  40  7   60
12  53  20  63  56  59  28  25
21  18  55  10  23  26  61  8
54  11  22  19  62  9   24  27``````
``````import Foundation

#if os(Linux)
srandom(UInt32(time(nil)))
#endif
class MyBacktracking
{
var size: Int;
var x: Int;
var y: Int;
/*maintain the knight"s position*/
var move_cx: [Int] = [1, 1, 2, 2, -1, -1, -2, -2];
var move_cy: [Int] = [2, -2, 1, -1, 2, -2, 1, -1];
init()
{
//Make default initial location
self.x = 0;
self.y = 0;
self.size = 8;
}
/*Check whether move location is valid to chessboard*/
func is_valid_move(_ x: Int, _ y: Int) -> Bool
{
if ((x >= 0 && y >= 0) && (x < self.size && y < self.size))
{
return true;
}
return false;
}
/*Checks whether a square is empty or not */
func is_empty(_ out: [Int], _ x: Int, _ y: Int) -> Bool
{
if ((self.is_valid_move(x, y)) && (out[y * self.size + x] < 0))
{
return true;
}
return false;
}
/*Returns the number of empty squares */
func getcount(_ out: [Int], _ x: Int, _ y: Int) -> Int
{
var i: Int = 0;
var count: Int = 0;
while (i < self.size)
{
if (self.is_empty(out, (x + self.move_cx[i]), (y + self.move_cy[i])))
{
count += 1;
}
i += 1;
}
return count;
}
/*Calculates the minimum degree
And assigns the counter to that square */
func move_process(_ out: inout[Int]) -> Bool
{
var start: Int = 0;
var count: Int = 0;
var i: Int = 0;
var flag: Int = -1;
var c: Int = 0;
var min: Int = (self.size + 1);
var nx: Int = 0;
var ny: Int = 0;
#if os(Linux)
start =  Int(random()%(size))

#else
start =  Int( arc4random_uniform(size))
#endif
while (count < self.size)
{
i = (start + count) % self.size;
nx = self.x + self.move_cx[i];
ny = self.y + self.move_cy[i];
if ((self.is_empty(out, nx, ny)))
{
c = self.getcount(out, nx, ny);
if (c < min)
{
flag = i;
min = c;
}
}
count += 1;
}
if (min == self.size + 1)
{
return false;
}
nx = self.x + self.move_cx[flag];
ny = self.y + self.move_cy[flag];
//Assigns the counter
out[ny * self.size + nx] = out[(self.y) * self.size + (self.x)] + 1;
self.x = nx;
self.y = ny;
return true;
}
/*Displays the chessboard with all the legal knight"s moves */
func print_result(_ out: [Int])
{
var i: Int = 0;
var j: Int = 0;
while (i < self.size)
{
j = 0;
while (j < self.size)
{
print(out[j * self.size + i] ,"\t", terminator: "");
j += 1;
}
print("\n", terminator: "");
i += 1;
}
}
/*Checks its neighbouring sqaures */
func neighbour(_ start_x: Int, _ start_y: Int) -> Bool
{
var i: Int = 0;
while (i < self.size)
{
if (((self.x + self.move_cx[i]) == start_x) && ((self.y + self.move_cy[i]) == start_y))
{
return true;
}
i += 1;
}
return false;
}
//Set default moves
func set_default(_ out: inout[Int])
{
//fill the chess board matrix with -1"s
var i: Int = 0;
while (i < self.size * self.size)
{
out[i] = -1;
i += 1;
}
}
/*Display the legal moves using warnsdorff"s heuristics */
func generate(_ out: inout[Int]) -> Bool
{

var i: Int = 0;
var sx: Int = 0;
var sy: Int = 0;
//Get a random starting location
#if os(Linux)
sx =  Int(random()%(size))
sy =  Int(random()%(size))
#else
sx =  Int( arc4random_uniform(size))
sy =  Int( arc4random_uniform(size))
#endif
self.x = sx;
self.y = sy;
//Set the value of first moves
out[self.y * self.size + self.x] = 1;
while (i < (self.size * self.size) - 1)
{
if (self.move_process(&out) == false)
{
return false;
}
i += 1;
}
if (self.neighbour(sx, sy) == false)
{
return false;
}
//When get a valid solution
self.print_result(out);
return true;
}
}
func main()
{
let obj: MyBacktracking = MyBacktracking();
var out: [Int] = Array(repeating: -1, count: obj.size * obj.size);
while (!obj.generate(&out))
{
obj.set_default(&out);
};
}
main();``````

#### Output

``````58     33  38  15  60  19  2   17
37  14  59  34  39  16  61  20
32  57  36  53  62  1   18  3
13  54  47  56  35  40  21  64
48  31  52  41  46  63  4   25
9   12  55  28  51  24  43  22
30  49  10  7   42  45  26  5
11  8   29  50  27  6   23  44``````

## Resultant Output Explanation

``````
39  8   27  24  33  10  29  14
26  23  38  9   28  13  32  11
7   40  25  34  37  46  15  30
22  35  42  47  56  31  12  45
41  6   51  36  61  44  55  16
50  21  48  43  54  57  62  1
5   52  19  60  3   64  17  58
20  49  4   53  18  59  2   63
```
```

The resultant output represents a valid knight's tour on an 8x8 chessboard. Each number corresponds to the move number of the knight. The knight starts at position (5, 5) and follows a sequence of moves until it visits all the squares of the chessboard exactly once. The numbers are arranged in the order of the knight's moves.

## Time Complexity of the Code

The time complexity of Warnsdorff's algorithm for the knight's tour problem is O(N^2) in the worst case. This is because the algorithm performs a constant number of operations for each square on the chessboard, which has a total of N^2 squares.

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