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

#include <iostream>
#include <stdlib.h>
#include <time.h>
 
using namespace std;
 
int const n = 8;
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;
}
 
bool NonCross ( int x, int y)
{
    return Moves(x,y) &&
}
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 vuvod(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;
}

#include <iostream>
#include <vector>
#include <thread>
#include <future>
#include <atomic>
#include <string>
 
typedef std::pair<int, int> vec; // точка
typedef std::pair<vec, vec> segment; // отрезок
 
const int n = 6; // размер доски
const int limit = n / 2 + n % 2; // нужно для пропуска клеток, результат которых симметричен
thread_local std::vector<vec> steps, longest; // текущий и самый длинный путь
std::atomic_int counter = 0; // счётчик проверенных клеток для многопоточности
 
// Перегрузка вывода для красоты
std::ostream& operator<<(std::ostream& out, const vec& p)
{
    return out << static_cast<char>('A' + p.first) << (p.second + 1);
}
 
// Сумма векторов
vec operator+(vec lhs, vec rhs)
{
    return vec(lhs.first + rhs.first, lhs.second + rhs.second);
}
 
// Разница векторов
vec operator-(vec lhs, vec rhs)
{
    return vec(lhs.first - rhs.first, lhs.second - rhs.second);
}
 
// Векторное произведение
int cross(const vec& p1, const vec& p2)
{
    return p1.first * p2.second - p2.first * p1.second;
}
 
// Знак без учёта нуля, ага
int sign(int number)
{
    return number < 0 ? -1 : 1;
}
 
// Проверка перечесения двух отрезков
bool crossing(const segment& s1, const segment& s2)
{
    vec cut;
    int prod1, prod2;
 
    cut = s1.second - s1.first;
    prod1 = cross(cut, s2.first - s1.first);
    prod2 = cross(cut, s2.second - s1.first);
    
    if (sign(prod1) == sign(prod2) || prod1 == 0 || prod2 == 0)
        return false;
 
    cut = s2.second - s2.first;
    prod1 = cross(cut, s1.first - s2.first);
    prod2 = cross(cut, s1.second - s2.first);
 
    if (sign(prod1) == sign(prod2) || prod1 == 0 || prod2 == 0)
        return false;
 
    return true;
}
 
void recursion(vec point)
{
    // Проверка на выход за пределы поля
    bool valid = point.first >= 0 && point.first < n && point.second >= 0 && point.second < n;
 
    // Проверка на пересечение отрезков и повторное использование клеток
    if (valid && !steps.empty())
    {
        // Проверка с конца чтобы сразу отсекать 1/8 ходов
        valid = point != steps.back();
 
        segment seg(steps.back(), point);
 
        for (size_t i = steps.size() - 1; i > 0 && valid; i--)
            valid = point != steps[i - 1] && !crossing(segment(steps[i - 1], steps[i]), seg);
    }
 
    // Если проверка не пройдена - сохранить самый длинный путь и выйти
    if (!valid)
    {
        if (steps.size() > longest.size())
            longest = steps;
        return;
    }
 
    // Добавление текущей точки в путь
    steps.push_back(point);
 
    // Все варианты хода
    static vec offsets[8] = { 
        vec( 2, 1), vec( 2, -1), 
        vec(-2, 1), vec(-2, -1),
        vec( 1, 2), vec( 1, -2),
        vec(-1, 2), vec(-1, -2)
    };
    // Проверка всех путей
    for (int i = 0; i < 8; i++)
        recursion(point + offsets[i]);
 
    // Извлечение текущей точки из пути
    steps.pop_back();
}
 
#define MULTITHREADING
 
std::vector<vec> checker(unsigned thread_id, unsigned thread_count)
{
    unsigned k = 0;
    for (int i = 0; i < limit; i++)
    {
        for (int j = i; j < limit; j++)
        {
            if (k == thread_id)
            {
                recursion(vec(i, j));
                std::cout << '\r' + std::to_string(++counter);
            }
            k = (k + 1) % thread_count;
        }
    }
    return longest;
}
 
int main()
{
#ifndef MULTITHREADING
    for (int i = 0; i < limit; i++)
    {
        for (int j = i; j < limit; j++)
        {
            std::cout << "\rCurrent start pos: " << i << ' ' << j;
            recursion(vec(i, j));
        }
    }
#else
    // Поддерживаемое количество потоков
    unsigned thread_count = std::thread::hardware_concurrency();
    if (thread_count == 0)
        thread_count = 1;
 
    // Количество обработанных клеток
    std::cout << 0;
 
    // Запуск потоков
    std::vector<std::future<std::vector<vec>>> futures;
    futures.reserve(thread_count);
    for (unsigned i = 0; i < thread_count; i++)
        futures.push_back(std::async(std::launch::async, checker, i, thread_count));
 
    // Ожидание завершения работы потоков и поиск самого длинного пути
    for (unsigned i = 0; i < thread_count; i++)
    {
        steps = futures[i].get();
        if (steps.size() > longest.size())
            longest.swap(steps);
    }
#endif // ! MULTITHREADING
 
    // Куча пробелов чтобы затереть вывод прогресса
    std::cout << "\r" << longest.size() - 1 << " steps.              " << std::endl;
 
    // Выводим путь
    std::cout << longest[0];
    for (size_t i = 1; i < longest.size(); i++)
        std::cout << '-' << longest[i];
    std::cout << std::endl;
}