Hát rég volt már poszt, de ezzel együtt ihlet is rég szállt meg.... :) Most viszont új erőre kapva a Mesterséges Intelligencia tárgytól a következő posztot ennek szentelem. A poszt témája az N királynő probléma. Tömören annyi a lényege hogy adott egy NxN-es sakktábla, ahova úgy kell felhelyezni N darab királynőt hogy nem üthetik egymást. Más szóval oszloponként és átlónként és soronként is csak 1 darab megengedett a királynőkből, ez szükséges de nem elégséges feltétele a dolognak!
A programom úgy működik hogy, elindul a sakktábla bal felső sarkából és N darab esetén NxN tesztesetet generál ami abból áll hogy leteszi az első helyre a királynőt és aztán az ütött mezők értékét 1-esre állítja. Utána megkeresi hogy melyek a szabad mezők, majd azok közül választ véletlenszerűen 1-et és oda rak le egy királynőt, és az általa ütött mezőket is 1-esre állítja, és megint keresi a szabadon maradt mezőket... Ez mind addig meg míg el nem fogynak a szabad mezők. Ha elfogyott a szabad mezők száma és N darab királynő van a táblán akkor talált egy megoldást a program és meg előre csak a soron következő mezőre rakja a királynőt és kezdi az egészet elölről, mindaddig míg nincs meg a megfelelő számú megoldás...Van viszont egy kis szépség hibája a proginak, mégpedig hogy semmi garancia nincs hogy a megoldások amiket talál nem egyeznek meg mert nincsenek rögzítve a megoldások az ellenőrzésre. Viszont kb 10 királynő esetén már elég kis eséllyel járja be ugyan azt az utat 2x, és a királynők számával ez még radikálisabban csökken. :)
4 Királynő esetén:
./nkir 4 2 <paraméterekkel indítva>
Ez a megoldas a 1. kör 3. teszesetében van!
Ez a 1. megoldasa a feladatnak!!
1 1 9 1
9 1 1 1
1 1 1 9
1 9 1 1
Ez a megoldas a 1. kör 9. teszesetében van!
Ez a 2. megoldasa a feladatnak!!
1 9 1 1
1 1 1 9
9 1 1 1
1 1 9 1
10 királynő esetén:
Ez a megoldas a 1. kör 16. teszesetében van!
Ez a 1. megoldasa a feladatnak!!
1 1 9 1 1 1 1 1 1 1
1 1 1 1 1 9 1 1 1 1
1 1 1 1 1 1 1 1 9 1
9 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 9 1 1
1 1 1 9 1 1 1 1 1 1
1 9 1 1 1 1 1 1 1 1
1 1 1 1 1 1 9 1 1 1
1 1 1 1 9 1 1 1 1 1
1 1 1 1 1 1 1 1 1 9
Ez a megoldas a 1. kör 24. teszesetében van!
Ez a 2. megoldasa a feladatnak!!
1 1 1 1 9 1 1 1 1 1
1 1 1 1 1 1 1 1 1 9
1 1 1 9 1 1 1 1 1 1
1 1 1 1 1 1 1 1 9 1
1 1 9 1 1 1 1 1 1 1
1 1 1 1 1 1 1 9 1 1
1 9 1 1 1 1 1 1 1 1
1 1 1 1 1 1 9 1 1 1
9 1 1 1 1 1 1 1 1 1
1 1 1 1 1 9 1 1 1 1
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int **sakktabla;
int *szabad_poz;
int kinok_szama;
int
lefoglal (int db)//létrehozzuk a sakktáblát
{
int i;
sakktabla = (int **) malloc (db * sizeof (int *));
for (i = 0; i < db; i++)
sakktabla[i] = (int *) malloc (db * sizeof (int));
return **sakktabla;
}
void
lenullaz (int db)//inicializáljuk a sakktáblát a kinullázással
{
int i, j;
for (i = 0; i < db; i++)
for (j = 0; j < db; j++)
{
sakktabla[i][j] = 0;
}
}
void
kiirat (int db)//kiprinteljük a sakktáblát!!!
{
int i, j;
for (i = 0; i < db; i++)
{
for (j = 0; j < db; j++)
printf ("%d ", sakktabla[i][j]);
printf ("\n");
}
}
void
kiloves (int ut, int db)//az ütött mezők "kilövése"
{
int sor, oszlop;
if (ut % db == 0)
{
sor = ((int) ut / db) - 1;
oszlop = ut - (sor * db) - 1;
}
else
{
sor = (int) ut / db;
oszlop = ut - (sor * db) - 1;
}
int i, j;
for (i = 0; i < db; i++)
sakktabla[sor][i] = 1;
for (i = 0; i < db; i++)
sakktabla[i][oszlop] = 1;
i = sor;
j = oszlop;
while (i < db && j < db)
{
sakktabla[i][j] = 1;
i++;
j++;
}
i = sor;
j = oszlop;
while (i >= 0 && j >= 0)
{
sakktabla[i][j] = 1;
i--;
j--;
}
i = sor;
j = oszlop;
while (i >= 0 && j < db)
{
sakktabla[i][j] = 1;
i--;
j++;
}
i = sor;
j = oszlop;
while (i < db && j >= 0)
{
sakktabla[i][j] = 1;
i++;
j--;
}
sakktabla[sor][oszlop] = 9;
}
void
szabad_nullaz (int db)//kinullázzunk a szabad elemeket tartalmazó tömböt
{
int i;
for (i = 0; i < (db * db); i++)
szabad_poz[i] = 0;
}
void
szabad_e (int db) //kigyűjtjük a szabad elemek pozícióját
{
int i, j, m;
m = 0;
for (i = 0; i < db; i++)
for (j = 0; j < db; j++)
if (sakktabla[i][j] == 0)
{
szabad_poz[m] = ((i * db) + j + 1);
m++;
}
}
void
szabad_kiirat (int db)//kiíratjuk a szabad pozíciókat
{
int i;
printf ("A szabadon maradt pozíciók: ");
for (i = 0; i < (db * db); i++)
if (szabad_poz[i] != 0)
printf ("%d ", szabad_poz[i]);
}
int
kiralynok_szama (int db)// a táblán lévő királynők számának meghatározása
{
int kinok_szama = 0;
int i, j;
for (i = 0; i < db; i++)
for (j = 0; j < db; j++)
if (sakktabla[i][j] == 9)
kinok_szama++;
return kinok_szama;
}
int
szabad_merete ()//megnézzük hány elem van a szabad_pozíciók tömbjében
{
int i = 0;
while (szabad_poz[i] != 0)
i++;
return i;
}
int
main (int argc, char *argv[])
{
int db, flag;
int s;
int veletlen;
int korok = 1;
int darabszam = 0;
unsigned int seed = (unsigned int) time (NULL);
srand (seed);
db = atoi (argv[1]);
flag = atoi (argv[2]);
szabad_poz = (int *) malloc ((db * db) * sizeof (int));
lefoglal (db);
printf ("Tehát akkor %d db. királynő ne üsse egymást a %d*%d-s táblán!\n", db, db, db);
while (1)
{
for (s = 1; s <= (db * db); s++)
{
lenullaz (db);
kiloves (s, db);
szabad_nullaz (db);
szabad_e (db);
while (szabad_poz[0] != 0)
{
veletlen = rand () % szabad_merete ();
kiloves (szabad_poz[veletlen], db);
szabad_nullaz (db);
szabad_e (db);
}
if (db == kiralynok_szama (db))
{
printf ("\nEz a megoldas a %d. kör %d. teszesetében van!\n", korok, s);
darabszam++;
printf ("Ez a %d. megoldasa a feladatnak!!\n", darabszam);
kiirat (db);
}
if (darabszam == flag)
break;
}
korok++;
if (darabszam == flag)
{
printf("Megvan az összes kívánt megoldás!!! Vége a programnak!!!\n\n");
break;
}
}
return 0;
}
