Backtracking – problema reginelor

Fiind dată o tablă de şah, de dimensiune n/n, se cer toate soluţiile de aranjare a n dame, astfel încât să nu se afle două dame pe aceeaşi linie, coloană sau diagonală (damele să nu se atace reciproc).


#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
int a[10],nr=0,n;
//funcţia de afişare a soluţiei
void scrie(void)
{
  int i;
  printf("Solutia numărul: %d\n",nr++);
  for(i=0;i < n;i++)   printf("Regina de pe linia %d pe coloana %d\n",(i+1),a[i]+1);   putchar("\n"); }
void reg(int i)
{
  int k,j,l;
  //în cazul în care am aşezat n regine am ajuns la soluţie
  if(i==n)
  {
    //afişăm soluţia
    scrie();
    putchar("\n");
    getch();
  }
  else
    //pentru fiecare nouă regină avem n posibile aşezări
    for(l=0;l < n;l++)     {       //încercăm să aşezăm regina i pe poziţia 1       a[i]=l;       //verificăm ca regina i să nu se atace cu nici o regină deja       //aşezată (deci cu fiecare din reginele de la 0 la i-1       for(k=j=0; j < i; j++)       //dacă găsim o regină pe aceeaşi coloană (deci a[i]==a[j])       //sau dacă se atacă pe diagonală (abs(a[i] -a[j])==(i-j))       //atunci facem pe k egal cu 1       if((a[i]==a[j]) || (abs(a[i]-a[j])==(i-j)))         k=1;     //dacă k=0 înseamnă că verificarea anterioară (a tuturor reginelor de     //la 0 la i-1 deja aşezate nu a găsit regine care să se atace cu     //regina i deci considerăm regina i aşezată şi apelăm funcţia     //recursivă încercând să aşezăm regina i+1     if(!k) reg(i+1);   } } void main(void) {   int j;   printf("Introd dimensiunea tablei:\n");   scanf("%d",&n);   for(j=0;j < n;j++)     a[j]=o;   //iniţializăm cu o vectorul ce reţine poziţia reginelor   reg(0);   //apelăm funcţia de aşezare a reginelor pornind de la regina 0 }

Leave a Reply