Se consideră o tablă de şah având m/n câmpuri. Se plasează un cal în colţul din stânga sus. Calul se mişcă conform regulilor din şah. Se cere să se găsească toate variantele (dacă există) de a acoperi întreaga tablă, adică să se determine un număr de m*n-i mutări astfel încât fiecare câmp să fie vizitat o singură dată.


#include "stdio.h"
#include "conio.h"
//şirurile pentru cele 8 salturi
int a[8]={2,1,-1,-2,-2,-1,1,2}, b[8]={1,2,2,i,-1,-2,-2,-1};
//matricea t va conţine drumul
int t[10][10],m,n;
//funcţia de afişare a soluţiei
void afiseaza(void)
{
  int p,r;
  for(p=0;p < m;p++)   {     for(r=0;r < n;r++)     printf("%d",t[p][r]);   putchar("\n");   }   getch(); }
//funcţia recursivă de salt; i şi j sunt coordonatele din care
//sărim iar k numărul saltului
void cal(int i, int j, int k)
{
  int i1,j1,d;
  //incercăm fiecare din cele 8 posibilități de salt
  for(d=0;d < 8;d++)   {     //i1 este linia în care încercăm să sărim     i1=i+a[d];     //j1 este coloana în care încercăm să sărim     j1=j+b[d]     //dacă nu ieşim din tablă iar în punctul în care urmează să sărim     //nu am mai sărit în drumul curent (adică matricea t conţine     //valoarea 0) atunci     if((i1 < m)&&(j1 < n)&&(i1 >= 0)&&(!t[i1][j1]))
    {
      //sărim în punctul de cordonate (i1,j1)
      //şi marcăm în t saltul
      t[i1][j1]=k;
      //dacă nu am atins numărul de sărituri dorit apelăm recursiv
      //funcţia de salt pornind de la noul punct şi poziţia
      //următoare a saltului
      if(k < m*n)         cal(i1,j1,k+1);       else       //dacă am sărit de m*n-1 ori deci k este egal cu m*n       {         //afişăm soluţia         afiseaza();         //rând gol între soluţii         putchar("\n");         //marcăm pe o ultimul salt făcut pentru a permite         //întoarcerea din backtracking în vederea căutării         //unei noi soluţii         t[i1][j1]=0;         }       }     }   //s-au epuizat toate cele 8 posibile variante de salt, ne întoarcem   //din backtracking, punând pe o poziţia curentă   t[i1][j1]=0; } void main(void) {   int i,j;   printf("Introdu nr de linii: ");   scanf("%d",&m);   printf("Introdu nr de coloane: ");   scanf("%d",&n);   //inițializăm cu 0 valorile matricii drumului   for(i=0;i < m;i++)     for(j=0;j < n;j++)       t[i][j]=0;   //marcăm prima poziție (colțul din stânga sus) cu 1 ca primul salt   t[0][0]=1;   //facem saltul 2 porning din stânga sus   cal(0,0,2); }