Posted on June 21, 2021 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:

Initialize the chessboard matrix with -1's. This matrix will represent the knight's tour.
Choose a random starting location (sx, sy) on the chessboard.
Set the value of the first move at position (x, y) to 1.
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.

Check if the last position has a valid move back to the starting position. If not, return 0.
Print the resulting knight's tour.
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.

Warnsdorff’s algorithm for knight’s tour problem

Problem Statement

Pseudocode Algorithm with Explanation

Code Solution

Output

Output

Output

Output

Output

Output

Output

Output

Output

Output

Resultant Output Explanation

Time Complexity of the Code

Comment

New Comment