Probleme rezolvate cu solutie in plan
Aranjarea reginelor
Dându-se o tablă de şah de dimensiune nxn (n>3) să se aranjeze pe ea n regine fără ca ele să se atace. Reamintim că o regină atacă linia, coloana şi cele 2 diagonale pe care se află. În figura de mai jos celulele colorare mai închis sunt atacate de regina poziţionată unde indică litera “R”.
#include<iostream.h>
#include<math.h>
int x[100],n,nrsol;
void scriesol ()
{ int i,j;
nrsol++;
cout<<"Solutia a "<<nrsol<<" este";
for(i=1;i<=n;i++)
{ cout<<endl;
for(j=1;j<=n;j++)
if (x[j]==i) cout<<"X ";
else cout<<"O ";
}
}
int potcont(int k)
{ int i;
for(i=1;i<=k-1;i++)
if (x[i]==x[k] || k-i==abs(x[k]-x[i])) return 0;
return 1;
}
void back(int k)
{
int i;
for(i=1;i<=n;i++)
{
x[k]=i;
if (potcont(k))
if (k==n) scriesol();
else back(k+1);
}
}
void main()
{
cin>>n;
nrsol=0;
back(1);
cout<<nrsol<<" solutii";
}
Săritura calului
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.