Osem napadalnih kraljic

Testi

testi-osem-napadalnih-kraljic.py

Naloga

Šahovska polja označimo s črkami a-h, ki predstavljajo koordinate stolpcev, in številkami 1-8, ki predstavljajo vrstice. Tako je polje b4 drugo polje v četrti vrsti.

Šahovska kraljica se lahko premika po stolpcih, vrsticah in diagonalah. Kraljica, ki bi jo postavili na b4, bi s svojo požrešnostjo ogrožala vsa polja stolpca b, vrste 4, poleg tega pa še diagonali, torej polja a5, c3, d2, e1 in a3, c5, d6, e7 in f8.

Na šahovnico postavimo določeno število kraljic. Razpored predstavimo s seznamom koordinat, pri čemer so koordinate opisane kot nizi, recimo ["a4", "c7", "d2"].

Spodnje naloge zahtevajo, da napišete različne funkcije. Kadar naloga eksplicitno zahteva, da mora funkcija klicati druge funkcije, se tega navodila obvezno držite. To je eden od namenov te vaje.

Naloge so razdeljene po ocenah. Za vsako oceno je potrebno pravilno rešiti tudi naloge za nižjo oceno. Tako je, na primer, za oceno 8 potrebno rešiti naloge za oceno 6, 7 in 8.

Namig: sam sem na začetku programa definiral niza

stolpci = "abcdefgh" vrstice = "12345678" in se potem v skoraj vseh funkcijah pridno sprehajal po njima. Res sta mi prišla prav, vesel sem, da sem to storil.

Za oceno 6

0. Če želiš, napiši funkcijo stolpec_prost(stolpec, razpored), ki kot argument prejme oznako stolpca in razpored kraljic ter vrne True, če v danem stolpcu ni nobene kraljice.

   Primer:

   >>> stolpec_prost("b", ["a4", "c7", "d2"]) True >>> stolpec_prost("c", ["a4", "c7", "d2"]) False

1. Napiši funkcijo prosti_stolpci(razpored), ki kot argument prejme razpored kraljic in kot rezultat vrne seznam vseh stolpcev, v katerih ni nobene kraljice. Pri reševanju ti bo v pomoč gornja funkcija, če si jo napisal (če je nisi, pa nič).

   Primer:

   >>> prosti_stolpci(["a4", "c7", "d2"]) ["b", "e", "f", "g", "h"] >>> prosti_stolpci(["h8", "a4", "b4", "c7", "g8", "d2", "e1", "f3"])) [] >>> prosti_stolpci([]) ["a", "b", "c", "d", "e", "f", "g", "h"]

2. Napiši funkcijo prost_stolpec(razpored), ki kot argument prejme razpored kraljic in kot rezultat vrne prvi stolpec, v katerem ni nobene kraljice. Če takšnega stolpca ni, vrne None. Funkcija naj uporablja gornjo funkcijo!

   Primer:

   >>> prost_stolpec(["a4", "c7", "d2"]) "b" >>> print(prost_stolpec(["h8", "a4", "b4", "c7", "g8", "d2", "e1", "f3"])) None >>> prost_stolpec([]) "a"

Za oceno 7

3. Napiši funkcijo napada(polje1, polje2), ki kot argument prejme koordinati dveh polj ter vrne True, če se polji napadata in False, če se ne. Dogovorimo se, da polje napada tudi samo sebe.

   Primer:

   >>> napada("a4", "a7") True >>> napada("a4", "e4") True >>> napada("a4", "a4") True >>> napada("a4", "c6") True >>> napada("a4", "c2") True >>> napada("a4", "c1") False

4. Napiši funkcijo napadajo(polje, razpored), ki kot argument prejme koordinate polja in razpored kraljic, kot rezultat pa vrne seznam vseh kraljic, ki napadajo podano polje. Funkcija naj kliče gornjo funkcijo!

   Primer:

   >>> napadajo("c2", ["a4", "c7", "d2"]) ["a4", "c7", "d2"] >>> napadajo("c6", ["a4", "c7"]) ["a4", "c7"] >>> napadajo("e8", ["a4", "c7", "d2"]) ["a4"] >>> napadajo("a4", ["a4", "c7", "d2"]) ["a4"] >>> napadajo("g8", ["a4", "c7", "d2"]) []

5. Napiši funkcijo napadeno(polje, razpored), ki kot argument prejme koordinate polja in razpored kraljic, kot rezultat pa vrne True, če katera od kraljic napada izbrano polje, sicer pa False. Funkcija naj na primeren način kliče gornjo funkcijo!

   Primer:

   >>> napadeno("a7", ["a4", "c7", "d2"]) True >>> napadeno("a6", ["a4", "c7"]) True >>> napadeno("h5", ["a4", "c7", "d2"]) False >>> napadeno("a4", []) False

Za oceno 8

6. Napiši funkcijo prosto_v_stolpcu(stolpec, razpored), ki kot argument prejme oznako stolpca in razpored kraljic, vrne pa seznam koordinat polj v njem, ki še niso napadena. Funkcija naj pokliče ustrezno gornjo funkcijo. >>> prosto_v_stolpcu("a", ["a4", "c7", "d2"]) [] >>> prosto_v_stolpcu("b", ["a4", "c7", "d2"]) ["b1"] >>> prosto_v_stolpcu("f", ["a4", "c7", "d2"]) ["f1", "f3", "f5", "f6", "f8"] >>> prosto_v_stolpcu("f", []) ["f1", "f2", "f3", "f4", "f5", "f6", "f7", "f8"]

7. Napiši funkcijo prosto_polje(razpored), ki kot argument prejme razpored kraljic, vrne pa koordinato prvega prostega polja - pri čemer s prvim mislimo čim bolj levo polje, znotraj polj v istem stolpcu pa tisto, ki je v vrstici z nižjim indeksom (če so prosta a2, a4 in b1, naj vrne a2). Če prostega polja ni, naj vrne None. Funkcija naj uporablja funkcijo za iskanje prostih stolpcev in funkcijo za iskanje prostih vrstic znotraj stolpca. >>> prosto_polje(["a4", "c7", "d2"]) "b1" >>> prosto_polje([]) "a1" >>> print(prosto_polje(["f1", "f2", "f3", "f4", "f5", "f6", "f7", "f8"])) None

Za oceno 9

8. Napiši funkcijo napadajoce_se(razpored), ki kot argument dobi nek razpored kraljic in kot rezultat vrne vse pare kraljic, ki se napadajo med sabo. Vsak par naj bo izpisan le enkrat! Funkcija naj uporablja ustrezno funkcijo izmed gornjih.
>>> napadajoce_se(["a4", "b1", "b7"]) [('b1', 'b7')] >>> napadajoce_se(["a4", "b1", "e8"]) [('a4', 'e8')] >>> napadajoce_se(["a4", "b1", "e4"]) [('a4', 'e4'), ('b1', 'e4')] >>> napadajoce_se(["a4", "b1", "e4", "f2"]) [('a4', 'e4'), ('b1', 'e4')] >>> napadajoce_se(["a4", "b1"]) [] >>> napadajoce_se(["a4", "b1", "c5", "d8", "e2", "f7", "g3", "h6"]) [] >>> napadajoce_se(["a1", "a2", "a3", "a4"]) [('a1', 'a2'), ('a1', 'a3'), ('a2', 'a3'), ('a1', 'a4'), ('a2', 'a4'), ('a3', 'a4')]
9. Napiši funkcij legalna(postavitev), ki kot argument dobi nek razpored in pove, ali je "legalen". Razpored je legalen, če vsebuje osem kraljic, ki se ne napadajo med sabo. Funkcija naj uporablja gornjo funkcijo.
>>> legalna(["a4", "b1", "c5", "d8", "e2", "f7", "g3", "h6"]) True >>> legalna(["a4", "b1", "c5", "d8", "e2", "f7", "g3"]) False >>> legalna(["a4", "b1", "c5", "d8", "e2", "f7", "g3", "h3"]) False

Za oceno 10

10. Samostojno napiši program, ki razporedi osem kraljic po šahovnici tako, da se medsebojno ne napadajo. Rezultat naj bo v obliki seznama, kakršni so zgornji.

    Sprogramirati moraš tudi vse gornje funkcije, ni pa ti jih potrebno uporabljati.

Rešitev

Kot je namigoval namig, najprej pripravimo niza s črkami, ki predstavljajo stolpce in številkami, ki predstavljajo vrstice. Kdor je nalogo reševal brez njih, bo videl, koliko je z njimi lažje. Kdor je reševal z njimi, naj poskusi brez, pa bo videl, koliko je težje.

stolpci = "abcdefgh" vrstice = "12345678" Zdaj pa akcija.

Rešitve za začetnike

def stolpec_prost(stolpec, postavitev): for p in postavitev: if p[0] == stolpec: return False return True

V ozadju funkcije je ista "fraza", kot jo imamo, recimo, v funkciji, ki ugotavlja, ali je število praštevilo: čim ugotovimo, da ni (da ni praštevilo ali pa da stolpec ni prost), vrnemo False. Če ne vrnemo False, pa na koncu, šele po zanki, vrnemo True.

Naslednja - poišči proste stolpce - je res preprosta (no, enako bomo rekli tudi pri vseh naslednjih ;)). Gremo prek seznama stolpcev (for s in stolpci), za vsakega pokličemo gornjo funkcijo, da izvemo, ali je prost. Če je, ga dodamo na seznam prostih stolpcev, sicer ne. Na koncu funkcije vrnemo seznam prostih.

def prosti_stolpci(postavitev): prosti = [] for s in stolpci: if stolpec_prost(s, postavitev): prosti.append(s) return prosti

Pa naslednja? Ta je šele enostavna! Potrebujemo prvi prost stolpec, napisali pa smo si že funkcijo, ki vrne vse proste stolpce? Pot odtod do konca ni dolga. Pokličemo funkcijo, ki vrne vse proste stolpce in če seznam ni prazen, vrnemo prvega. Če je, ne vrnemo ničesar in funkcija torej vrne None, kot vse funkcije, ki ne vračajo ničesar.

def prost_stolpec(postavitev): prosti = prosti_stolpci(postavitev) if prosti: return prosti[0]

In tako pridemo do najpreprostejše doslej. Ne zanke ne pogoja ne potrebuje. Dve polji se napadata, če sta v istem stolpcu (polje1[0]==polje2[0]), isti vrstici (polje1[0]==polje2[0]) ali pa na isti diagonali. Slednje merimo tako, da pretvorimo vse koordinate v njihove kode ASCII - s funkcijo ord, ki ste jo prav v ta namen "slučajno" srečali na vajah. Če je absolutna vrednost razlik koordinat enaka - pomaknemo se enako stolpcev levo/desno kot vrstic gor/dol - sta polji na isti diagonali.

def napada(polje1, polje2): return polje1[0]==polje2[0] or \ polje1[1]==polje2[1] or \ abs(ord(polje1[0])-ord(polje2[0]))==abs(ord(polje1[1])-ord(polje2[1]))

Ko je ta funkcija napisana, se lahko le še smejimo naslednji: dano polje napadajo tiste kraljice, ki stojijo na poljih, ki napadajo dano polje. Napadalke bomo zbirali v istoimenskem seznamu; za vsako kraljico iz dane postavitve preverimo, ali napada podano polje in jo po potrebi dodamo na seznam.

def napadajo(polje, postavitev): napadalke = [] for kraljica in postavitev: if napada(kraljica, polje): napadalke.append(kraljica) return napadalke

Naslednja funkcija ... ah, polje je napadeno, če ga kaka kraljica napada.

def napadeno(polje, postavitev): return len(napadajo(polje, postavitev)) > 0

Prosta polja so polja, ki jih nihče ne napada. Zapeljemo se prek vrstic, jih sestavimo skupaj s stolpcem (stolpec+vrstica) in preverimo, ali je polje napadeno. Če ni, ga dodamo na seznam prostih.

def prosto_v_stolpcu(stolpec, postavitev): prosta = [] for vrstica in vrstice: if not napadeno(stolpec+vrstica, postavitev): prosta.append(stolpec+vrstica) return prosta

Do prvega prostega polja pridemo tako, da gremo prek vseh stolpcev in za vsakega povprašamo, ali je v njem kaj prostih polj. Če so, vrnemo prvega. Sicer nadaljujemo. Če ne najdemo ničesar, ne vrnemo ničesar ... in s tem smo vrnili None.

def prosto_polje(postavitev): stolpec = prost_stolpec(postavitev) if stolpec: vrstica = prosto_v_stolpcu(stolpec, postavitev) if vrstica: return vrstica[0]

In potem pride prva (in zadnja) resna naloga (recimo). Potrebujemo vse pare kraljic, torej naredimo dve zanki. Da pa bi vsak par dobili le enkrat, "enumeriramo" kraljice. Spremenljivka i vsebuje indeks kraljice kraljica1. V notranji zanki pogledamo le vse kraljice do i-te. Če se tidve polji napadata, dodamo par kraljic v seznam napadajočih se. Ker naloga nekako nakazuje, naj bi bil par urejen po abecedi (oz. v enakem vrstnem redu, kot so navedene kraljice), damo v par najprej kraljica2 in nato kraljica1.

def napadajoce_se(postavitev): napadajoce = [] for i, kraljica1 in enumerate(postavitev): for kraljica2 in postavitev[:i]: if napada(kraljica1, kraljica2): napadajoce.append((kraljica2, kraljica1)) return napadajoce

In še zadnja: postavitev je legalna, če vsebuje osem kraljic in je seznam napadajočih se prazen.

def legalna(postavitev): return len(postavitev)==8 and not napadajoce_se(postavitev)

"Industrijske" rešitve

V jeziku, ki premore osnove funkcijskega programiranja, teh nalog noben zaresen programer ne bi reševal tako, kot smo jih zgoraj. Tule so hitrejše rešitve; zaenkrat za znalce, ostali pa se bomo tega učili enkrat decembra. (Seveda bi se dalo tudi vse ostalo spisati krajše, vendar je tule ideja, da napišemo spodobno, tako, kot bi napisali v praksi.)

def stolpec_prost(stolpec, postavitev): return not any(x[0]==stolpec for x in postavitev) def prosti_stolpci(postavitev): return [s for s in stolpci if stolpec_prost(s, postavitev)] def prost_stolpec(postavitev): prosti = prosti_stolpci(postavitev) if prosti: return prosti[0] def napada(polje1, polje2): return polje1[0]==polje2[0] or polje1[1]==polje2[1] or \ abs(ord(polje1[0])-ord(polje2[0]))==abs(int(polje1[1])-int(polje2[1])) def napadajo(polje, postavitev): return [kraljica for kraljica in postavitev if napada(kraljica, polje)] def napadeno(polje, postavitev): return bool(napadajo(polje, postavitev)) def prosto_v_stolpcu(stolpec, postavitev): return [stolpec+vrstica for vrstica in vrstice if not napadajo(stolpec+vrstica, postavitev)] def prosto_polje(postavitev): stolpec = prost_stolpec(postavitev) if stolpec: vrstica = prosto_v_stolpcu(stolpec, postavitev) if vrstica: return vrstica[0] def napadajoce_se(postavitev): return [(kraljica2, kraljica1) for i, kraljica1 in enumerate(postavitev) for kraljica2 in postavitev[:i] if napada(kraljica1, kraljica2)] def legalna(postavitev): return len(postavitev)==8 and not napadajoce_se(postavitev)

Tipične napake

Tule je nekaj tipičnih napak (poleg prepisovanja, ki je vedno največja napaka).

• seznam[:1] ne vrne prvega elementa seznama temveč seznam s prvim elementom.
• Ne pišite if napada(polje, razpored[x]) == True: temveč if napada(polje, razpored[x]):.
• Podobno je tole if b==1: return False else: return True Zadoščalo bi return b==1.
• Tudi letos opažamo return "True". Funkcija naj ne vrača niza True temveč vrednost True. True je konstanta, tako kot pi ali 42. Tudi številke 42 ne pišemo pod narekovaje, kadar jo hočemo vrniti (razen, če hočemo vrniti niz 42, ne številke).
• Stavka return None na koncu funkcije ni potrebno pisati. (Ni pa prepovedano.)

Za konec še enkrat prosimo, da uporabljate Python 3.0 ali višji, saj bodo prihodnje naloge z njim veliko lažje rešljive. Poleg tega nam olajšate popravljanje, če oddajate nestisnjene datoteke .py, ne arhivov .rar ali .zip.