i
i
“1478-Juvan-Polkraljice” — 2010/8/25 — 8:19 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 29 (2001/2002)
Številka 3
Strani 158–159
Martin Juvan:
POLKRALJICE
Ključne besede: razvedrilna matematika, računalništvo, šahovnica,
postavitve figur.
Elektronska verzija:
http://www.presek.si/29/1478-Juvan-polkraljice.pdf
c© 2001 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
Računalništvo I
POLKRALJICE
Polkraljica je (izmišlje na) šahovska figura , ki je p o moči med trdnjavo in
pravo kr alj ico. Pravzaprav po znamo dve vrsti po lkraljic , bele in črne .
Bela polk ralji ca napada vsa po lja v svo ji vr sti ci , vsa polj a v svojem
stolpc u in vsa polj a na naraščaj oči diagonali , na kateri stoj i. P odobno
črna p olkralj ica napada vsa polj a v svoji vr sti ci in v svojem stolpc u t er
še vsa polja na padajoči diagon ali , na kat eri stoj i. Nap ad en a polj a za obe
vrst i po lkralj ic so prikazana t udi na spodnj i sliki.
x X
X X
X X
X X
X X il;:c X X X X X'o
X X
X X
X
X
X
X X
X X
X X c" X X X X X1).,
X X
X X
X X
Na ša hov nico velikost i ti x ti je vedno moč post aviti ti t rdnjav t ako, da
noben a ne nap ada nob ene druge (in sicer na n! različnih načinov). Če je
n =1= 2,3, pot em obstaja t udi taka post avit ev n kr alji c. Vsaka post avit ev n
kraljic pa določa 2" različnih post avit ev n po lkralj ic (vsako kraljico lahko
sp re me nimo v be lo ali v črno po lkralj ico ). P oleg tega pa obstaj a t udi
m nogo postavitev polk ralji c, ki j ih ne dobimo t ako, da kralj ice spre menimo
v po lkraljice (taka je npr . postavit ev črnih polkr alji c po glavni naraščajoči
diagonali ša hovnice).
V nalo gi nas bodo zanim ale po st avi t ve polkralji c, pri katerih nob en a
polk ralj ica ne napada no be ne druge. Natančneje , zanimalo nas bo , na
koliko različnih načinov lahko na ša hovnico velikosti n x n post avimo k
belih in n - k črnih polkraljic tako , da nobe na ne napada nobene druge.
S po skušanjem hit ro najdemo naslednje vrednosti :
velikost šahov nice 1 x 1 2 x 2 3x3
število belih polkralji c O 1 O 1 2 O 1 2 3
število postavitev 1 1 1 O 1 3 2 2 3
"-v---' "'-v--" "--v---'
2 2 10
b tabele mzberemo, da ne obataja %hIjubna" postwitev e m  bele in 
e n e ~ e p o ~ ~ ~ ~ m v e ~ 2 ~ 2 .  Mordabftev-itdd 
o p d t u d i m k a j  shatrija Z a ~ ~ n j s n s m r e E ~ o s t p r i k ~  
tisti pri n - k. Tb ni s1uhj, saj nrun xcaljmje prels vodclrame (alf pa prek 
navpitne) Whale idmmia pmwb 5nh3jmbno" poatmitw k beliZl in 
n-kt%nfhpokrdjkzv "miroljubnoA pos&avit~~n-kbl&b k Cdh 
pohaljie, 
Sedaj pa k ppr&mju. Spragyjcm vas, na koliko r d b i h  mEmv 
je moT: na obihjno ikhovnico vd&&i 8 x 8 paestaPiti 8 po'Wo:aQic W, 
da mhce od njih ne napada nobene dmge. Naj ww ~ p o z o h ,  der je 
i&m& patavitev dike, eaj lahlaJ 3% kraljh postavhno na 92 ra5l.i- 
mdmv, pmhvittsv krqie pa dolob lw 256 r W W h  p&iwitev 
polkrdjic. Z& wan pmdhgmn, da se mbge lot* z rahmhhm. Za 
iahodiiiik lahko wmete r- program, ki poi&% vm poetavitve 
kraljic na ihhmnicxll, in g;a ugtremo pri-te. Talc program, napban v 
pragmm&m j d c u  C, je npr. mStgv nalm 6.16 v kqji C mj bo.