Найти самый длинный несамопересекающийся путь коня на доске с помощью рекурсивного алгоритма

В общем, требуется ваша помощь. Необходимо написать программу. Единственное, что я смог сделать:

#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;

int const n = 6;
int Doska[n][n];
int x0,
    y0;

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

bool CanStep(int x, int y)
{
    return x >= 0 && y >= 0 && x < n && y < n;
}

bool Moves(int x, int y)
{
    return CanStep(x, y) && Doska[x][y] == 0;
}

void Gen (int Doska[n][n], int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            Doska[i][j] = 0;
        }
    }
}

void pokaz(int Doska[n][n], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << "---------------------------------" << endl;
        for (int j = 0; j < n; j++)
        {
            if (j < n - 1)
                cout << "|" << " " << Doska[i][j] << " ";
            else
                cout << "|" << " " << Doska[i][j] << " " << "|";
        }
        cout << endl;
    }
    cout << "---------------------------------" << endl;
}

Здесь только наброски программы. Как я хотел сделать: матрица 6 на 6, заполненная 0 элементами.. Когда конь ходит, менять элемент, на который он сходил с 0 на 1, плюс суммировать счётчик. И в конце вывести этот счётчик( длину пути). Но несколько проблем:

1. Я не знаю, как реализовать алгоритм ходьба коня с помощью рекурсива.
2. Я не понимаю, что значит несамопересекаемость и как её проверить ( вот пример на скрине). Что вообще подразумевается под путём в данной задачи?
3. Я впервые сталкиваюсь с таким видом задач, поэтому совершенно не понимаю, как это реализовать. Поэтому пока просто беру задачи с похожих тем и пытаюсь их переделать.