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