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.