Iz prethodnih tekstova možemo prikupiti dovoljno elemenata da napravimo kompletan program koji pronalazi sva rešenja problema osam kraljica. Došli smo do zaključka da se ovaj program može implementirati tako što se za svaki od mogućih 16.777.216 rasporeda osam kraljica na šahovskoj tabli proveri da li je on jedno od rešenja. Ako jeste – ispisujemo ga na ekran i nastavljamo proveru.
Jedina komponenta koja nedostaje je već pominjana funkcija SledećiRaspored() koja treba da od trenutnog rasporeda na tabli (odnosno u nizu [8]int) istu tu tablu dovede u sledeći logičan raspored, i tako u 16.777.216 izvršavanja pokrije sve moguće rasporede kraljica na tabli, i to po tačno jedanput.
Podrazumevane vrednosti promenljivih u Go-u
Važno je napomenuti još jednu stvar koja se u izvornom kodu programa ne vidi, a mi se u našim primerima oslanjamo na nju. To je činjenica da se sve promenljive u Go-u postavljaju – inicijalizuju na vrednost koja je definisana kao podrazumevana za njihov tip. Tako se i šahovska tabla
var tabla šahovskaTabla
postavlja na vrednost koja je podrazumevana za tip [8]int, a to je niz od osam nula, što je istovremeno i prvi od 16.777.216 mogućih rasporeda. Zato program u primeru 6 radi tako što u petlji najpre proveri da li je trenutni raspored jedno od rešenja, i nakon toga prelazi na sledeće rešenje i novo izvršavanje petlje.
Funkcija SledećiRaspored
Niz od osam cifara, od kojih svaka može uzeti vrednost između nula i sedam, može se posmatrati i kao osmocifreni oktalni broj. Tako smo koračanje kroz sve moguće rasporede osam kraljica na šahovskoj tabli sveli na brojanje od 0 do 077777777 (oktalni brojevi se u Go-u označavaju nulom ispred broja). Istovremeno smo obezbedili i garanciju da ćemo sve rasporede isprobati tačno jedanput, odnosno da ni jedan raspored nećemo preskočiti ili isprobati više puta.
I stvarno, kada oktalni broj 077777777 pretvorimo u decimalni, dobijemo 16.777.215 (ili heksadecimalni 0xFFFFFF), što zajedno sa nulom (tačnije osam nula) kao početnim rasporedom daje 16.777.216.
Povećavanje nekog višecifrenog broja za jedan se radi tako što se najniža (krajnja desna) cifra poveća za 1, pa ako je prekoračila opseg jedne cifre – onda se u nju upisuje nula i cifra levo od nje se po istim pravilima poveća za jedan. Na primer, povećavanje za po jedan decimalnog četvorocifrenog brojeva može ići ovako:
597 598 599 600
Ovde smo u zadnjem koraku cifru 9 na najnižoj poziciji povećali na 10, zadržali nulu na najnižoj poziciji i 9 na srednjoj poziciji povećali na 10, zadržali nulu na srednjoj poziciji i 6 povećalli za 1.
Princip je isti kod oktalnih brojeva, jedino što je kod njih maksimalna vrednost jedne cifre 7:
0275 0276 0277 0300
Objašnjenje je isto kao u prethodnom primeru, u zadnjem koraku smo cifru 7 na najnižoj poziciji povećali na 10, zadržali nulu na najnižoj poziciji i 7 na srednjoj poziciji povećali na 10, zadržali nulu na srednjoj poziciji i 2 na najvišoj poziciji povećalli za 1.
Jasno je da brojanje počinjemo od 000000000 i završavamo kada 077777777 treba da povećamo na 0100000000, što je više od osam cifara. U svim slučajevima osim za 077777777+01 naša funkcija treba da poveća broj (preuredi kraljice na šahovskoj tabli) i vrati true. U slučaju 077777777+01 funkcija će početi sa povećavanjem broja 077777777 za jedan, ali će na kraju otkriti da dolazi do prekoračenja, i vratiti false kao rezultat. Usput će se i kraljice na šahovskoj tabli sa pozicije [7 7 7 7 7 7 7 7] vratiti na [0 0 0 0 0 0 0 0], ali to nam neće smetati, jer inače u tom trenutku završavamo sa obradom.
U prethodnom članku smo videli kako izgleda početak i kraj fajla sa rasporedima, i to ustvari jeste sekvenca osmocifrenih oktalnih brojeva:
00000000 00000001 00000002 00000003 00000004 00000005 00000006 00000007 00000010 00000011 77777766 77777767 77777770 77777771 77777772 77777773 77777774 77777775 77777776 77777777
Funkcija SledećiRaspored() treba da uveća osmocifreni oktalni broj za jedan, i da javi da li je u tome uspela ili ne. Osmocifreni broj je predstavljen kao niz od osam cifara, [8]int.
Napisaćemo je kao petlju koja ide od zadnje do prve cifre. Unutar petlje ćemo pokušati da uvećamo tekuću cifru za 1:
- Ako uspemo – izlazimo iz funkcije sa rezultatom “uspeh”, odnosno true.
- Ako ne uspemo – tekuću cifru postavljamo na vrednost nula i puštamo da se u sledećem prolazu kroz petlju cifra levo od tekuće uveća za 1.
Jasno je da u slučaju da “ne uspemo” sa uvećavanjem zadnje cifre – izlazimo iz petlje, i da je to situacija kada je uvećavanje broja završeno. U tom slučaju rezultat funkcije je false.
Brojanje, ili formiranje različitih rasporeda, će početi od nule, odnosno sa svih osam kraljica u prvom redu, i završiti sa 077777777, odnosno sa svih osam kraljica i osmom redu. U međuvremenu ćemo redom proći sve moguće rasporede.
Program koji radi na opisani način izgleda ovako:
Ovaj program ispisuje sva rešenja problema osam kraljica, i to u već poznatom obliku: šahovska tabla sa rasporedom figura i niz od osam brojeva koji predstavljaju prikazani raspored onako kako se on vidi “iznutra”.
Početak i kraj izgledaju 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] 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
Ustvari, za nas programere rešenje je samo niz od osam brojeva, što možemo dobiti ako u gornjem programu umesto tabla.Print() stavimo fmt.Println(tabla). U ovako skraćenom načinu ispisa, sva rešenja izgledaju ovako (prikazana u četiri kolone):
Pošto su rešenja ustvari oktalni brojevi, mogu se prikazati i ovako:
