problem konika szachowego

Mam napisać program, który sprawdza czy danej szachownicy nxn możliwe jest przejście konikiem szachowym wszystkich pól (z pola 0,0)tak, że każde odwiedzam tylko raz. Wyprodukowałem coś takiego:

#include <iostream>

using namespace std;

int ruch =0;
void konik(bool **tab, int m, int n, int max);

int main()
{
    int n;
    bool **tab;
    cout<<"Podaj wymiar szachownicy ";
    cin>>n;
    tab= new bool*[n];
    for (int i=0;i<n;i++)
    {
        tab[i]=new bool[n];
    }
    for (int i=0;i<n;i++)
    {
        for(int k=0;k<n;k++)
        {
                tab[i][k]=0;
        }
    }
    for (int i=0;i<n;i++)
    {
        for(int k=0;k<n;k++)
        {
                cout<<tab[i][k];
        }
        cout<<endl;
    }
    konik(tab,0,0,n-1);
system("pause");
}
    
void konik(bool **tab, int m, int n, int max)
{
     ruch++;
     static int g;
     tab[m][n]=1;

     if((n-1)>=0&&(m-2)>=0&&tab[m-2][n-1]==0)
       konik(tab,m-2,n-1,max);
     if((n+1)<=max&&(m-2)>=0&&tab[m-2][n+1]==0)
       konik(tab,m-2,n+1,max);
     if((n+2)<=max&&(m-1)>=0&&tab[m-1][n+2]==0)
        konik(tab,m-1,n+2,max); 
     if((n+2)<=max&&(m+1)<=max&&tab[m+1][n+2]==0)                                            
        konik(tab,m+1,n+2,max);
     if((n+1)<=max&&(m+2)<=max&&tab[m+2][n+1]==0)
        konik(tab,m+2,n+1,max);
     if((n-1)>=0&&(m+2)<=max&&tab[m+2][n-1]==0)
        konik(tab,m+2,n-1,max);
     if((n-2)>=0&&(m+1)<=max&&tab[m+1][n-2]==0)
        konik(tab,m+1,n-2,max);
     if((n-2)>=0&&(m-1)>=0&&tab[m-1][n-2]==0)
        konik(tab,m-1,n-2,max);
          if(ruch==((max+1)*(max+1)))
     {
                              cout<<"Droga znaleziona";
                              g++;
                              cout<<g<<endl;
     }
     if(ruch-1<=0) 
     {
                   cout<<"Nie znaleziono drogi"<<endl;
     }
     ruch--;
     tab[m][n]=0;
     
}

Niby mi działa przy małych szachownicach, gdzie przejście na pewno nie jest możliwe wyświetla komunikat "nie znaleziono drogi" a przy szachownicy 6x6 taką drogę znajduje. Dziwne jest to natomiast, że gdy wprowadziłem zmienną g która liczy ilość znalezionych dróg w szachownicy 5x5 znajduje ich aż 305 co nie wydaje mi się możliwe. Innym problemem jest to, że już w szachonicy 7x7 na wynik trzeba trochę poczekać. Macie jakieś pomysły jak usprawnić algorytm by bez problem liczył tak do szachownicy n=8,9. Proszę o nie wklejanie jakiś kodów z innych stron. To sam mogę znaleźć, tylko o modyfikacje tego kodu albo o wskazanie błędów.

Algorytm rekurencyjny do tego problemu niestety działa wolno. Można go lekko usprawnić wybierając początkowo lepszą permutację ruchów (tzn w które strony konik ma skakać najpierw w które później).
Ale jest też algorytm znacznie szybszy, zachłanny. Polega na tym ze konik skacze na pole, z którego ma najmniej możliwości skoku.

No to i ja podziele się moimi spostrzeżeniami.

1. jak sam napisałeś zadaniem tego programu jest odpowiedź na pytanie czy dla danej szachownicy istnieje taka droga. Myśle że można pokazać że dla dowolnego n>4 taka droga zawsze istnieje (sprowadzając ten problem jakoś tam do problemu drogi Hamiltona, korzystając z tego że plansza/graf ma regularną strukturę), zatem IMO taki program staje się bezużyteczny. Co innego gdy chcesz wypisać taką ścieżkę lub wszystkie takie ścieżki, wtedy ma to sens.

2. tak jak napisał Shalom używasz dość prostego rekurencyjnego backtracka, można go usprawnić na kilka sposobów. Możesz skorzystać z takiej prostej obserwacji:

Niech puste pole (a,b) ma stopień d jeśli można "wskoczyć" na nie konikiem z d różnych pustych pól.
Jeżeli w pewnym momencie przeszukiwania istnieją 2 pola u,v każde stopnia = 1 oraz konik nie stoi teraz ani na u ani na v => robimy powrót.

Takie sprawdzanie na pewno mozna efektywnie zaimplementować zauważając że przy skoku zmieniają się stopnie conajwyżej 8 pustych pól.

aż 305 co nie wydaje mi się możliwe

Mój prologowy programik zliczył ich dla planszy 5x5 dokładnie 304, a więc ktoś tu kłamie:)

yurai rzeczywiście 304 pamięci to napisałem, nie wydawało mi się że możliwa jest aż tak duża liczba kombinacji dla tak małej planszy. Dzięki wielkie za za rady yurai i Shalom dowiedziałem się tego co chciałem ;)