Fiind dată o tablă de şah de dimensiunea nxn şi un cal în colţul stânga sus al acesteia, se cere să se afişeze toate posibilităţile de mutare a acestei piese de şah astfel încât să treacă o singură dată prin fiecare pătrat al tablei. O soluţie va fi afişată ca o matrice nxn în care sunt numerotate săriturile calului.
Exemplu, pentru n=5, o soluţie este
1 14 9 20 23
10 19 22 15 8
5 2 13 24 21
18 11 4 7 16
3 6 17 12 25
Pentru rezolvarea acestei probleme vom codifica direcţiile de deplasare pentru că ar fi ineficient să scriem două cicluri for de la –2 la 2 cu cele 25 de variante de deplasare din care valide sunt doar opt. De asemenea aici spre deosebire de celelalte probleme tratate la aplicarea metodei backtracking în plan nu vom folosi un vector soluţie, ci vom scrie săriturile în tablou urmărind ca la revenire să refacem poziţiile ocupate pentru a nu se lua blocaje. În figura de mai jos sunt prezentate cele 8 mutări posibile pentru un cal.
#include <iostream>
#include<fstream>
const int dx[8]={-1,1,2,2,1,-1,-2,-2};
const int dy[8]={-2,-2,-1,1,2,2,1,-1};
int a[10][10],n;
ofstream f(„cal.out”);
void afis()
{ int i,j;
for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++) f<<a[i][j]<<” „;
f<<endl;
}
f<<endl;
}
int inside(int i,int j)
{
return i>=1 && i<=n && j>=1 && j<=n;
}
void back(int i, int j, int pas)
{ int k,inou,jnou;
a[i][j]=pas;
if (pas==n*n) afis();
else for(k=0;k<8;k++)
{ inou=i+dx[k];
jnou=j+dy[k];
if (inside(inou,jnou) && a[inou][jnou]==0)
back(inou,jnou,pas+1);
}
a[i][j]=0;
}
void main()
{ cin>>n;;
back(1,1,1);
}