n kraljic

Ukvarjam se s problemom kako spraviti n kraljic na sahovsko desko tako da se pri tem ne napadajo.Imam dve funkciji (ena pove ali je bila kraljica napadena ali ne, druga pa najde vse ugodne postavitve)

Generiral sem si tudi matriko ki naj bi služila kot šahovnica.

Sedaj pa ne vem kako bi naredil, da bi prvo kraljico vstavil jaz ostale kraljice pa bi vstavljal avtomatsko s pomocjo zgornjih dveh funkcij.

Teoretično naj bi slo nekako tako da v prvem koraku dam kraljico v 1.stolpec, v drugem koraku v drugi stolpec in tako naprej do n -tega stolpca.Stolpec sahovske deske je j=1,2,...,n, vrstica i pa pripada i-ti kraljici s čimer se izloči možnost da bi bile dve kraljici v isti vrstici.

Prosim če kdo ve rešitev oz.če je že delal kaj podobnega da mi svetuje kako naprej!

k=vrstica v kateri je k-ta kraljica
x[k]=oznacuje stolpec v katerem je k -ta kraljica


Hvala!!!

Nevone, razloz mu kako s Critticallom!!

Zadevo lahko resis kot je ze bilo omenjeno z evolucijskim algoritmom, lahko pa tudi uporabis rekurzijo in tehniko imenovano backtracking.

EDIT: Malo cudno deluje ta forum, sem dodal eno piko, pa mi kar ni prikazalo, uspelo sele v cetrtek poskusu.

 
 $DIMENSIONS X[280] Y[280]
 $SHOWVAR solutions
 $DECLAREINT x0 x1 x2 x3 x4 x5 x6 y0 y1 y2 y3 y4 y5 y6 zero upper dx dy i ok solutions
 $RETVAR X[] Y[]
 
 
 
 upper=7;
 upper--;
 zero=0;
 x0=0;x1=1;x2=2;x3=3;x4=4;x5=5;x6=6;
 
 for (y0=zero;y0<=upper;y0++) {
 for (y1=zero;y1<=upper;y1++) {
 dx=x1-x0;dx=abs(dx);dy=y1-y0;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 for (y2=zero;y2<=upper;y2++) {
 dx=x2-x0;dx=abs(dx);dy=y2-y0;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 dx=x2-x1;dx=abs(dx);dy=y2-y1;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 for (y3=zero;y3<=upper;y3++) {
 dx=x3-x0;dx=abs(dx);dy=y3-y0;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 dx=x3-x1;dx=abs(dx);dy=y3-y1;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 dx=x3-x2;dx=abs(dx);dy=y3-y2;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 for (y4=zero;y4<=upper;y4++) {
 dx=x4-x0;dx=abs(dx);dy=y4-y0;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 dx=x4-x1;dx=abs(dx);dy=y4-y1;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 dx=x4-x2;dx=abs(dx);dy=y4-y2;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 dx=x4-x3;dx=abs(dx);dy=y4-y3;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 for (y5=zero;y5<=upper;y5++) {
 dx=x5-x0;dx=abs(dx);dy=y5-y0;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 dx=x5-x1;dx=abs(dx);dy=y5-y1;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 dx=x5-x2;dx=abs(dx);dy=y5-y2;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 dx=x5-x3;dx=abs(dx);dy=y5-y3;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 dx=x5-x4;dx=abs(dx);dy=y5-y4;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 for (y6=zero;y6<=upper;y6++) {
 dx=x6-x0;dx=abs(dx);dy=y6-y0;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 dx=x6-x1;dx=abs(dx);dy=y6-y1;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 dx=x6-x2;dx=abs(dx);dy=y6-y2;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 dx=x6-x3;dx=abs(dx);dy=y6-y3;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 dx=x6-x4;dx=abs(dx);dy=y6-y4;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 dx=x6-x5;dx=abs(dx);dy=y6-y5;dy=abs(dy);
 ok=1;
 if (dx==zero) {ok=0;}
 if (dy==zero) {ok=0;}
 if (dx==dy) {ok=0;}
 if (ok!=zero) {
 X[i]=x0;Y[i]=y0;i++;X[i]=x1;Y[i]=y1;i++;X[i]=x2;Y[i]=y2;i++;X[i]=x3;Y[i]=y3;i++;X[i]=x4;Y[i]=y4;i++;X[i]=x5;Y[i]=y5;i++;X[i]=x6;Y[i]=y6;i++;
 solutions=i;
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 

Kaksni evolucijski algoritem in podobno sranje...

Evo ti celotno kodo napisano v C-ju:

/* Program prešteje na koliko načinov lahko na šahovnico n x n postavimo kraljice, tako da se ne napadajo */

#define MAX 20

static long kraljice(int );

main()
{
	int n;

	printf("Vnesite velikost sahovnice: ");
	scanf("%d", &n);

	printf("Stevilo postavitev kraljic: %d\n", kraljice(n));
}

static long kraljice(int n)
{
	int vrstica[MAX];  /* postavitev kraljic po posamzenih vrsticah */
	int stolpec[MAX];  /* evidenca o zasedenih stolpcih */

	int d1[2 * MAX -1], d2[2 * MAX -1];  /* diagonale */
	int i, j;
	long stevec = 0;    /* stevilo razlicnih postavitev */

	/* vse vrstice, stolpci in diagonale so prazni */
	for(i=0; i < n; ++i)
	{
		vrstica[i] = -1;
		stolpec[i] = 0;
	}

	for(i=0; i < 2 * n - 1; ++i) d1[i] = d2[i] = 0;

	i = 0;
	while(i >= 0){
	j = vrstica[i];
		if(j >= 0)
		  stolpec[j] = d1[n - i + j - 1] = d2[i + j] = 0;
		while(++j < n && (stolpec[j] || d1[n - i + j -1] || d2[i + j]));
		if(j == n)
		  vrstica[i--] = -1;
		else{
			vrstica[i] = j;
			stolpec[j] = d1[n - i +j -1] = d2[i + j] = 1;
			if(i == n - 1)
				++stevec;   /* vse kraljice so postavljene nova resitev */
			else
			    ++i;
			}
		}
		return stevec;
	}

Program deluje za šahovnico velikosti maksimalno 20 x 20. Pa že 20 x 20 dolgo računa.

Pa veselo programiranjne...

quaj to strict- c ?
neki zanakruh namazat?

saj tisto od maddogoda dela.
samo tales strict-c ne dela.

Mislim ... hehe ... se ti gre da tole ne bi delalo noraguta, da je že kar ganljivo.