Postavka problema
Da li je moguće rasporediti osam kraljica na šahovskoj tabli, tako da ni jedna ne “gađa” preostalih sedam? Kraljice gađaju druge figure po pravilima u šahu, odnosno:
- vertikalno, sve što je u istoj koloni,
- horizontalno, sve što je u istom redu,
- dijagonalno.
Moguće je, postoje 92 različita rasporeda koji zadovoljavaju uslov da nijedna ne gađa nijednu drugu.
Programski model
Mesto rešavanja problema, i mesto čuvanja i predstavljanja rešenja je šahovska tabla:
Šezdeset četiri polja u kvadratnom rasporedu “osam puta osam” nas vuku ka dvodimenzionalnom nizu, recimo:
var tabla [8][8]string
Onda bi početak raspoređivanja figura sa slike mogao da bude:
tabla[0][0] = “top” tabla[0][1] = “konj”
Ili, uz upotrebu šahovskih simbola (koji su deo skupa znakova Unicode):
tabla[0][0] = “♖” tabla[0][1] = “♘”
Šahovski simboli su pogodniji za štampanje šahovske table sa figurama, pa bi program koji štampa raspored sa slike mogao da izgleda ovako:
// primer 1
package main
import "fmt"
var tabla [8][8]string
func main() {
tabla[0] = [8]string{"♖", "♘", "♗", "♕", "♔", "♗", "♘", "♖"}
tabla[1] = [8]string{"♙", "♙", "♙", "♙", "♙", "♙", "♙", "♙"}
tabla[6] = [8]string{"♟︎", "♟︎", "♟︎", "♟︎", "♟︎", "♟︎", "♟︎", "♟︎"}
tabla[7] = [8]string{"♜", "♞", "♝", "♛", "♚", "♝", "♞", "♜"}
for i := 2; i < 6; i++ {
tabla[i] = [8]string{" ", " ", " ", " ", " ", " ", " ", " "}
}
for i := 7; i >= 0; i-- {
fmt.Printf("%d %v\n", i+1, tabla[i])
}
fmt.Println(" a b c d e f g h")
}
a proizvod njegovog izvršavanja:
8 [♜ ♞ ♝ ♛ ♚ ♝ ♞ ♜] 7 [♟︎ ♟︎ ♟︎ ♟︎ ♟︎ ♟︎ ♟︎ ♟︎] 6 [ ] 5 [ ] 4 [ ] 3 [ ] 2 [♙ ♙ ♙ ♙ ♙ ♙ ♙ ♙] 1 [♖ ♘ ♗ ♕ ♔ ♗ ♘ ♖] a b c d e f g h
Međutim, nas ovde ne interesuje programski model šahovske table koja je funkcionalno sposobna da prihvati proizvoljnu figuru na proizvoljnom mestu, već tabla na kojoj će biti samo tačno osam kraljica. Sledeća tri rasporeda nam mogu pomoći da uočimo koje osobine naša tabla treba da ima:
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
Program koji generiše gornja tri rasporeda izgleda ovako:
// primer 2
package main
import (
"fmt"
"math/rand"
)
var prazanRed = [8]string{".", ".", ".", ".", ".", ".", ".", "."}
func main() {
tabla1, tabla2, tabla3 := [8][8]string{}, [8][8]string{}, [8][8]string{}
for i := 0; i < 8; i++ {
tabla1[i], tabla2[i], tabla3[i] = prazanRed, prazanRed, prazanRed
}
for i := 0; i < 8; i++ {
tabla1[i][2], tabla2[i][i], tabla3[i][rand.Intn(8)] = "♛", "♛", "♛"
}
for i := 7; i >= 0; i-- {
fmt.Printf("%d %v %d %v %d %v\n", i+1, tabla1[i], i+1, tabla2[i], i+1, tabla3[i])
}
fmt.Println(" a b c d e f g h a b c d e f g h a b c d e f g h")
}
Prvi raspored je “sve kraljice u jednoj koloni”, što nikako ne može biti jedno od rešenja problema osam kraljica. Drugi raspored je po dijagonali, što takođe ne može biti rešenje.
Treći raspored je malo bliži potencijalnom rešenju, ali je očigledno da tri kraljice u koloni b nisu dobar početak, kao ni dve u koloni h.
Dakle, da bi neki raspored “ušao u razmatranje” potrebno je da u svakoj koloni bude po tačno jedna kraljica. Isto važi i za redove i za dijagonale, ali o tome kasnije.
Prvi uslov ćemo zadovoljiti ako, na primer, raspored kraljica na tabli pamtimo kao niz od osam “pozicija kraljice u koloni”. Prvi od gornja tri rasporeda se ne može predstaviti na ovaj način, i to nije nedostatak pošto se radi o unapred poznatom “lošem rešenju”. Drugi raspored je
[0 1 2 3 4 5 6 7]
odnosno – dijagonalni. Primećujemo da u ovom načinu predstavljanja rasporeda kraljica nigde ne pamtimo koja figura je u pitanju. Nigde nema ♛, i nije ni potrebno jer ♛ je u opisu problema.
Treći raspored nije moguće prikazati na ovaj način, ali je moguće prikazati malo promenjen, sličan raspored:
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 [- ? - 3 7 - 5 ?] → [0 4 6 3 7 2 5 1]
U daljim eksperimentima, šahovska tabla za rešavanje problema osam kraljica biće:
var tabla [8]int
Ovakva tabla obezbeđuje da prvi od tri uslova iz definicije problema uvek bude ispunjen, odnosno da u svakoj koloni bude po tačno jedna kraljica, pa onda ni jedna kraljica neće moći da “gađa” neku drugu vertikalno.
Program koji generiše jedan slučajni raspored na ovakvoj šahovskoj tabli izgleda ovako:
// primer 3
package main
import (
"fmt"
"math/rand"
"time"
)
var tabla [8]int
func main() {
rand.Seed(time.Now().UnixNano())
for i := 0; i < 8; i++ {
tabla[i] = rand.Intn(8)
}
fmt.Println(tabla)
}
a nekoliko slučajnih rasporeda ovako (odnosno, svaki put drugačije):
[6 3 3 1 6 6 3 7] [1 2 2 1 5 7 5 5] [2 3 1 7 6 1 7 5] [1 5 5 3 3 5 2 7] [4 6 7 3 5 6 2 6]
Iz ovih slučajnih rasporeda se već vidi kako proveriti sledeći, drugi uslov – da nema više od jedne kraljice u jednom redu: brojevi u rasporedu se ne smeju ponavljati. Očigledno je da nijedan od gornjih rasporeda ne ispunjava taj uslov, pa ni jedan od njih nije kandidat za proveru trećeg uslova – da nema “gađanja” po dijagonalama. I u ovom trenutku se već nazire algoritam za proveru drugog i trećeg uslova, ali o njima kasnije.
Prethodno pitanje, koje nije deo rešenja ali jeste deo posmatranja problema, je: Kako štampati ovaj model šahovske table? Odnosno, kako od
[0 4 6 3 7 2 5 1]
stići do
8 [. . . . ♛ . . .]
7 [. . ♛ . . . . .]
6 [. . . . . . ♛ .]
5 [. ♛ . . . . . .]
4 [. . . ♛ . . . .]
3 [. . . . . ♛ . .]
2 [. . . . . . . ♛]
1 [♛ . . . . . . .]
a b c d e f g h
