Bektreking

Pitanja i problemi
1

Treba da postavim n kraljica na tablu tako da se one medjusobno ne napadaju
zelim preko matrica da ga uradim tako da sam pokusao sledece:
#include
using namespace std;
int n=8,a[8][8]={};

void pisi()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cout<<a[i][j];
cout<<endl;
}
}

bool napadaju_se(int r,int p)
{

for(int i=0;i<r;i++)	
for(int j=0;j<n;j++)
{
		
if(a[i][j]==1) 
	{	

	if(p==j)
		return true;//napadaju se;

	for(int i1=i,j1=j;i1<=r && j1<n;i1++,j1++)
		if(i1==r && j1==p) 	
			return true;//napadaju se;
			

	for(int i1=i,j1=j;i1<=r && j1>=0;i1++,j1--)
		if(i1==r && j1==p) 
			return true;//napadaju se;
	}
}
return false;//ne napadaju se

}

void f(int b,int r,int p)
{
if(b==n)
{
pisi();
cout<<endl;
return;
}

if(napadaju_se(r,p)==false) 
{
	a[r][p]=1;
	f(b+1,r+1,0); //idem u sledeci red je r smo u jedan vec smestili kraljicu, pozicija krece od 0
}
else f(b,r,p+1); //pozicija se povecava

a[r][p]=0;//vracam na nulu ako slucaj gde kraljica zauzimma poziciju r p nije moguc

}

int main()
{
f(0,0,0);//brohj_kraljica_koje_smo_postavili \ red \ pozicija
}

moze li neko da pomogne sta mi fali

2

Izbaci onaj posledji parametar “p” i napravi iteraciju po kolonama u okviru funkcije f. takodje ti nije setiranje na 0 na pogrešnom mestu.

void f(int b,int r) {
    if(b==n) {
        pisi();
        cout<<endl;
        return;
    }
    for(int p = 0; p < n; p++) {
        a[r][p]=1;
        if(!napadaju_se(r,p))
            f(b+1,r+1);
        a[r][p]=0;
    }
}

a pošto ti ima i “b” i “r” uvek istu vrednost možeš i da izbaciš jedan od ta dva parametra

void f(int k) {
    if(k==n) {
        pisi();
        cout<<endl;
        return;
    }
    for(int p = 0; p < n; p++) {
        a[k][p]=1;
        if(!napadaju_se(k,p))
            f(k+1);
        a[k][p]=0;
    }
}

A nema potrebe da držiš to u obliku matrike. Dovoljno ti je array x[0…n] gde su vrednosti pozicije kraljice u nekoj koloni (0…n). Onda ti je proveravanje napadanja i-te i j-te kraljice mnogo jednostavnije. x[i] == x[j] or abs(i - j) == abs(x[i] - x[j]).

1 Like
3

Hvala jasno je