Broj mogućih rasporeda osam kraljica na šahovskoj tabli veličine 8×8 polja je 64x63x62x61x60x59x58x57, odnosno 178.462.987.637.760. Ako bismo proveravali deset miliona kombinacija u sekundi – bilo bi nam potrebno nešto više od pola godine da ih sve proverimo. Za sto miliona provera u sekundi, što bi već predstavljalo izazov za kućne računare, bilo bi potrebno dvadeset dana.
Ako imamo u vidu usvojeni način predstavljanja rasporeda kraljica na šahovskoj tabli – kao niz od osam brojeva – onda je taj broj 8x8x8x8x8x8x8x8, odnosno 16.777.216 kombinacija. To je broj koji savremeni računari mogu da savladaju za veoma kratko vreme – nekoliko sekundi.
Program koji pronalazi sva rešenja mogao bi da izgleda ovako:
Jedino što ovde još nismo naveli je funkcija SledećiRaspored() koja pomera kraljice na šahovskoj tabli na kontrolisani način. Ona je opisana u tekstu “Prvo rešenje problema osam kraljica”, odakle se može prepisati i ceo primer 6.
Ovaj program će proveriti svaki od 16.777.216 rasporeda i ispisaće na ekran sve one koji predstavljaju jedno od rešenja problema osam kraljica. Vreme izvršavanja programa je manje od 200ms, a rezultat koji se ispisuje na ekran je veliki 19929 bajtova i sadrži 921 liniju teksta. Zadnja linija je:
Broj pokušaja: 16777216, H.OK: 40320, broj rešenja: 92
i dugačka je 57 bajtova (54 slova, među kojima ima dva slova š koja se u utf-8 sistemu kodiranja predstavljaju sa dva bajta, 0xC5A1 + kraj reda, \n odnosno NewLine). Ovo ostavlja 19872 bajta za prikaz rešenja, odnosno 216 bajtova po rešenju. Iz prethodnih prikaza rešenja, a i iz izvornog koda programa (funkcije Print) vidimo da se jedno rešenje štampa kao deset redova po 19 slova + kraj reda, s’ tim što se znak ♛ kodira sa tri bajta, 0xE2999B, što daje 8×22+2×20=216. Dakle, izlaz iz našeg programa prolazi osnovnu logičku kontrolu.
Početak ispisa izgleda ovako:
8 [. . ♛ . . . . .] 7 [. . . . . ♛ . .] 6 [. . . ♛ . . . .] 5 [. ♛ . . . . . .] 4 [. . . . . . . ♛] 3 [. . . . ♛ . . .] 2 [. . . . . . ♛ .] 1 [♛ . . . . . . .] a b c d e f g h [0 4 7 5 2 6 1 3] 8 [. . ♛ . . . . .] 7 [. . . . ♛ . . .] 6 [. ♛ . . . . . .] 5 [. . . . . . . ♛] 4 [. . . . . ♛ . .] 3 [. . . ♛ . . . .] 2 [. . . . . . ♛ .] 1 [♛ . . . . . . .] a b c d e f g h [0 5 7 2 6 3 1 4]
i tu su prikazana prva dva rešenja, dok kraj fajla sa dva zadnja rešenja izgleda ovako:
8 [♛ . . . . . . .] 7 [. . . . . . ♛ .] 6 [. . . ♛ . . . .] 5 [. . . . . ♛ . .] 4 [. . . . . . . ♛] 3 [. ♛ . . . . . .] 2 [. . . . ♛ . . .] 1 [. . ♛ . . . . .] a b c d e f g h [7 2 0 5 1 4 6 3] 8 [♛ . . . . . . .] 7 [. . . . . . ♛ .] 6 [. . . . ♛ . . .] 5 [. . . . . . . ♛] 4 [. ♛ . . . . . .] 3 [. . . ♛ . . . .] 2 [. . . . . ♛ . .] 1 [. . ♛ . . . . .] a b c d e f g h [7 3 0 2 5 1 6 4] Broj pokušaja: 16777216, H.OK: 40320, broj rešenja: 92
Broj rešenja koja zadovoljavaju horizontalni kriterijum, 40380, je ustvari 8! jer on predstavlja broj rasporeda u kojima imamo po tačno jednu kraljicu u svakoj koloni (što smo obezbedili načinom predstavljanja rasporeda kraljica kao [8]int) i tačno jednu kraljicu u svakom redu. Ovo, prateći redosled intuitivnog postavljanja kraljica, znači da prva kraljica koju stavljamo zauzima prvu kolonu i u njoj ima osam različitih mogućih pozicija, druga u drugoj koloni ima sedam preostalih mogućnosti, treća šest, i tako dalje do osme koja ide u osmu kolonu i ima samo jedan slobodan red – dakle 8x7x6x5x4x3x2x1 = 8! = 40320.
Kratko objašnjenje o izvršavanju programa i preusmeravanju izlaza u fajl
Ako se naš primer 6 nalazio u fajlu pod imenom primer6.go, izvršavanje je moglo da se odvija tako što najpre kompajliramo program, a onda izvršimo kompajlirani program i preusmerimo njegov izlaz u fajl:
go build
./primer6 > primer6.txt
Potom komandama
ls -l primer6.txt
wc primer6.txt
dobijamo informacije o veličini fajla u bajtovima (prva komanda) i broju linija (druga komanda), dok sâm sadržaj fajla možemo pregledati pomoću komande
less primer6.txt
koja omogućava kretanje unutar fajla.
Početak i kraj fajla, koji su prilazani u tekstu ispred, dobijeni su sledećim komandama:
head -20 primer6.txt
tail -21 primer6.txt
Prvom komandom prikazano je prvih dvadeset linija fajla, a drugom zadnja 21 linija.
Dimenzije pokušaja
Obzirom da je naslov ovog teksta “Dimenzije problema”, a do sada smo se bavili dimenzijama njegovih rešenja, napravićemo još jedan eksperiment. Modifikovaćemo program iz primera 6 tako da štampa po jedan red za svaki mogući raspored kraljica na tabli, i ne štampa rešenja.
Ovaj program se, bez zapisivanja njegovog izlaza, izvršava oko 15 do 20 sekundi, zavisno od snage računara. Sa zapisivanjem rezultata u fajl (288 megabajta), vreme izvršavanja može da bude od 25 do 40 sekundi, zavisno od brzine računara i diskova.
Ukoliko bismo izbacili liniju koja štampa rezultat, fmt.Println(tabla), vreme izvršavanja bi palo ispod 200 milisekundi, što je velika razlika u odnosu na 15 sekundi. Na ovom primeru vidimo da čak i jednostavno zapisivanje velike količine podataka može da zauzme značajne resurse, naročito ako se izvodi kroz mnogo sitnih operacija.
Fajl koji smo dobili izvršavanjem primera 7 ima 16.777.217 linija, 16.777.216 pokušaja i jednu liniju sa statistikom izvršavanja. Svaka linija 17 znakova + kraj reda (osam cifara koje prikazuju raspored, sedam razmaka između cifara i dve uglaste zagrade daje 17 znakova). Već znamo da zadnja linija zauzima 57 bajtova, pa je ukupna veličina fajla 16.777.216×18+57=301.989.945 bajtova. Početak i kraj fajla izgledaju ovako:
[0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 1] [0 0 0 0 0 0 0 2] [0 0 0 0 0 0 0 3] [0 0 0 0 0 0 0 4] [0 0 0 0 0 0 0 5] [0 0 0 0 0 0 0 6] [0 0 0 0 0 0 0 7] [0 0 0 0 0 0 1 0] [0 0 0 0 0 0 1 1] [7 7 7 7 7 7 6 6] [7 7 7 7 7 7 6 7] [7 7 7 7 7 7 7 0] [7 7 7 7 7 7 7 1] [7 7 7 7 7 7 7 2] [7 7 7 7 7 7 7 3] [7 7 7 7 7 7 7 4] [7 7 7 7 7 7 7 5] [7 7 7 7 7 7 7 6] [7 7 7 7 7 7 7 7] Broj pokušaja: 16777216, H.OK: 40320, broj rešenja: 92
Pošto je broj mogućih rasporeda stepen broja osam, 88, a kilobajt je 1024=2×83, i megabajt 1024×1024=4×86, za očekivati je da veličina fajla bez zadnje linije bude ceo broj megabajta. Dakle, 301.989.888/1024/1024=288Mb. Do broja 288 dolazimo i ovako:
88x18/(4×86) = 8×87x18/(4×86) = 2x8x18 = 288
Za one koji su upoznati sa stepenima broja 2 (2,4,8,16,32,64,128,256,512,1024,2048…) ova računica može da se napiše (ili čak izračuna napamet) i ovako:
88x(16+2)/(4×86) = 8×87x(16+2)/(4×86) = 2x8x16+2x8x2 = 256+32 = 288
