Da li je sledeći raspored kraljica na tabli jedno od 92 rešenja problema osam kraljica?
8 [. . . . ♛ . . .] 7 [. . ♛ . . . . .] 6 [. . . . . . ♛ .] 5 [. ♛ . . . . . .] 4 [. . . ♛ . . . .] 3 [. . . . . ♛ . .] 2 [. . . . . . . ♛] 1 [♛ . . . . . . .] a b c d e f g h [0 4 6 3 7 2 5 1]
Provera po kriterijumima daje sledeći rezultat:
- Vertikalno: svaka kraljica je sama u svojoj koloni – uslov ispunjen.
- Horizontalno: svaka kraljica zauzima po jedan red – uslov ispunjen.
- Dijagonalno:
- kraljice a1 i d4 dele istu dijagonalu, kao i b5 i e8;
- kraljice c7 i h2 dele istu dijagonalu, kao i e8 i g6.
Kako bi izgledao program koji proverava ove uslove za dati raspored?
Prvi uslov je ispunjen samim načinom predstavljanja šahovske table sa kraljicama u programskom modelu – svaka kolona sadrži tačno po jednu kraljicu.
Drugi uslov, da u svakom redu bude tačno po jedna kraljica, svodi se na proveru da li u nizu od osam brojeva [8]int, koji je osnova tipa šahovskaTabla, nema ponavljanja brojeva. Drugi način je provera da li su u nizu od osam brojeva prisutni svi brojevi od nula do sedam.
Deo programa za proveru drugog, horizontalnog uslova može izgledati ovako:
func (t šahovskaTabla) Horizontalno() bool {
var b [8]bool
for _, r := range t {
if b[r] {
return false
}
b[r] = true
}
return true
}
Odnosno, proveru vršimo tako što koristimo niz od osam promenljivih tipa bool. Za svaki od brojeva iz tipa šahovskaTabla najpre proverimo da li je njegova pozicija u nizu već bila prisutna levo od njega. Ako jeste – vraćamo rezultat false, horizontalni uslov nije ispunjen. Ako nije – označavamo da je od sada prisutna i nastavljamo dalje.
Za raspored [1 7 7 3 1 6 1 4], prvi “pseudoslučajni” koji dobijamo ako ne inicijalizujemo generator slučajnih brojeva, provera bi išla ovako:
• niz b se inicijalizuje na [false false false false false false false false];
• kolona 0: u njoj je vrednost 1 i ona nije bila prisutna do sada, b[1] je false;
• b[1] postaje true, b = [false true false false false false false false];
• kolona 1: u njoj je vrednost 7 i ona nije bila prisutna do sada, b[7] je false;
• b[7] postaje true, b = [false true false false false false false true];
• kolona 2: u njoj je vrednost 7 i ona jeste bila prisutna do sada, b[7] je true;
• vraćamo false kao rezultat provere jer ima dve kraljice u jednom redu – redu 7.
Naravno, raspored [0 4 6 3 7 2 5 1] bi prošao ovaj test, jer je podešen da u svakom redu bude po jedna kraljica.
Važno je napomenuti da je ovaj način provere horizontalnog uslova veoma efikasan, jer otkriva duplikate čim se oni pojave i prekida dalju proveru. Suprotan primer bi bio ako bismo niz od osam brojeva sortirali i onda proveravali da li u sortiranom nizu ima ponavljanja. Tu bi se uvek radilo celo sortiranje, bez obzira da li se ponavljanje desilo u prve dve kolone ili u zadnje dve.
Treći uslov, da po oba dijagonalna pravca ima najviše jedna kraljica u svakoj dijagonali, mora se ispitivati odvojeno za svaki pravac. Ukoliko se, kao kod horizontalne provere, držimo principa da svaka sledeća kolona proverava prethodne, odnosno “gleda iza sebe – levo od sebe”, onda bi provere u oba pravca mogle da se ilustruju ovako:
8 [. . . . ♛ . . .] 8 [↖ ↖ . . ♛ . . .] 7 [. . ♛ ↙ . . . .] 7 [↖ ↖ ♛ . . ↖ . .] 6 [. ↙ ↙ . . . ♛ .] 6 [↖ ↖ ↖ ↖ . . ♛ .] 5 [↙ ♛ . . . ↙ . .] 5 [. ♛ ↖ ↖ ↖ . . .] 4 [↙ . . ♛ ↙ . . .] 4 [. . . ♛ ↖ ↖ . .] 3 [. . ↙ ↙ . ♛ . .] 3 [. . . . . ♛ ↖ .] 2 [. ↙ ↙ . ↙ . . ♛] 2 [. . . . . . . ♛] 1 [♛ ↙ . ↙ . . ↙ .] 1 [♛ . . . . . . .] a b c d e f g h a b c d e f g h [0 4 6 3 7 2 5 1] [0 4 6 3 7 2 5 1]
Očigledno je da kolona 0 ne mora da radi nikakve provere, jer levo od nje nema ničega. Ostale kolone se proveravaju tako što proveravamo da li se u prethodnim kolonama nalazi broj koji predstavlja “sudar” ili “gađanje”, i koji se dobija na sledeći način:
Ova provera za gornji primer, [0 4 6 3 7 2 5 1], išla bi ovako:
• i=1, N=4, j=0: tabla[0]≠3 i tabla[0]≠5
• i=2, N=6, j=1: tabla[1]≠5 i tabla[1]≠7; j=0: tabla[0]≠4 i N+2=8, 8>7
• i=3, N=3, j=2: tabla[2]≠2 i tabla[2]≠4; j=1: tabla[1]≠1 i tabla[1]≠5; j=0: tabla[0]=0
Sada treba konstruisati program, odnosno funkciju “func (t šahovskaTabla) Dijagonalno() bool” za proveru ovih dijagonalnih uslova. Jasno je da ova funkcija treba da radi provere za sve kolone osim prve, odnosno za kolone 1 do 7:
func (t šahovskaTabla) Dijagonalno() bool {
for i := 1; i<8; i++ {
Provera kolone i prema kolonama levo od i
}
return true
}
U sledećem koraku preciziranja programa ćemo “Provera kolone i prema kolonama levo od i” implementirati kao petlju od 0 do i-1, ili od i-1 do 0, i proveru tekuće kolone u toj petlji sa kolonom i.
func (t šahovskaTabla) Dijagonalno() bool {
for i := 1; i<8; i++ {
// Provera kolone i prema kolonama levo od i
for j := i-1; j>=0; j-- {
Provera kolona i,j
}
}
return true
}
Još je ostalo da napišemo kod za proveru dve kolone, prema gornjim uputstvima:
func (t šahovskaTabla) Dijagonalno() bool {
for i := 1; i < 8; i++ {
// Provera kolone i prema kolonama levo od i
for j := i - 1; j >= 0; j-- {
// Provera kolona i,j
N := t[i]
X := t[j]
// Provera prve dijagonale
if N-(i-j) >= 0 && X == N-(i-j) {
return false
}
// Provera druge dijagonale
if N+(i-j) < 8 && X == N+(i-j) {
return false
}
}
}
return true
}
Na kraju ćemo uobličiti program koji generiše određeni broj slučajnih rasporeda, do zadatog maksimalnog broja, i svaki slučajni raspored proverava pomoću funkcija Horizontalno i Vertikalno. Program će završiti sa radom kada pronađe slučajni raspored koji odgovara kriterijumima, ili dođe do maksimalnog broja pokušaja.
// primer 5
package main
import (
"fmt"
"math/rand"
)
type šahovskaTabla [8]int
func (t šahovskaTabla) Print() {
var redovi [8][8]string
var prazanRed = [8]string{".", ".", ".", ".", ".", ".", ".", "."}
// inicijalizacija redova
for red := 0; red < 8; red++ {
redovi[red] = prazanRed
}
for i := 0; i < 8; i++ {
redovi[t[i]][i] = "♛"
}
for i := 7; i >= 0; i-- {
fmt.Printf("%d %v\n", i+1, redovi[i])
}
fmt.Printf(" a b c d e f g h \n %v\n", t)
}
func (t šahovskaTabla) Horizontalno() bool {
var b [8]bool
for _, r := range t {
if b[r] {
return false
}
b[r] = true
}
return true
}
func (t šahovskaTabla) Dijagonalno() bool {
for i := 1; i < 8; i++ {
// Provera kolone i prema kolonama levo od i
for j := i - 1; j >= 0; j-- {
// Provera kolona i,j
N := t[i]
X := t[j]
// Provera prve dijagonale
if N-(i-j) >= 0 && X == N-(i-j) {
return false
}
// Provera druge dijagonale
if N+(i-j) < 8 && X == N+(i-j) {
return false
}
}
}
return true
}
func (t šahovskaTabla) SlučajniRaspored() {
for i := 0; i < 8; i++ {
tabla[i] = rand.Intn(8)
}
}
var tabla šahovskaTabla
func main() {
//rand.Seed(time.Now().UnixNano())
brojPokušaja, brojHorizontalnih, maxBrojPokušaja := 0, 0, int(1e8)
for i := 0; i < maxBrojPokušaja; i++ {
tabla.SlučajniRaspored()
brojPokušaja++
if tabla.Horizontalno() {
brojHorizontalnih++
if tabla.Dijagonalno() {
tabla.Print()
fmt.Printf("Broj pokušaja: %d, H.OK: %d\n", brojPokušaja, brojHorizontalnih)
return
}
}
}
fmt.Printf("Bez rešenja, broj pokušaja: %d, H.OK: %d\n", brojPokušaja, brojHorizontalnih)
}
Maksimalni broj pokušaja postavljen je prilično visoko, na 108 odnosno 100.000.000 – sto miliona. Ukoliko program izvršimo kako je ovde naveden, bez inicijalizacije generatora slućajnih brojeva, dobićemo ovakav rezultat:
8 [. . ♛ . . . . .] 7 [. . . . . ♛ . .] 6 [. . . . . . . ♛] 5 [♛ . . . . . . .] 4 [. . . . ♛ . . .] 3 [. . . . . . ♛ .] 2 [. ♛ . . . . . .] 1 [. . . ♛ . . . .] a b c d e f g h [4 1 7 0 3 6 2 5] Broj pokušaja: 96228, H.OK: 243
Dakle, bez malo sto hiljada pokušaja je bilo potrebno da se dođe do rešenja. Pri tome je od 96228 pokušaja, samo 243 zadovoljilo horizontalni uslov, a od njih samo jedno i dijagonalni. Vidimo da ovaj način “pronalaženja” rešenja nije efikasan. Naročito ako hoćemo da pronađemo sva rešenja.
Ukoliko sklonimo komentar sa inicijalizacije generatora slučajnih brojeva, možemo dobiti i drugačija (slučajnija) rešenja:
8 [. . ♛ . . . . .] 8 [. . . . ♛ . . .] 8 [. ♛ . . . . . .] 7 [♛ . . . . . . .] 7 [. ♛ . . . . . .] 7 [. . . ♛ . . . .] 6 [. . . . . . ♛ .] 6 [. . . ♛ . . . .] 6 [. . . . . ♛ . .] 5 [. . . . ♛ . . .] 5 [. . . . . ♛ . .] 5 [. . . . . . . ♛] 4 [. . . . . . . ♛] 4 [. . . . . . . ♛] 4 [. . ♛ . . . . .] 3 [. ♛ . . . . . .] 3 [. . ♛ . . . . .] 3 [♛ . . . . . . .] 2 [. . . ♛ . . . .] 2 [♛ . . . . . . .] 2 [. . . . . . ♛ .] 1 [. . . . . ♛ . .] 1 [. . . . . . ♛ .] 1 [. . . . ♛ . . .] a b c d e f g h a b c d e f g h a b c d e f g h [6 2 7 1 4 0 5 3] [1 6 2 5 7 4 0 3] [2 7 3 6 0 5 1 4]
Takođe, i broj pokušaja se razlikuje od slučaja do slučaja:
Broj pokušaja: 93106, H.OK: 241 Broj pokušaja: 144352, H.OK: 344 Broj pokušaja: 203906, H.OK: 491
