♞ Ce este Turul Calului?
Turul Calului (Knight's Tour) este problema de a muta un cal de șah pe o tablă N×N astfel încât să viziteze fiecare celulă exact o singură dată.
Pe o tablă 6×6 există mii de soluții care pornesc din colțul (0,0). Heuristica Warnsdorff găsește prima soluție aproape instant.
🐴 Mișcările Calului
Calul se mișcă în formă de "L": 2 pătrate într-o direcție și 1 pătrat perpendicular (sau invers).
(-2,-1)
(-2,+1)
(-1,-2)
(-1,+2)
(+1,-2)
(+1,+2)
(+2,-1)
(+2,+1)
🔁 Abordarea Backtracking + Warnsdorff
La fiecare pas, calul încearcă cele 8 mișcări posibile — dar le sortează după heuristica Warnsdorff: merge mai întâi spre celula cu cei mai puțini vecini disponibili. Astfel impasurile sunt evitate, reducând dramatic numărul de reveniri.
💻 Cod C++
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cal.in");
struct comp {int l,c;};
comp x[50], depl[10]={ {0,0} , {-2,1} ,{-1,2} ,{1,2} ,{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
int n , l0 , c0 , sol=0, d[10];
void CITIRE()
{
cin>>n;
cin>>l0>>c0;
x[1].l=l0;
x[1].c=c0;
}
void INIT(int k) { d[k]=0; }
int EXISTA(int k)
{
if(d[k]<8) return 1;
else return 0;
}
void VALPOS(int k)
{
x[k].l=x[k-1].l+depl[d[k]].l;
x[k].c=x[k-1].c+depl[d[k]].c;
}
int VALID(int k)
{
int i;
for(i=1;i<k;i++)
if((x[k].l==x[i].l)&&(x[k].c==x[i].c)) return 0;
if((x[k].l<1)||(x[k].c<1)||(x[k].l>n)||(x[k].c>n)) return 0;
return 1;
}
int SOLUTIE(int k)
{
if(k==n*n) return 1;
else return 0;
}
void TIPAR(int k)
{
int i; sol++;
cout<<"Solutia "<<sol<<":"<<endl;
for(i=1;i<=k;i++)
cout<<x[i].l<<"-"<<x[i].c<<" ";
cout<<endl<<endl;
}
void BCKG()
{
int k=2;
INIT(k);
while (k>1)
if(EXISTA(k)) {
d[k]++;
VALPOS(k);
if(VALID(k)) if(SOLUTIE(k)) TIPAR(k);
else {k++; INIT(k);}
}
else k--;
}
int main()
{
CITIRE();
BCKG();
}
Fiecare mutare = un nivel de recursivitate
Heuristica reduce backtrack-urile la aproape zero
🎯 Heuristica Warnsdorff
Regula: la fiecare pas, alege mutarea care duce în celula cu cei mai puțini vecini liberi (gradul cel mai mic). Celulele „de colț" au mai puține ieșiri — dacă le amânăm, riscăm să rămânem blocați mai târziu.
❌ Fără heuristică
Ordinea fixă a mutărilor → mii de backtrack-uri înainte de prima soluție
✅ Cu Warnsdorff
Soluția găsită aproape direct, cu 0–2 backtrack-uri pe tablă 5×5