Razmotrite omiljeni problem za razumijevanje algoritama, problem osam kraljica. Klasična definicija: "Postavite 8 kraljica na šahovsku ploču 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 s gledišta obična osoba, ali apsolutno besmisleno s hakerske točke gledišta, a ja ću vam reći zašto:

Analizirajmo algoritam: koristi se klasična backtracking pretraga, područje rješenja predstavljamo u obliku grafa, čiji je svaki vrh pozicija dame u kojoj ona nije napadnuta i ne pobjeđuje već postavljene dame ploča, tj. samo trebamo prikupiti sve "grane" koje se sastoje od točno osam vrhova. Kao metodu traženja ovih “grana” autor nam nudi klasični algoritam pretraživanja u širinu, tj. redoslijed obilaska grafa će izgledati ovako:

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

Pa u čemu je problem? U našem slučaju, za ploču 8x8, dobit ćemo 92 različita rješenja, a zamislite da, kao što se često događa u pravi 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.

Tablica koja prikazuje ovisnost broja rješenja o veličini ploče:

Što će to značiti za naš scenarij? A to što će ići u jako dugu potragu, a kako će sve odluke morati držati u glavi, u samo 15 minuta Python će pojesti 300 megabajta memorije. Tko ima snažan procesor i veliki volumen RAM memorija može provjeriti hoće li se ovaj proces uopće završiti...

I sve što smo trebali za rješavanje takvog problema bilo je odabrati ispravan algoritam za obilaženje grafa, što bi u našem slučaju bilo redovno pretraživanje najprije u dubinu, a zatim bi se graf obilazio ovim redoslijedom:

I kod bi bio mnogo jednostavniji, a čak i nakon 15 minuta skripta bi trošila točno onoliko memorije koliko i sekunda nakon pokretanja. A ovako bi njegova implementacija izgledala u Pythonu:

Def rc_queens(n_col, width, sol): if len(sol) == width: print sol else: for n_row in range(width): if (safe_queen(n_row, n_col, sol)): rc_queens(n_col+1, width , sol+) def safe_queen(new_row, new_col, sol): for col in range(len(sol)): if (sol == new_row or abs(col - new_col) == abs(sol - new_row)): return 0 return 1 if __name__ == "__main__": za n u rasponu(8): rc_queens(1, 8, [n])
p.s. Ovo je samo hakerski pogled na problem, možda netko može ponuditi pogled "teorijske informatike"?

Prije par mjeseci pojavio sam se s analizom klasični problem o postavljanju kraljica na šahovskoj ploči (vidi detalje i povijest u nastavku). Problem je nevjerojatno poznat i već je istražen pod mikroskopom, pa je bilo iznenađujuće da se pojavilo nešto uistinu novo.

(ovdje je maksimalan broj dama, a na mjesto križa možete staviti bijelu, a na mjesto crnu točku - 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 to učiniti?

Linearna pretraga klasičnog problema

Najviše zanimljiva točka da se čak i stručnjaci ponekad zbune i misle da je za rješavanje N-dama potrebna kombinatorna pretraga i misle da je složenost problema veća od P. Jednom sam na Habréu pisao o tome što su P i NP: i. Međutim, problem je riješen bez pretjerivanja opcije! To jest, za ploču bilo koje veličine uvijek možete rasporediti dame jednu iza druge ljestvice:

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

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

Kako izbrojati broj rješenja u praksi

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

Riješenje: ispišite znak i n po n, vratite 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 brojati rješenja (a njihov broj je nepoznat i nitko ih prije nije brojao), tada najbolja opcija O prototipu se govori u nastavku.

N-ov komplement i programiranje skupa odgovora

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

Što to znači u praksi? Najlakši način da riješimo ovaj problem (ili iznenada, ako trebamo njegovu varijaciju) je koristiti SAT. Međutim, više mi se sviđa sljedeća analogija:

SAT je asembler za kombinatorne NP probleme, a Answer Set Programming (ASP) je C++ (ASP također ima tajanstvenu rusku dušu: ponekad je zbunjujući i nepredvidiv za neupućene; usput, teorija na kojoj se temelji moderni ASP izumljena je u 1988. Mikhail Gelfond i Vladimir Lifshits, koji su tada radili na sveučilištima Texas odnosno Stanford).

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

Pojedinosti rješenja ovdje nisu toliko važne, a Answer Set Programming je vrijedan zasebnog posta (koji je bio u mom nacrtu nepristojno dugo): pa pogledajmo konceptualne točke

% red domene(1..n). stupac(1..n). % svi različiti 1 ( kraljica(X,Y) : stupac(Y) ) 1:- red(X). 1 ( kraljica(X,Y) : red(X) ) 1:- stupac(Y). % uklanjanja proturječnih odgovora:- 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 ( dama (X,Y) : stupac (Y) ) 1:- red (X). - se zove pravilo izbora i ono određuje što je važeći prostor pretraživanja.

Posljednja tri retka nazivaju se ograničenjima cjelovitosti: i oni definiraju koja ograničenja rješenje mora zadovoljiti: ne može biti kraljica u istom retku, ne može biti kraljica u istom stupcu (izostavljeno zbog simetrije) i ne može postojati kraljica na istoj dijagonali.

Preporučam Clingo kao sustav za eksperimentiranje.
A 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 nevjerojatno učinkovit i brz, ali najvjerojatnije će biti brži od grube sile s povratom napisanim u brzo rješenje. Međutim, ako razumijete osnovna načela sustava, ASP može postati "regexp za NP-complete probleme."

Provedimo jednostavan numerički eksperiment s našim ASP modelom. Dodao sam 5 izdajničkih kraljica u model i pokrenuo pretragu za rješenjem za N od 1 do 150 i ovo je ono što je ispalo (pokrenite na običnom kućnom laptopu):

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

zaključke

• Novi rezultat nije povezan s klasičnim problemom od 8 matica, već s dodatkom generaliziranog problema matica (što je zanimljivo, ali općenito logično);
• Složenost se znatno povećava, budući da lukavim postavljanjem dama na ploču možete poremetiti algoritam koji postavlja dame prema nekom fiksnom obrascu;
• Nemoguće je učinkovito prebrojati broj rješenja (dobro, nikako; sve dok se ne dogodi neki horor i P postane jednako NP, itd.);
• Možda će ovaj rezultat utjecati na rad modernih SAT sustava, jer neki stručnjaci vjeruju da je ovaj problem nešto jednostavniji od klasičnih NP-kompletnih problema (ali ovo je samo mišljenje)
• Ako odjednom trebate riješiti sličan problem iz nekog razloga, najbolje je koristiti sustave ala Answer Set Programming, posebno dizajnirane za tu svrhu

Ovaj problem je jedna od vrlo zanimljivih šahovskih zagonetki.

Uvjet je sljedeći: je li moguće postaviti osam dama na praznu ploču tako da nijedna od njih ne “napada” onu drugu, tj. tako da dvije kraljice ne stoje u istom stupcu, ili u istom redu, ili na istoj dijagonali šahovske ploče. Kao što razumijete, postoji rješenje za ovaj problem, i to više od jednog. Na slici 1 prikazao sam jednu od mogućih opcija za postavljanje matica.

			F
F
				F
							F
	F
						F
		F
					F

Slika 1

Rješavanje ovog problema na računalu nije jako teško. U principu, možete glupo proći kroz sve moguće opcije za postavljanje kraljica na ploču, a zatim odrediti odgovarajuće. Nije teško napisati takav program, ali postavlja se pitanje: "Koliko opcija postoji i koliko je vremena potrebno da ih razvrstate?" Da budem iskren, bio sam previše lijen da prebrojim točan broj opcija, ali, očito, morat ću dugo čekati.

Stoga morate nekako odrediti na koje polje postaviti sljedeću kraljicu. Na primjer, postavljanje nekoliko kraljica u jednu liniju je besmisleno (to je u suprotnosti s uvjetom). Ako problem pokušate riješiti ručno, postaje jasno da postavljanje 6 - 7 dama nije teško. Ali nakon toga nema slobodnih ćelija (koje nije "tukla" niti jedna matica). Stoga dame treba postaviti tako da pogađaju što manje polja. Vrlo je dobro ako nekoliko različitih kraljica "tuku" ista polja, ali u isto vrijeme ne "tuku" jedna drugu.

Takvi se algoritmi nazivaju heuristički i vrlo se često koriste u razvoju računalnih igara. Ti algoritmi obično sadrže uvjete na temelju kojih računalo može izračunati posljedice pojedinog poteza (u ovom slučaju broj polja koje će dama “pobijediti”) i odabrati najbolji. 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 njega ćemo pohraniti podatke o tome je li određena ćelija slobodna ili ne. Dakle, da bismo odredili koliko će ćelija matica “pobijediti” od zadane, potrebno je pomicati maticu u svim mogućim smjerovima (ima ih 8) i brojati slobodne ćelije. Za pomicanje kraljice prikladno je koristiti dva jednodimenzionalna niza, čiji elementi pokazuju koliko ćelija kraljica treba pomaknuti kada se kreće u odabranom smjeru. Definirao sam ih ovako:

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 kretanju udesno. Prvi je dijagonalno udesno i gore, itd.

Za pomicanje kraljice, na primjer, jedno polje prema dolje, možete pisati

X += hor; y += vert;

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

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

NASTAVNI RAD

"Rješenje problema s 8 kraljica"

Kharkov 2007

Svrha rada: razviti program koji bi jasno pokazao mogućnosti postavljanja kraljica na šahovskoj ploči, zadovoljavajući pravila problema.

Metoda istraživanja: proučavanje literature, izrada i otklanjanje pogrešaka programa na računalu, provjera rješenja.

Program postavljanja matica može se koristiti u praksi u obrazovne svrhe. Također se može koristiti 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 može postaviti osam dama na ploču da ne prijete jedna drugoj, tj. nijedno dvoje nije stajalo na istoj vertikali, horizontali i dijagonali i koliko je takvih putova?"

Problem s osam kraljica

Očito je nemoguće postaviti više od osam mirnih dama (kao i topova) na običnu ploču. Lako je pronaći neki raspored od osam dama koje ne ugrožavaju jedna drugu (slika prikazuje četiri tražena rasporeda). Puno je teže izbrojati ukupan broj aranžmana i izvesti ih, što zapravo i jest zadatak.

Zanimljivo je da su mnogi autori ovaj problem i njegovo rješenje pogrešno pripisali samom K. Gaussu. Naime, prvi ju je 1848. godine postavio njemački šahist M. Bezzel. Dr. F. Science pronašao je 60 rješenja i objavio ih u novinama “Illustrierte Zeitung” od 1. lipnja 1850. Tek nakon toga Gauss se zainteresirao za problem i pronašao 72 rješenja, o čemu je izvijestio u pismu svom prijatelju astronomu Schumachera od 2. rujna 1850. Kompletan isti skup rješenja, koji se sastoji od 92 pozicije, primio je isti F. Sciences. Naveo ih je u spomenutim novinama od 21. rujna 1850. Tu je kronologiju utvrdio 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 se teorijom determinanti). Gledajući unaprijed, primjećujemo da postoji samo dvanaest značajnih rješenja (koja se ne podudaraju s refleksijama i rotacijama ploče).

Postoje mnogi poznati načini organiziranja učinkovite potrage za lokacijom osam miroljubivih matica (metode Permentiera, La Noea, Gunthera, Glashera, Laquierea itd.). Ove metode opisane su u brojnoj literaturi o zabavnoj matematici. U našem kompjuterskom dobu, problem ove vrste ne bi izazvao toliko veliko zanimanje. Uostalom, dovoljno je izraditi jednostavan program, au roku od nekoliko minuta nakon njegovog uvođenja u stroj ispisat će se sve 92 potrebne pozicije.

Od svakog rješenja problema dame, niz drugih može se dobiti rotiranjem ploče za 90, 180 i 270°, kao i njezinim zrcaljenjem u odnosu na linije koje dijele ploču na pola. Na primjer, iz rasporeda prikazanog na Sl. a zakretanjem ploče za 90° u smjeru kazaljke na satu dobivamo raspored na sl. c, a kada se ploča reflektira u odnosu na liniju koja razdvaja krila kralja i kraljice - 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 pločom omogućuju dobivanje, općenito govoreći, sedam novih iz jednog rasporeda mirnih kraljica. Dokazano je da su u općem slučaju na nhn ploči (za n > 1) za bilo koji raspored n mirnih dama moguće tri situacije:

1) s jednim odrazom ploče nastaje novi raspored dama, ali s rotacijama i drugim odrazima ne dobivaju se nova rješenja;

2) novo rješenje nastaje kada se ploča zakrene za 90°, a njezini odrazi daju još dva rasporeda;

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

U slučaju 1) izvorno rješenje se naziva dvostruko simetrično, u slučaju 2) – simetrično, a u slučaju 3) – jednostavno. Za običnu ploču svako je rješenje ili jednostavno ili simetrično, a dvostruko simetričnih rješenja nema.

Skup rasporeda od osam mirnih dama naziva se osnovnim ako, prvo, ti rasporedi ne prelaze jedan u drugi tijekom rotacija i odraza ploče, i, drugo, bilo koji drugi raspored dobiven je iz nekog osnovnog pomoću ovih transformacija ploče. Dokazano je da svaki osnovni skup rješenja problema sadrži točno 12 rasporeda. Evo jednog takvog skupa:

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 dobiva se od ovih dvanaest korištenjem rotacija i refleksija ploče. Glavni raspored na Sl. b je simetričan, ostalih jedanaest osnovnih rasporeda je jednostavno. Dakle, ukupno na ploči imamo 11·8+1·4=92 rasporeda osam dama koje ne ugrožavaju jedna drugu.

Zabilježimo nekoliko zanimljivih svojstava mirnih matica. Simetrični raspored na sl. b, kao što bi trebalo biti, ima vanjsku simetriju. Karakteristična je i po tome što središnji dio ploče (4x4 polje) ne zauzimaju dame. Ovdje su također slobodne obje glavne dijagonale ploče (ovo svojstvo ima i osmi glavni raspored). U prvom rasporedu (Sl. a), tri dame nisu na istoj ravnoj liniji povučenoj kroz središta polja (to ne znači samo okomice, horizontale i dijagonale ploče, već i ravne linije s drugim kutovima nagiba ).

Svako rješenje problema s osam kraljica može se napisati kao skup (t1, t2, j, t8), koji je permutacija brojeva 1, 2, j, 8. Ovdje je ti broj vodoravne crte na kojoj je kraljica i-te okomite tribine. Budući da dame ne stoje na istoj vodoravnoj liniji, tada su svi brojevi ti različiti, a kako dame ne stoje na istoj dijagonali, tada za svaki i, j (i< j Ј 8) имеем: |tj-ti| № j-i.

Zapišimo brojeve 1, 2, j, 8 prvo rastućim, a zatim padajućim redoslijedom. Nakon toga zbrajamo brojeve svake od ove dvije permutacije s 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.

Dobiveni zbrojevi tvore dva skupa: (4, 9, 5, 12, 10, 7, 11, 14) i (11, 14, 8, 13, 9, 4, 6, 7). Razmotrimo sljedeć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 navedene operacije zbrajanja?

Problem osam dama privukao je pozornost Gaussa upravo u vezi s ovim čisto aritmetičkim problemom. Ispada da postoji korespondencija jedan na jedan između rješenja ova dva problema. Drugim riječima, svaki raspored osam dama koje ne prijete jedna drugoj daje rješenje aritmetičkog problema, i obrnuto. Za odabranu permutaciju oba se skupa sastoje od različite brojeve, a to nije slučajno - odgovara prvom glavnom rasporedu (vidi sliku a).

Lako je vidjeti da se, kada se ploča okreće i reflektira, neka rješenja dobivaju od drugih pomoću jednostavnih aritmetičkih operacija na koordinatama polja koje zauzimaju dame. Analiza ovih operacija otkriva dodatna svojstva otopina o kojima nećemo raspravljati.

Problem n kraljica. Postavite n kraljica na nxn šahovsku ploču tako da ne prijete jedna drugoj.

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

Na ploči 4g4 je jedan glavni raspored, i to dvostruko simetričan: a2, b4, c1, d3, tj. Postoje samo dva rješenja. Dvije su glavne formacije na ploči 5g5: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, d1, e4. Ukupni broj Postoji deset formacija, a od njih možete odabrati pet tako da, kada se nađu jedna na drugu, 25 dama popuni sva polja ploče 5x5.

Imajte na umu da u općem slučaju n rasporeda (rješenja problema) može ispuniti cijelu nxn ploču kada se superponira samo za one n koji nisu višekratnici dva i tri. Iz ovoga, naime, proizlazi da je za običnu ploču nemoguće odabrati osam rasporeda koji pokrivaju sva 64 polja ploče.

Generalizirajući algebarsko svojstvo rješenja problema osam dama, dobivamo da je raspored n dama (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 uvjet. Poznata su mnoga rješenja ovog problema, neka od njih su objavljena u ozbiljnim matematičkim časopisima. Jedna metoda za postavljanje n kraljica bez prijetnje jedna drugoj na proizvoljnoj ng̀n (n = 5) ploči može se pronaći u knjizi “Matematika na šahovskoj ploči”.

Opis algoritma i strukture programa:

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

Imamo funkciju (int put_queen (int x)), koja postavlja sljedeću damu na polje i poziva samu sebe da postavi sljedeću, ako se sljedeća dama ne može postaviti, tada vraća kontrolu funkciji iz koje je pozvana , a ona zauzvrat, pokušava postaviti svoju kraljicu na drugo mjesto, i opet rekurzivno pozvati samu sebe. Kada funkcija postavi posljednju damu, korisniku se prikazuje rezultat postavljanja.

Na samom početku pozivamo funkciju s parametrom x jednakim nuli (numeriranje počinje od 0), što znači da mora postaviti prvu damu. 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 broj kraljice i njegovu x-koordinatu, odnosno stupac, a vrijednost - y-koordinatu, odnosno red. Koristimo svojstvo da na jednom stupcu ne može biti više matica.

U ovom ćemo članku govoriti o poznatoj logičkoj zagonetki pod nazivom " osam kraljica“Suština problema je u tome što treba znati postaviti osam kraljica na šahovsku ploču (8 x 8) tako da jedna drugoj ne budu pod udarom (podsjećam da kraljica (dama) pogađa u pravoj liniji. i dijagonalno). Reći ću, da postoji nekoliko opcija za postavljanje, ali njihovo ručno pronalaženje nije uvijek lako, posebno je teško postaviti posljednju kraljicu. Jedna od opcija za postavljanje kraljica prikazana je dolje na slici 1.

Slika 1

Kako bismo riješili problem osam kraljica, napisat ćemo program u programskom jeziku C++ koji će rasporediti matice. Predlažem da slijedite ovu taktiku:

1. Zamislite šahovsku ploču 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 dane ćelije. Pogledajte sliku 2

Slika 2

Kao što možete vidjeti, ako postavite kraljicu na poziciju x = 2, y = 1, tada će biti 23 ćelije pod napadom. Ovaj postupak morat ćete napraviti za svaku ćeliju šahovske ploče (dvodimenzionalni niz). Kao rezultat toga, dobivamo sljedeću sliku, prikazanu dolje na slici 3

Slika 3

3. Nakon što ste postavili prioritete, trebate odabrati polje s minimalnim prioritetom (ono s manje smetnji drugih polja na ploči) i na njega postaviti kraljicu. Mislim da je tu jasno... jer ako dame postavite na ona polja s kojih možete uhvatiti veći broj drugih polja, onda sigurno nećemo doći do postavljanja osam dama. Nastavljamo razmišljati...ako postoji nekoliko ćelija s minimalnim prioritetom (a na samom početku rasporeda to će biti slučaj), tada ćemo nasumično odabrati odgovarajuću. Kako se to može logično organizirati? Da bismo to učinili, prvo moramo pronaći minimalni prioritet (recimo 21 - bit će najmanji u prvoj iteraciji - vidi sliku 3), zatim prebrojati broj ćelija s tim prioritetom (u našem slučaju, od 21 od ovih identičnih stanica će ih biti čak 28), a zatim generirajte slučajni broj u rasponu od 1 do broja identičnih stanica (ima ih 28) i na temelju broja dobivenog generacijom postaviti maticu na pravo mjesto. Nekako ćemo označiti ćeliju u koju postavljamo kraljicu, na primjer, dodijeliti joj vrijednost 100. Možete uzeti apsolutno bilo koju vrijednost, samo je odaberite tako da ne bude definirana kao minimalna pri određivanju prioriteta.

4. Nakon što postavite maticu, potrebno je ukloniti ćelije koje je pogodila, označivši ih nekim brojem. Recimo da ove ćelije označim brojem 99 radi praktičnosti.

Malo pojašnjenje. Kada glavni algoritam za slaganje kraljica proradi i na šahovskoj ploči (dvodimenzionalni niz koji oponaša šahovsku ploču) ostane samo ćelija s brojevima 100 (to su kraljice) i 99 - tučene ćelije, tada ćemo prikazati rezultat na ekranu pod uvjetom da ako naiđemo na broj 100 - tada nacrtamo damu (ili u konzoli - pahuljicu, crtu itd.), inače neka ćelija bude jednostavno prazna (ili u konzoli, radi jasnoće, možete označite ih crticom, točkama itd.).

5. Zatim se opet sve ponavlja od točke 2 do 4 dok ne postavimo sve matice kojih bi trebalo biti osam. Postoji još jedna stvar: u prvom pokušaju, čak i korištenjem takozvanog "pametnog" pristupa implementaciji problema, gornji algoritam možda neće postaviti svih osam kraljica. Ali postoji izlaz iz ove situacije. Nakon plasmana provjerit ćemo jesmo li uspjeli postaviti sve matice. Ako nije, onda ponovite raspored ponovno.

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 ponovno učitati svoju web stranicu (gumb "osvježi" u pregledniku ili F5) i tada će se rezultat promijeniti. Nažalost, još ne poznajem Ajax web tehnologiju, pa da biste dobili novu sliku, morate ponovno učitati stranicu.

Slika 4

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

Const int VELIČINA = 8; int main() ( int tabla; int x, y; int *ptrX = &x, *ptrY = srand(time(NULL)); //dok ne postavimo svih 8 dama uradi ( resetBoard(tabla); //pokušaj rasporedite dame 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 odbor, dimenzija 8 x 8 ćelija - ovo će biti naša šahovska ploča. Također ćemo trebati varijable za pohranu koordinata točaka ( x I g) i pokazivači na njih ( ptrX I ptrY). Za inicijalizaciju polja s nulama koristit ćemo funkciju resetBoard().

2) Matrica je deklarirana i inicijalizirana. Sada pogledajmo unutar petlje za, koja će izvršiti uređenje osam matica. Kao što smo rekli gore u točki 2, svakoj ćeliji matrice trebamo postaviti vlastiti prioritet. Funkcija će to učiniti ploča za ažuriranje().

3) Prioriteti su postavljeni. Sada, kao što smo rekli u točki 3, moramo odabrati ćeliju s minimalnim prioritetom. Ako ih ima nekoliko, tada se odabir vrši nasumično. Sve to čini funkcija izabrati ćeliju(), koji kao argumente uzima matricu i pokazivače na koordinate x I g. Djelujući preko pokazivača, ova funkcija mijenja vrijednosti koordinata x I g u glavnom programu. Jer x i y koordinate su se promijenile (tijekom najave, kao što vidite, nisu pokrenute), tada možete ići na matricu odbor 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 se postupak ponavlja točno osam puta kako je navedeno u uvjetima petlje za. Ako, kao što sam gore napisao, nije moguće postaviti svih osam kraljica iz prvog pokušaja, tada se postupak postavljanja poništava pomoću resetBoard() i ciklus uređenja počinje iznova. Da nam kaže jesu li svih osam kraljica postavljene ili ne, funkcija checkQueens(), vraćajući se laž, ako nije bilo moguće dogovoriti, i istina, ako je dogovor bio uspješan.

To je u biti sve što sam vam htio reći o ovom algoritmu. Potpuna provedba programa navedena je u nastavku.

//Osam dama //potrebne datoteke zaglavlja #include #uključi #uključi #uključi const int VELIČINA = 8; //prototipovi funkcija void resetBoard(int); void ploča ažuriranja(int); int HelpUpdateBoard(int, int, int, bool); void selectCell(int, int*, int*); void deleteCell(int, int, int); bool provjera kraljica(int); void printBoard(int); korištenje imenskog prostora std; int main() ( int tabla; int x, y; int *ptrX = &x, *ptrY = srand(time(NULL)); //dok ne postavimo svih 8 dama uradi ( resetBoard(tabla); //pokušaj rasporedite dame 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) brojač++; ) 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 dok (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++; ) povratni brojač; ) //ispis rezultata 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đer na web mjestu možete pronaći još jednu implementaciju algoritma "Osam kraljica", koju je implementirao programer Alexey i za što mu veliko hvala.