Problema en encontrar el número de todos los caminos desde (0,0) hasta (n,n) visitando cada casilla exactamente una vez.

Estoy tratando de aprender sobre el retroceso y me he encontrado con el problema descrito en el título. He utilizado un conjunto visited para llevar un registro de todos los casilleros que he visitado. He escrito el siguiente código, pero parece que no funciona. Siempre termino teniendo algunos casilleros no visitados. Por favor ayúdame.

“`cpp
#include <bits stdc++.h="">

using namespace std;

int n = 4;
int cnt;

using coords = pair<int, int="">;

bool inGrid(coords pos)
{
return (pos.first < n && pos.first >= 0 && pos.second >= 0 && pos.second < n) ? true : false;
}

set<coords> possibleSteps(coords pos)
{
set<coords> sc;
sc.insert({pos.first, pos.second + 1});
sc.insert({pos.first, pos.second – 1});
sc.insert({pos.first + 1, pos.second});
sc.insert({pos.first – 1, pos.second});
return sc;
}

void search(int steps, coords pos, set<coords> visited)
{
if (pos == coords{n – 1, n – 1} && steps == n * n – 1)
{
++cnt;
return;
}
visited.insert(pos);
auto pSteps = possibleSteps(pos);
for (auto &s : pSteps)
{
if (inGrid(s) && !visited.count(s))
search(steps + 1, s, visited);
}
}

int main()
{
cout << "Ingrese la dimensión de la cuadrícula n = ";
cin >> n;
set<coords> visited;
search(0, {0, 0}, visited);
cout << cnt;
return 0;
}
“`</int,>