25 martie 2010

Problema reginelor

Pe o tablă NxN trebuie așezate N regine astfel încât să nu existe conflicte între oricare 2 piese (o regină poate elimina altă regină dacă segmentul determinat de cele două piese este paralel cu oricare din axele sau diagonalele tablei de joc).

In program, *s este vectorul care retine pe ce linie se afla fiecare regina pusa pe o singura coloana. Ex. s[1]=3 inseamna `regina de pe coloana 1 se afla pe linia 3`.

#include "stdio.h"
#include "stdlib.h"
#include "math.h"

int n , *s;
int vf;

void avans () {

vf++;
s[vf]=-1;

}

int succesor () {

s[vf]++;
return s[vf] < n;

}

int valid () {

int ok = 1;
int i;
for (i=0; i < vf; i++)
if(s[i]==s[vf] || abs(s[vf]-s[i])==vf-i)
ok=0;
return ok;
}

int sol () {

return vf==n-1;
}

void tipar () {

int i,j;
printf("solutie\n");
for(i=0; i < n; i++) {
for(j=0; j < n; j++) {
if(s[i]==j) printf("Q");
else printf("#"); }
printf("\n"); }
printf("\n");
}

void back() {

vf = -1;
avans ();
while(vf > -1) {
if(succesor()) {
if(valid()) { if(sol()) tipar();
else avans(); }
else ; }
else vf--; }
}

int main() {

printf("\n");
printf("n= ");
scanf("%d", &n);
s = (int *) malloc (n*sizeof(int));
back();
return 0;

}

Niciun comentariu: