Razmotrite omiljeni problem za razumijevanje algoritama, problem osam kraljica. Klasična definicija: "postavi 8 dama na šahovsku tablu tako da nijedna od njih ne pobijedi drugu." Ok, problem je vrlo popularan u raznim intervjuima, a Wikipedia nam odmah daje rješenje u mom omiljenom Pythonu.

I to je sigurno ispravno rješenje sa stanovišta obicna osoba, ali apsolutno besmisleno sa hakerske tačke gledišta, a ja ću vam reći zašto:

Analizirajmo algoritam: koristi se klasično pretraživanje unazad, područje rješenja predstavljamo u obliku grafa, čiji je svaki vrh pozicija dame u kojoj ona nije napadnuta i ne pobjeđuje dame koje su već postavljene na tabla, tj. samo trebamo sakupiti sve "grane" koje se sastoje od tačno osam vrhova. Kao metodu za traženje ovih „grana“, autor nam nudi klasični algoritam pretrage u širinu, tj. redoslijed prelaska grafa će izgledati ovako:

I čim algoritam proradi, dobićemo sva moguća rješenja.

U čemu je problem? U našem slučaju, za ploču 8x8, dobićemo 92 različita rješenja, a zamislite to, kao što se često dešava u stvarni problemi, ne znamo veličinu ploče. Ako je ploča 25x25, kao u Tai Shogi, tada će broj rješenja već biti 275,986,683,743,434.

Tabela koja pokazuje ovisnost broja rješenja o veličini ploče:

Šta će to značiti za naš scenario? A činjenica da će ići u veoma dugu potragu i pošto će sve odluke morati da drži u glavi, za samo 15 minuta Python će pojesti 300 megabajta memorije. Ko ima moćan procesor i veliki volumen ram memorija mogu provjeriti da li će se ovaj proces uopće završiti...

A sve što nam je trebalo da riješimo takav problem je da odaberemo ispravan algoritam za prelazak preko grafa, što bi u našem slučaju bila redovna pretraga u dubinu, a zatim bi se graf prelazio ovim redoslijedom:

I kod bi bio mnogo jednostavniji, pa čak i nakon 15 minuta skripta bi potrošila točno istu količinu memorije kao sekundu nakon pokretanja. A ovako bi izgledala njegova implementacija u Pythonu:

Def rc_queens(n_col, width, sol): if len(sol) == width: print sol else: za n_row u rasponu(width): if (safe_queen(n_row, n_col, sol)): rc_queens(n_col+1, width , sol+) def safe_queen(new_row, new_col, sol): za col u rasponu(len(sol)): if (sol == novi_red ili abs(col - new_col) == abs(sol - new_row)): vrati 0 return 1 ako __name__ == "__main__": za n u rasponu(8): rc_queens(1, 8, [n])
P.S. Ovo je samo hakersko viđenje problema, možda neko može ponuditi pogled na "teorijsku informatiku"?

Prije par mjeseci sam se pojavio sa analizom klasični problem o rasporedu dama na šahovskoj tabli (pogledajte detalje i istoriju ispod). Problem je nevjerovatno poznat i već je ispitan pod mikroskopom, pa je bilo iznenađujuće da se pojavilo nešto zaista novo.

(ovdje je maksimalan broj dama, a na mjesto krsta možete staviti bijelu, a na mjesto crne tačke - ali ne obje odjednom; preuzeto iz članka)

Modeli i složenost problema

Došlo je vrijeme da se zapravo razgovara: kako sve to riješiti i koliko brzo se to može učiniti?

Linearno traženje klasičnog problema

Većina zanimljiva poenta da se čak i stručnjaci ponekad zbune i misle da rješavanje N-kraljica zahtijeva kombinatorno pretraživanje i misle da je složenost problema veća od P. Jednom sam pisao o tome šta su P i NP na Habréu: i. Međutim, problem je riješen bez preterivanja opcije! Odnosno, za dasku bilo koje veličine, uvijek možete poredati dame jednu iza druge ljestve:

Otuda zaključak da za N = 1 i N > 3 uvijek postoji rješenje (vidi algo), a za N = 2 ili N = 3
uvijek ne (trivijalno slijedi sa ploče). To znači da se problem rješivosti za N kraljica (gdje treba reći da li postoji rješenje ili ne) rješava trivijalno u konstantnom vremenu (u redu, konstruktivno u linearnom vremenu - uredi/provjeri).

Vrijeme je da još jednom provjerite ono što ste pročitali, čitamo tipičan naslov "problem N kraljica je prepoznat kao NP-kompletan problem" - jesu li vam se oči zacaklele?

Kako računati broj rješenja u praksi

Ovdje počinje zabava: broj rješenja za problem postavljanja matice čak ima i svoje ime - "sekvenca A000170". Na ovom dobre vijesti se završavaju. Složenost problema: veća od NP i P#, u praksi to znači da je optimalno rješenje preuzimanje podataka sekvence u rječnik i vraćanje željenog broja. Pošto je za N=27 već izračunato na paralelnom klasteru za koliko sedmica.

Rješenje: napiši znak i n po n, vrati a(n)
n a(n)
1: 1
2: 0
3: 0
4: 2
5: 10
6: 4
7: 40
8: 92
9: 352
10: 724
…
21: 314666222712
22: 2691008701644
23: 24233937684440
24: 227514171973736
25: 2207893435808352
26 22317699616364044
27: 234907967154122528

Međutim, ako imate neku škakljivu vrstu problema i još uvijek trebate prebrojati rješenja (a njihov broj je nepoznat i niko ih ranije nije brojao), onda najbolja opcija O prototipu se govori u nastavku.

Programiranje N komplementa i skupa odgovora

Ovdje počinje najzanimljiviji dio: od čega se sastoji? novi rezultatčlanci? Problem komplementa N matica je NP-kompletan! (Zanimljivo je da je NP-potpunost komplementa latinskog kvadrata bila poznata još 1984. godine.)

Šta to znači u praksi? Najlakši način da riješite ovaj problem (ili iznenada, ako nam zatreba njegova varijacija) je korištenje SAT-a. Međutim, više mi se sviđa sljedeća analogija:

SAT je asembler za kombinatorne NP probleme, a programiranje skupa odgovora (ASP) je C++ (ASP također ima misterioznu rusku dušu: ponekad je zbunjujući i nepredvidiv za neupućene; usput, teorija koja leži u osnovi modernog ASP-a je izmišljena u 1988. od strane Mihaila Gelfonda i Vladimira Lifšica, koji su tada radili na univerzitetima u Teksasu i Stanfordu).

Jednostavno rečeno: ASP je deklarativni programski jezik za ograničenja (ograničenja u engleskoj literaturi) sa Prolog sintaksom. Odnosno, zapišemo koja ograničenja rješenje mora zadovoljiti, a sistem sve svodi na SAT opciju i nađe nam rješenje.

Detalji rješenja ovdje nisu toliko važni, a programiranje skupa odgovora je vrijedno posebnog posta (koji je nedolično dugo u mom nacrtu): pa pogledajmo konceptualne točke

% domenskog reda(1..n). stupac(1..n). % sverazličitih 1 (dama(X,Y) : stupac(Y) ) 1:- red(X). 1 ( kraljica(X,Y) : red(X) ) 1:- kolona(Y). % ukloniti konfliktne odgovore:- dama(X1,Y1), dama(X2,Y2), X1< X2, Y1 == Y2. :- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 + X1 == Y2 + X2. :- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 - X1 == Y2 - X2.

Red 1 ( kraljica(X,Y) : kolona(Y) ) 1:- red(X). - naziva se pravilom izbora i određuje šta je valjani prostor pretraživanja.

Posljednja tri reda nazivaju se ograničenja integriteta: i oni definiraju koja ograničenja mora zadovoljiti rješenje: ne može biti dama u istom redu, ne može biti dama u istom stupcu (izostavljeno zbog simetrije) i ne može biti dama na istoj dijagonali.

Preporučujem Clingo kao sistem za eksperimentisanje.
I za početak, vrijedi pogledati njihov vodič i pročitati njihov blog na www.hakank.org.

Naravno, ako prvi put pišete u ASP-u, tada prvi model neće biti nevjerovatno efikasan i brz, ali će najvjerovatnije biti brži od grube sile s povratom napisanim u brzo rešenje. Međutim, ako razumijete osnovne principe sistema, ASP može postati "regexp za NP-kompletne probleme".

Provedimo jednostavan numerički eksperiment s našim ASP modelom. Dodao sam 5 izdajničkih kraljica u model i tražio rješenje za N od 1 do 150 i evo šta je ispalo (pokreni na običnom kućnom laptopu):

Ukupno, naš ASP model može pronaći rješenja za problem komplementa za N za otprilike minut<= 150 (в обычном случае). Это показывает, что система отлично подходит для прототипирования моделей сложных комбинаторных задач.

zaključci

• Novi rezultat nije vezan za klasični problem 8 dama, već za dodavanje generaliziranog problema dama (što je zanimljivo, ali općenito logično);
• Kompleksnost se značajno povećava, jer lukavim postavljanjem dama na tablu možete poremetiti algoritam koji postavlja dame prema nekom fiksnom obrascu;
• Nemoguće je efektivno izbrojati broj rješenja (pa, nikako; dok se ne dogodi neki užas i P postane jednako NP, itd.);
• Možda će ovaj rezultat utjecati na rad modernih SAT sistema, jer neki stručnjaci smatraju da je ovaj problem nešto jednostavniji od klasičnih NP-potpunih problema (ali ovo je samo mišljenje)
• Ako iz nekog razloga iznenada trebate riješiti sličan problem, najbolje je koristiti sisteme ala Answer Set Programming, posebno dizajnirane za ovu svrhu

Ovaj problem je jedna od veoma zanimljivih šahovskih zagonetki.

Uslov je sljedeći: da li je moguće postaviti osam dama na praznu tablu tako da nijedna od njih ne “napadne” drugu, tj. tako da dvije dame ne stoje na istoj koloni, ili na istom redu, ili na istoj dijagonali šahovske ploče. Rješenje za ovaj problem, kao što razumijete, postoji, i to više od jednog. Na slici 1 sam pokazao jednu od mogućih opcija za postavljanje matica.

			F
F
				F
							F
	F
						F
		F
					F

Slika 1

Rešavanje ovog problema na računaru nije teško. U principu, možete glupo proći kroz sve moguće opcije za postavljanje dama na ploču, a zatim odrediti odgovarajuće. Nije teško napisati takav program, ali postavlja se pitanje: "Koliko opcija postoji i koliko vremena je potrebno da se one razvrstavaju?" Da budem iskren, bio sam previše lijen da izbrojim tačan broj opcija, ali, po svemu sudeći, morat ću dugo čekati.

Stoga morate nekako odrediti na koje polje postaviti sljedeću kraljicu. Na primjer, stavljanje nekoliko dama u jednu liniju je besmisleno (ovo je u suprotnosti sa uslovom). Ako problem pokušate riješiti ručno, postaje jasno da postavljanje 6 - 7 matica nije teško. Ali nakon ovoga nema slobodnih ćelija (koje nije „potukla“ nijedna matica). Stoga je kraljice potrebno postaviti tako da pogode što manje polja. Vrlo je dobro ako nekoliko različitih dama “tuku” ista polja, ali u isto vrijeme ne “tuku” jedna drugu.

Takvi algoritmi se nazivaju heurističkim i vrlo se često koriste u razvoju kompjuterskih igara. Ovi algoritmi obično sadrže uslove na osnovu kojih računar može izračunati posledice određenog poteza (u ovom slučaju broj polja koje će dama „pobeći”) i izabrati najbolje. Druge primjere programa koji koriste heurističke algoritme možete vidjeti na web stranici http://www.vova-prog.narod.ru/.

Da bismo riješili problem, potreban nam je niz pristupačnosti. U njemu ćemo pohraniti informacije o tome da li je određena ćelija slobodna ili ne. Dakle, da bismo odredili koliko ćelija će matica “prebiti” od date, potrebno je pomicati maticu u svim mogućim smjerovima (ima ih 8) i prebrojati slobodne ćelije. Za pomicanje matice zgodno je koristiti dva jednodimenzionalna niza, čiji elementi označavaju koliko ćelija matica treba pomaknuti kada se kreće u odabranom smjeru. Ja sam ih ovako definisao:

Const int vert = (0,-1,-1,-1,0,1,1,1); const int hor = (1,1,0,-1,-1,-1,0,1);

Nulti element odgovara pomicanju udesno. Prvi je dijagonalno udesno i gore, itd.

Da biste pomaknuli damu, na primjer, za jedno polje niže, možete napisati

X += hor; y += vert;

Zatim morate odabrati ćeliju koja odgovara najmanjem broju "izbačenih" slobodnih ćelija. Ako postoji nekoliko takvih ćelija, odaberite jednu od njih nasumično i stavite kraljicu na nju (u ovom slučaju morate napomenuti u nizu pristupačnosti da su odgovarajuće ćelije zauzete). Proces se ponavlja dok se ne instalira svih 8 matica.

Ovaj primjer jasno pokazuje glavni nedostatak heurističkog programiranja - ono ne rješava uvijek problem. Program koji koristi ovaj algoritam pronalazi rješenje otprilike jedno od deset. Ovaj rezultat se, naravno, može poboljšati ako se, na primjer, analiza izvrši nekoliko poteza unaprijed. Ali, u svakom slučaju, takav program neće moći da garantuje rešenje, samo ćemo povećati verovatnoću da ga pronađemo.

KURSNI RAD

"Rješavanje problema 8 kraljica"

Harkov 2007

Svrha rada: razviti program koji bi jasno pokazao mogućnosti postavljanja dama na šahovsku ploču, zadovoljavajući pravila zadatka.

Metod istraživanja: proučavanje literature, kreiranje i otklanjanje grešaka programa na računaru, provjera rješenja.

Program postavljanja matica može se koristiti u praksi u obrazovne svrhe. Može se koristiti i za proučavanje matematičkog modela problema. Uostalom, problem je posebno zanimljiv kada se veličina šahovske ploče povećava.

Zadatak zvuči ovako:

“Na koji način se osam dama može postaviti na tablu da ne prijete jedna drugoj, tj. nema dva koja stoje na istoj vertikali, horizontali i dijagonali i koliko takvih načina?"

Problem osam kraljica

Očigledno je nemoguće postaviti više od osam mirnih dama (kao i topova) na regularnu tablu. Lako je pronaći neki raspored od osam matica koje ne prijete jedna drugoj (na slici su prikazana četiri potrebna rasporeda). Mnogo je teže izbrojati ukupan broj aranžmana i izvesti ih, što je, zapravo, zadatak.

Zanimljivo je da su mnogi autori greškom pripisali ovaj problem i njegovo rješenje samom K. Gaussu. Zapravo, prvi ga je 1848. godine postavio njemački šahist M. Bezzel. Dr F. Science pronašao je 60 rješenja i objavio ih u listu “Illustrierte Zeitung” od 1. juna 1850. Tek nakon toga Gauss se zainteresovao za problem i pronašao 72 rješenja, o čemu je izvijestio u pismu svom prijatelju astronomu. Schumacher od 2. septembra 1850. Kompletan isti set rješenja, koji se sastoji od 92 pozicije, primio je isti F. Sciences. On ih je naveo u pomenutim novinama od 21. septembra 1850. Ovu hronologiju je uspostavio poznati njemački istraživač matematičke zabave W. Arens.

Strogi dokaz da 92 rješenja iscrpljuju sve mogućnosti dobio je tek 1874. engleski matematičar D. Glasher (koristeći teoriju determinanti). Gledajući unaprijed, napominjemo da postoji samo dvanaest značajnih rješenja (koja se ne poklapaju sa refleksijama i rotacijama ploče).

Postoji mnogo poznatih načina da se organizira efikasna potraga za lokacijom osam mirnih matica (metode Permentier, La Noe, Gunther, Glasher, Laquiere, itd.). Ove metode su opisane u brojnoj literaturi o zabavnoj matematici. U našem kompjuterskom dobu, problem ove vrste ne bi izazvao tako veliko interesovanje. Na kraju krajeva, dovoljno je napraviti jednostavan program, a u roku od nekoliko minuta nakon njegovog uvođenja u mašinu, sve 92 potrebne pozicije će biti odštampane.

Od svakog rješenja za problem dame može se dobiti niz drugih rotiranjem ploče za 90, 180 i 270°, kao i preslikavanjem u odnosu na linije koje dijele ploču na pola. Na primjer, iz rasporeda prikazanog na sl. i, kada se ploča okrene za 90° u smjeru kazaljke na satu, dobijamo raspored na sl. c, a kada se daska reflektuje u odnosu na liniju koja razdvaja krila kralja i dama - na sl. d. Koristeći druge rotacije i refleksije ploče, može se dobiti još pet rješenja.

Dakle, naznačene operacije sa šahovskom tablom omogućavaju da se iz jednog rasporeda mirnih dama dobije, uopšteno govoreći, sedam novih. Dokazano je da su u opštem slučaju na nhn dasci (za n > 1) za bilo koji raspored n mirnih matica moguće tri situacije:

1) jednim odrazom daske nastaje novi raspored matica, ali se rotacijama i drugim odrazima ne dobijaju nova rešenja;

2) novo rešenje nastaje kada se tabla rotira za 90°, a njeni odrazi daju još dva rasporeda;

3) tri rotacije table i četiri refleksije dovode do sedam različitih rasporeda (a ako računamo originalni, onda imamo ukupno osam pozicija).

U slučaju 1) originalno rješenje se naziva dvostruko simetrično, u slučaju 2) – simetrično, au slučaju 3) – jednostavno. Za običnu ploču, svako rješenje je jednostavno ili simetrično, a ne postoje dvostruko simetrična rješenja.

Skup rasporeda od osam mirnih dama naziva se osnovnim ako se, prvo, ti rasporedi ne transformišu jedan u drugi tokom rotacija i odraza daske, i, drugo, bilo koji drugi raspored se dobije iz nekog osnovnog pomoću ovih transformacija daske. Dokazano je da svaki osnovni skup rješenja problema sadrži tačno 12 aranžmana. Evo jednog takvog seta:

1) vidi sl. A;

2) vidi sl. b;

3) a4, b1, c5, d8, e6, f3, g7, h2;

4) a4, b2, c5, d8, e6, f1, g3, h7;

5) a4, b2, c7, d3, e6, f8, g1, h5;

6) a4, b2, c7, d3, e6, f8, g5, h1;

7) a3, b5, c2, d8, e6, f4, g7, h1;

8) a4, b1, c5, d8, e2, f7, g3, h6;

9) a4, b7, c3, d8, e2, f5, g1, h6;

10) a6, b4, c2, d8, e5, f7, g1, h3;

11) a4, b8, c1, d5, e7, f2, g6, h3;

12) a4, b2, c7, d5, e1, f8, g6, h3.

Preostalih 80 formacija dobijeno je od ovih dvanaest pomoću rotacija i refleksije daske. Glavni raspored na sl. b je simetričan, ostalih jedanaest osnovnih rasporeda je jednostavnih. Dakle, ukupno na tabli imamo 11·8+1·4=92 rasporeda osam dama koje se međusobno ne ugrožavaju.

Napomenimo nekoliko zanimljivih svojstava mirnih kraljica aranžmana. Simetrični raspored na sl. b, kako treba da bude, ima vanjsku simetriju. Odlikuje ga i činjenica da centralni dio table (4x4 kvadrat) ne zauzimaju dame. Obe glavne dijagonale table su takođe slobodne ovde (osmi glavni aranžman takođe ima ovo svojstvo). U prvom rasporedu (sl. a), nema tri dame na istoj pravoj liniji povučenoj kroz centre polja (to znači ne samo vertikale, horizontale i dijagonale daske, već i prave linije sa drugim uglovima nagiba ).

Bilo koje rješenje problema osam kraljica može se zapisati kao skup (t1, t2, j, t8), koji je permutacija brojeva 1, 2, j, 8. Ovdje je ti broj vodoravne linije na kojoj je kraljica i-te vertikalne tribine. Kako dame ne stoje na istoj horizontalnoj liniji, onda su svi brojevi ti različiti, a pošto dame ne stoje na istoj dijagonali, onda za bilo koje i, j (i< j Ј 8) имеем: |tj-ti| № j-i.

Zapišimo brojeve 1, 2, I, 8 prvo rastućim redoslijedom, a zatim opadajućem. Nakon toga, dodajemo brojeve svake od ove dvije permutacije sa brojevima proizvoljne permutacije od osam brojeva, na primjer ovo - (3, 7, 2, 8, 5, 1, 4, 6): 1, 2, 3, 4, 5, 6, 7, 8

3, 7, 2, 8, 5, 1, 4, 6

4,9, 8, 7, 6, 5, 4, 3, 2, 1

3, 7, 2, 8, 5, 1, 4, 6

11,14,8,13,9,4, 6, 7.

Rezultirajući zbroji čine dva skupa: (4, 9, 5, 12, 10, 7, 11, 14) i (11, 14, 8, 13, 9, 4, 6, 7). Hajde da razmotrimo sledeći problem.

Koje permutacije brojeva od 1 do 8 rezultiraju u dva takva skupa, u svakom od kojih su svi elementi različiti, kao rezultat naznačene operacije sabiranja?

Problem osam kraljica privukao je Gaussovu pažnju upravo u vezi sa ovim čisto aritmetičkim problemom. Ispostavilo se da postoji korespondencija jedan-na-jedan između rješenja ova dva problema. Drugim riječima, svaki raspored od osam kraljica koje ne prijete jedna drugoj daje rješenje aritmetičkog problema, i obrnuto. Za odabranu permutaciju, oba skupa se sastoje od različiti brojevi, i to nije slučajno - odgovara prvom glavnom rasporedu (vidi sl. a).

Lako je vidjeti da kada se ploča rotira i reflektira, neka rješenja se dobijaju od drugih koristeći jednostavne aritmetičke operacije na koordinatama polja koje zauzimaju kraljice. Analiza ovih operacija otkriva dodatna svojstva rješenja o kojima nećemo raspravljati.

Problem n kraljica. Stavite n dama na nhn šahovsku ploču tako da ne prijete jedna drugoj.

Na ploči 1x1, jedna dama je postavljena na jedno polje i rješenje postoji. Na tabli 2x2, jedna dama, bez obzira gdje stoji, napada tri druga polja, a drugu damu nema gdje postaviti. Samo dvije mirne dame mogu stati na dasku 3x3. Dakle, za ploče 2x2 i 3x3 problem nema rješenja. Ova dva slučaja su izuzeci. Za svih n > 3, n x n dama se mogu postaviti na nxn tablu koje ne prijete jedna drugoj.

Na tabli 4´4 nalazi se jedan glavni raspored, i to dvostruko simetričan: a2, b4, c1, d3, tj. Postoje samo dva rješenja. Postoje dve glavne formacije na tabli 5´5: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, d1, e4. Ukupan broj Postoji deset formacija, a od njih možete izabrati pet takvih da, kada se nalože jedna na drugu, 25 dama popuni sva polja na tabli 5x5.

Imajte na umu da u opštem slučaju, n aranžmana (rješenja problema) mogu popuniti cijelu nxn ploču kada se nadograđuju samo za one n koji nisu višekratnici dva i tri. Iz ovoga, posebno, proizilazi da je za redovnu tablu nemoguće odabrati osam rasporeda koji pokrivaju sva 64 polja na tabli.

Uopštavajući algebarsko svojstvo rješenja problema osam kraljica, dobijamo da je raspored n kraljica (t1, t2, j, tn) na ploči n´n željeni ako za bilo koje i, j (i< j Ј n) имеет место: |tj-ti| № j-i. Таким образом, задача об n ферзях сводится к чисто matematički problem o pronalaženju permutacije brojeva 1, 2, j, n koja zadovoljava navedeni uslov. Poznata su mnoga rješenja ovog problema, neka od njih su objavljena u ozbiljnim matematičkim časopisima. Jedan način za postavljanje n dama bez prijetnji jedna drugoj na proizvoljnu n´n (n = 5) ploču može se naći u knjizi “Matematika na šahovskoj tabli”.

Opis algoritma i strukture programa:

Ovaj program implementira rekurzivnu metodu za rješavanje problema 8 kraljica.

Imamo funkciju (int put_queen (int x)), koja stavlja sljedeću kraljicu na polje i sama sebe poziva da postavi sljedeću, ako se sljedeća kraljica ne može postaviti, onda vraća kontrolu funkciji iz koje je pozvana , a to zauzvrat pokušava postaviti svoju kraljicu na drugo mjesto i ponovo rekurzivno dozvati sebe. Kada funkcija postavi posljednju damu, rezultat postavljanja se prikazuje korisniku.

Na samom početku pozivamo funkciju s parametrom x jednakim nuli (numeracija počinje od 0), što znači da mora postaviti prvu kraljicu. Kada ova funkcija vrati kontrolu glavna funkcija, to znači da su sve opcije pronađene.

Za pohranjivanje položaja kraljica koristi se niz od 8 elemenata cjelobrojnog tipa (int queens). Redoslijed elementa u ovom nizu označava dam broj i njegovu x-koordinatu, odnosno kolonu, i njegovu vrijednost - y-koordinatu, odnosno red. Koristimo svojstvo da ne može biti nekoliko matica na jednom stupcu.

U ovom članku ćemo govoriti o poznatoj logičkoj zagonetki pod nazivom " osam kraljica„Suština problema je u tome što treba da budete u mogućnosti da postavite osam dama na šahovsku tablu (8 x 8) tako da ne budu jedna na drugoj (da vas podsetim da dama (dama) pogađa pravolinijski i dijagonalno ću reći da postoji nekoliko opcija za postavljanje, ali nije uvijek lako pronaći ih, posebno je teško postaviti posljednju maticu koja je prikazana ispod na slici 1.

Slika 1

Da bismo riješili problem osam kraljica, napisaćemo program u programskom jeziku C++, koji će rasporediti kraljice. Predlažem sledeću taktiku:

1. Zamislite šahovsku tablu kao dvodimenzionalni niz, veličine 8 x 8.

2. Za svaku ćeliju niza postavite broj koji će reći koliko drugih ćelija kraljica može pobijediti iz date ćelije. Vidi sliku 2

Slika 2

Kao što vidite, ako maticu postavite na poziciju x = 2, y = 1, tada će biti napadnute 23 ćelije. Ovaj postupak će se morati obaviti za svaku ćeliju šahovske ploče (dvodimenzionalni niz). Kao rezultat, dobijamo sljedeću sliku, prikazanu ispod na slici 3

Slika 3

3. Nakon što su prioriteti postavljeni, potrebno je da izaberete polje sa minimalnim prioritetom (ono sa manje smetnji od drugih polja na tabli) i postavite damu na njega. Mislim da je tu jasno... jer ako postavite dame na ona polja sa kojih možete uhvatiti veći broj drugih polja, onda definitivno nećemo doći do plasmana osam dama. Nastavljamo s rasuđivanjem...ako postoji nekoliko ćelija sa minimalnim prioritetom (a na samom početku aranžmana će to biti slučaj), onda ćemo nasumično odabrati odgovarajuću. Kako se to može logički organizovati? Da bismo to uradili, prvo moramo pronaći minimalni prioritet (recimo 21 - to će biti najmanji u prvoj iteraciji - vidi sliku 3), zatim izbrojati broj ćelija sa ovim prioritetom (u našem slučaju, od 21 od ovih identičnih ćelija će ih biti čak 28), a zatim generisati slučajni broj u rasponu od 1 do broja identičnih ćelija (ima ih 28) i na osnovu broja dobijenog tokom generisanja postaviti maticu na pravo mjesto. Nekako ćemo označiti ćeliju u koju stavljamo maticu, na primjer, dodijelivši joj vrijednost 100. Možete uzeti apsolutno bilo koju vrijednost, samo je odaberite tako da nije definirana kao minimalna pri određivanju prioriteta.

4. Nakon postavljanja matice, morate ukloniti ćelije koje je pogodila, označavajući ih nekim brojem. Recimo da ove ćelije označim brojem 99 radi praktičnosti.

Malo pojašnjenje. Kada je glavni algoritam za raspoređivanje dama proradio i imamo samo ćelije sa brojevima 100 (ovo su dame) i 99 - pretučene ćelije koje su ostale na šahovskoj ploči (dvodimenzionalni niz koji oponaša šahovsku ploču), tada ćemo prikazati rezultat na ekranu pod uslovom da ako naiđemo na broj 100 - onda nacrtajte kraljicu (ili u konzoli - pahuljicu, heš znak, itd.), U suprotnom učinite ćeliju jednostavno praznu (ili u konzoli, radi jasnoće, možete označite ih crticom, tačkama itd.).

5. Zatim se sve ponavlja od tačaka 2 do 4 dok ne postavimo sve matice kojih treba da bude osam. Postoji još jedna stvar: u prvom pokušaju, čak i koristeći takozvani “pametni” pristup implementaciji problema, gornji algoritam možda neće postaviti svih osam kraljica. Ali postoji izlaz iz ove situacije. Nakon plasmana ćemo provjeriti da li smo uspjeli plasirati sve matice. Ako ne, ponovite aranžman ponovo.

Na sljedećoj četvrtoj slici stavio sam u akciju gore opisani algoritam radi jasnoće. On može izdati razne opcije aranžmane, ali da biste to učinili morate ponovo učitati svoju web stranicu (dugme "osvježi" u pretraživaču ili F5) i tada će se rezultat promijeniti. Nažalost, još ne poznajem Ajax web tehnologiju, pa da biste dobili novu sliku morate ponovo učitati stranicu.

Slika 4

Evo tipa programa (za sada prikazujem samo njegov glavni dio - funkciju main()) koji implementira algoritam

Const int SIZE = 8; int main() ( int board; int x, y; int *ptrX = &x, *ptrY = srand(time(NULL)); //dok ne postavimo svih 8 kraljica (resetBoard(board); //pokušaj rasporedite kraljice za (int i = 1; i<= 8; i++) { updateBoard(board); choiseCell(board, ptrX, ptrY); board[x][y] = 100; deleteCell(board, x, y); } } while(!checkQueens(board)); printBoard(board); return 0; }

Kao što vidite, implementira ono što sam rekao gore

1) Deklarirajte dvodimenzionalni niz board, dimenzija 8 x 8 ćelija - ovo će biti naša šahovnica. Također će nam trebati varijable za pohranjivanje koordinata tačaka ( x I y) i pokazivače na njih ( ptrX I ptrY). Da bismo inicijalizirali niz nulama, koristit ćemo funkciju resetBoard().

2) Matrica je deklarirana i inicijalizirana. Pogledajmo sada unutar petlje za, koji će izvesti aranžman osam matica. Kao što smo rekli gore u tački 2, potrebno je da svakoj matričnoj ćeliji postavimo vlastiti prioritet. Funkcija će to učiniti updateBoard().

3) Prioriteti su postavljeni. Sada, kao što smo rekli u tački 3, trebamo odabrati ćeliju sa minimalnim prioritetom. Ako ih ima nekoliko, onda se odabir vrši nasumično. Sve ovo radi funkcija selectCell(), koji kao argument uzima matricu i pokazivače na koordinate x I y. Djelujući kroz pokazivače, ova funkcija mijenja vrijednosti koordinata x I y u glavnom programu. Jer x i y koordinate su se promijenile (tokom najave, kao što vidite, nisu pokrenute), onda možete ići na matricu board kontakt preko indeksa. Postavite odabrane koordinate na 100 (ovdje imamo kraljicu).

4) Nakon postavljanja matice označite ćelije koje je ubio. Ova funkcija to radi deleteCell().

Ovaj proces se ponavlja tačno osam puta kako je navedeno u uslovima petlje za. Ako, kao što sam gore napisao, nije moguće postaviti svih osam dama iz prvog pokušaja, tada se proces postavljanja resetuje pomoću resetBoard() i ciklus aranžmana počinje iznova. Da nam kaže da li je svih osam kraljica postavljeno ili ne, funkcija checkQueens(), vraćanje laž, ako nije bilo moguće dogovoriti, i istina, ako je aranžman bio uspješan.

To je u suštini sve što sam želio da vam kažem o ovom algoritmu. Potpuna implementacija programa je data u nastavku.

//Osam kraljica //potrebne datoteke zaglavlja #include #include #include #include const int SIZE = 8; //prototipovi funkcije void resetBoard(int); void updateBoard(int); int helpUpdateBoard(int, int, int, bool); void selectCell(int, int*, int*); void deleteCell(int, int, int); bool checkQueens(int); void printBoard(int); korištenje imenskog prostora std; int main() ( int board; int x, y; int *ptrX = &x, *ptrY = srand(time(NULL)); //dok ne postavimo svih 8 kraljica (resetBoard(board); //pokušaj rasporedite kraljice za(int i = 1; i<= 8; i++) { updateBoard(board); choiseCell(board, ptrX, ptrY); board[x][y] = 100; deleteCell(board, x, y); } } while(!checkQueens(board)); printBoard(board); return 0; } //проверяем, расставлены ли все ферзи или нет bool checkQueens(int board) { int counter = 0; for(int i = 0; i < SIZE; i++) for(int j = 0; j < SIZE; j++) if(board[i][j] == 100) counter++; return (counter == 8 ? true: false); } //обнуляем все клетки доски void resetBoard(int board) { for(int i = 0; i < SIZE; i++) for(int j = 0; j < SIZE; j++) board[i][j] = 0; } //помечаем побитые клетки void deleteCell(int board, int x, int y) { helpUpdateBoard(board, x, y, true); } //ищем подходящую клетку для постановки ферзя void choiseCell(int board, int *ptrX, int *ptrY) { int counter = 0, rnd; int min = board; //находим значение минимального приоритета for(int i = 0; i < SIZE; i++) for(int j = 0; j < SIZE; j++) if(board[i][j] < min) min = board[i][j]; //узнаем сколько в матрице есть клеток в одинак.приоритетом for(int i = 0; i < SIZE; i++) for(int j = 0; j < SIZE; j++) if(board[i][j] == min) counter++; //генерируем случайное число rnd = 1 + rand() % counter; counter = 0; //выбираем одну клетку из одинаковых случайным образом //и запоминаем ее координаты for(int i = 0; i < SIZE; i++) for(int j = 0; j < SIZE; j++) if(board[i][j] == min) if(++counter == rnd) *ptrX = i, *ptrY = j; } //обновляем приоритеты клеток шахматной доски void updateBoard(int board) { for(int i = 0; i < SIZE; i++) for(int j = 0; j < SIZE; j++) if(board[i][j] != 100 && board[i][j] != 99) board[i][j] = helpUpdateBoard(board, i, j, false); } //вспомогательная ф-ция: делаем проходы по всем направлениям //для вычисления приоритетов клеток int helpUpdateBoard(int board, int x ,int y, bool label) { int counter = 0, xTemp = x, yTemp = y; //по диагонали вправо вниз while(xTemp < (SIZE - 1) && yTemp < (SIZE - 1)) { xTemp++; yTemp++; if(label) board = 99; //если клетка не занята ферзем и не побита if(board != 100 && board != 99) counter++; } xTemp = x, yTemp = y; //по диагонали влево вверх while(xTemp >0 && yTemp > 0) ( xTemp--; yTemp--; if(oznaka) ploča = 99; if(ploča != 100 && ploča != 99) counter++; ) xTemp = x, yTemp = y; //dijagonalno udesno gore while(xTemp< (SIZE - 1) && yTemp >0) ( xTemp++; yTemp--; if(oznaka) ploča = 99; if(ploča != 100 && ploča != 99) brojač++; ) xTemp = x, yTemp = y; //dijagonalno lijevo dolje while(xTemp > 0 && yTemp< (SIZE - 1)) { xTemp--; yTemp++; if(label) board = 99; if(board != 100 && board != 99) counter++; } xTemp = x, yTemp = y; //вверх while(yTemp >0) ( yTemp--; if(oznaka) ploča = 99; if(ploča != 100 && ploča != 99) brojač++; ) xTemp = x, yTemp = y; //dolje while(yTemp< (SIZE - 1)) { yTemp++; if(label) board = 99; if(board != 100 && board != 99) counter++; } xTemp = x, yTemp = y; //вправо while(xTemp < (SIZE - 1)) { xTemp++; if(label) board = 99; if(board != 100 && board != 99) counter++; } xTemp = x, yTemp = y; //влево while(xTemp >0) ( xTemp--; if(label) board = 99; if(board != 100 && board != 99) counter++; ) return counter; ) //rezultati ispisa void printBoard(int board) ( for(int i = 0; i< SIZE; i++) { cout << endl; for(int j = 0; j < SIZE; j++) cout << setw(4) << (board[i][j] == 100 ? "#" : "."); cout << endl; } }

Rezultat programa

P.S. Takođe na sajtu možete pronaći još jednu implementaciju algoritma "Osam kraljica", koju je implementirao programer Aleksej i na čemu mu veliko hvala.