×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

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.

Warnsdorff's algorithm for Knight's tour problem

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


Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.