Problema comis-voiajorului

Un comis voiajor trebuie să viziteze un număr n de oraşe. Iniţial, el se află într-unul dintre ele, notat 1. Comis voiajorul doreşte să nu treacă de două ori prin acelaşi oraş, iar la întoarcere să revină în oraşul din care a plecat. Cunoscând legăturile existente între oraşe, se cere să se tipărească toate drumurile posibile pe care le poate efectua comis voiajorul.Drumurile dintre orase sunt date sub forma unei matrici a[i][j]=1 daca intre orasul i si j exista drum si a[i][j]=0 daca nu exista drum intre orasul i si orasul j.

 

#include<iostream.h>
#include<conio.h>
#include<math.h>
int st[20],n,k,a[10][10];

void init()
{st[k]=1;}

int succesor()
{if (st[k]<n)
{st[k]++;
return 1;
}
else return 0;}

int valid()
{if( a[st[k-1]][st[k]]==0) return 0;
for(int i=1;i<k;i++)
if(st[i]==st[k] ) return 0;
if((k==n) && (a[1][st[k]]==0)) return 0;
return 1;}

int sol()
{return (k==n);}

void tipar()
{for(int i=1;i<=n;i++) cout<<st[i]<<" ";
cout<<endl;
}

void bkt()
{int as;k=2;
init();
while(k>0)
{
do {} while ((as=succesor()) && !valid());
if (as)
if (sol()) tipar();
else {k++;init();}
else k--;
}
}

void main()
{cout<<"numarul de orase=";cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) cin>>a[i][j];
st[1]=1;
bkt();
}