DailyCodingProblem-Practice/Knight’s tour.cpp at master · RitikJainRJ/DailyCodingProblem-Practice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
using namespace std;

void knightTour(int);
bool _knightTour(int, int, int, int**, int);
bool isSafe(int, int, int**, int);

int main(){
    int t, n;

    cin >> t;
    while(t--){
        cin >> n;
        knightTour(n);
    }
    return 0;
}

void knightTour(int n){
    int **arr = new int*[n];
    bool res = false;

    for(int i = 0; i < n; i++)
        arr[i] = new int[n];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            arr[i][j] = -1;
    for(int k = 0; k < n; k++)
        for(int l = 0; l < n; l++){
            arr[k][l] = 0;
            if(_knightTour(k, l, 1, arr, n)){
                for(int i = 0; i < n; i++){
                    for(int j = 0; j < n; j++)
                        cout << arr[i][j] << "  ";
                    cout << endl;
                }
                res = true;
            }
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                    arr[i][j] = -1;
        }
    if(!res)
        cout << -1 << endl;
}

bool _knightTour(int x, int y, int move, int **arr, int n){
    if(move == n * n){
        return true;
    }

    int xMove[] = {2, 1, -1, -2, -2, -1, 1, 2};
    int yMove[] = {1, 2, 2, 1, -1, -2, -2, -1};
    for(int i = 0; i < 8; i++){
        int _x = x + xMove[i];
        int _y = y + yMove[i];
        if(isSafe(_x, _y, arr, n)){
            arr[_x][_y] = move;
            if(_knightTour(_x, _y, move + 1, arr, n))
                return true;
            arr[_x][_y] = -1;
        }
    }
    return false;
}

bool isSafe(int x, int y, int **arr, int n){
    if(0 <= x && x < n && 0 <= y && y < n && arr[x][y] == -1)
        return true;
    return false;
}