Knight's Tour

Given a starting position of a knight on an 8x8 chessboard, your task is to find a sequence of moves such that it visits every square exactly once.

On each move, the knight may either move two steps horizontally and one step vertically, or one step horizontally and two steps vertically.

Example:

Input:  y = 2, x = 1

Output:

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

Approach:

C++

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

//all eight directions
int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};

int grid[9][9];

int deg(int x1, int y1)
{
    int s = 0;
    for (int i = 0; i < 8; i++)
    {
        int x2 = x1 + dx[i];
        int y2 = y1 + dy[i];
        if (x2 >= 1 && x2 <= 8 && y2 >= 1 && y2 <= 8 && !grid[x2][y2])
            s++;
    }
    return s;
}
bool knightsTour(int mv, int x, int y)
{
    grid[x][y] = mv;

    //if at the last position
    if (mv == 64)
        return 1;
    vector<tuple<int, int, int>> v;
    for (int i = 0; i < 8; i++)
    {
        int x1 = x + dx[i], y1 = y + dy[i];

        //check for valid cell or not
        if (x1 >= 1 && x1 <= 8 && y1 >= 1 && y1 <= 8 && !grid[x1][y1])
        {
            int d = deg(x1, y1);
            v.push_back({d, x1, y1});
        }
    }
    sort(v.begin(), v.end());
    for (auto [d, x1, y1] : v)
    {
        if (knightsTour(mv + 1, x1, y1))
            return 1;
    }
    grid[x][y] = 0;
    return 0;
}
int main()
{
    int y = 2, x = 1;

    knightsTour(1, x, y);
    for (int i = 1; i < 9; i++)
    {
        for (int j = 1; j < 9; j++)
        {
            cout << grid[i][j] << " ";
        }
        cout << "\n";
    }
}