Home » Interview coding problems/challenges

Warnsdorff's algorithm for Knight's tour problem

Warnsdorff's algorithm for Knight's tour problem: Here, we are going to learn to solve the problem Warnsdorff's algorithm for Knight's tour problem. Submitted by Souvik Saha, on February 07, 2020

Description:

This is a standard problem to implement Warnsdorff's algorithm for knight's tour problem using backtracking.

Problem statement:

Given a chess board and a knight is placed to any of the position of the chess. You have to find out either the knight will go through all the positions of the chess and if it is possible then print the total chess or not possible.

    Test cases T
    T no. of position will be given.

    E.g.
    3
    0 0
    0 4
    1 7

    Output:
    If it is possible for the knight to travel whole chess then 
    print the total matrix otherwise print "not possible to cover".

Example

    T=3

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

    Output:
    Not possible to cover.

Explanation with example:

Choosing the right part to cover the whole chess is a problem of combination and we will solve it through the backtracking process.

In chess, for a knight, there are several positions to mov­­e from a position.

Every time it will follow a route. When the knight will be struck then they will back and choose another path to go the all position of the chess.

For the position (0,0).

There are 8 points (1,2) (2,1) (2,-1) (1, -2) (-1,-2) (-2,-1) (-2,1) and (-1,2). In 8 points (2,-1) (1, -2) (-1,-2) (-2,-1) (-2,1) (-1,2) points are invalid. So we have to go either (1,2) or (2,1). We will choose any of them and then from that point will see the next 8 points and consider only the valid moves. If at any position no possible move will not possible then back to the previous move and from that go to the other path and stop if the step cont will be 64.

C++ implementation:

#include <bits/stdc++.h>
using namespace std;

int x[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int y[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };

bool is_safe(int a, int b)
{
    return (a >= 0 && a < 8 && b >= 0 && b < 8);
}

bool traverse(int pos_x, int pos_y, int count, int* arr, bool* visited)
{
    *(arr + pos_x * 8 + pos_y) = count;
    *(visited + pos_x * 8 + pos_y) = true;
    if (count == 64)
        return true;
    if (count > 64)
        return false;
    for (int i = 0; i < 8; i++) {
        int x_axis = pos_x + x[i];
        int y_axis = pos_y + y[i];
        if (is_safe(x_axis, y_axis) && *(visited + x_axis * 8 + y_axis) == false && traverse(x_axis, y_axis, count + 1, arr, visited)) {
            return true;
        }
    }
    *(arr + pos_x * 8 + pos_y) = 0;
    *(visited + pos_x * 8 + pos_y) = false;
    return false;
}

int main()
{
    int t;

    cout << "Test Case : ";
    cin >> t;

    while (t--) {
        int pos_x, pos_y;
        cout << "Enter the position : ";
        cin >> pos_x;
        cin >> pos_y;
        int count = 1;
        int arr[8][8] = { 0 };
        bool visited[8][8] = { false };
        //arr[pos_x][pos_y]=1;
        //visited[pos_x][pos_y]=true;
        if (traverse(pos_x, pos_y, count, &arr[0][0], &visited[0][0])) {
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    cout << arr[i][j] << " ";
                }
                cout << endl;
            }
        }
        else {
            cout << "not possible to cover" << endl;
        }
    }
    return 0;
}

Output

Test Case : 3

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

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

Enter the position : 1 7
not possible to cover