3. Turnaj Mladých Šachistov vzorové riešenie

3
....k...
........
...H....
........
...h....
........
....K...
........

........
....h...
..k.....
.....H..
...K....
........
........
........

k..H....
...H....
.HH.....
........
........
......K.
........
........

Nemozna situacia.
Neutralna situacia.
Biely hrac ma mat.

4
k..H....
...H....
.HH.....
........
........
......K.
.r......
........

K.....Rr
R.h....r
........
........
rr......
.....k..
........
........

k.......
.......R
........
...B....
.R......
......K.
..q.....
........

........
..PPP...
..PkP...
...Pp...
...K....
........
........
........

Biely hrac ma sach.
Cierny hrac ma mat.
Biely hrac ma sach.
Cierny hrac ma sach.

Táto úloha bola trochu neklasická v tom, že jej obtiažnosť nespočívala vo vymyslení riešenia, ale jeho implementácií. Vzorák sa totiž prakticky nachádzal v samotnom zadaní:

“{farba} hrac ma sach.”, kde {farba} je “Biely”, resp. “Cierny”, ak je kráľ tohto hráča v ohrození, ale existuje platný ťah niektorou z jeho figúrok taký, po ktorom už v ohrození nebude.

Ak zistíme, že práve jeden kráľ je v ohrození, stačí nám vyskúšať každý ťah tohto hráča, a zakaždým sa spýtať znovu tú istú otázku – je kráľ v ohrození? Ak je aspoň raz odpoveď “nie”, odpovedáme šach, inak mat.

Vzhľadom na to že hlavným cieľom úlohy je donútiť riešiteľa si dopredu premyslieť ako túto jednu vetu naprogramovať čo najprehľadnejšie a bezbolestnejšie, hlavným cieľom vzoráku bude priblížiť ako k takémuto problému pristupovať, namiesto toho aby sa po vyslovení jednovetového riešenia prilepili strany hotového kódu.

Vzorové riešenie by teda, po prepísaní do pseudokódu, vyzeralo zatiaľ zhruba takto

string vyries()
{
    nacitaj a spracuj vstup

    B = je_ohrozeny(biely_kral,sachovnica)
    C = je_ohrozeny(cierny_kral,sachovnica)

    if B and C:
        return "Nemozna situacia."
    if !B and !C:
        return "Neutralna situacia."

    for priatelska_figurka in sachovnica:
        for nova_sachovnica in skus_vsetky_tahy(priatelska_figurka,sachovnica):
            if !je_ohrozeny(ohrozeny kral,nova_sachovnica):
                return farba + " hrac ma sach."

    return farba + " hrac ma mat."
}

main()
{
    t = input()
    while(t--)
        print(vyries())
}

Samozrejme vynechávam detaily ako načítanie vstupu a zapamätanie si pozícíí králov a pod. Štruktúra je tá dôležitá časť. Toto riešenie by teda bolo kompletné, ak by boli hotové funkcie je_ohrozeny(kto,kde) , ktorá zistí či figúrka kto na šachovnici kde je ohrozená nepriateľskými figúrkami, a skus_vsetky_tahy(kto,kde) ktorá zoberie figúrku kto a šachovnicu kde, a vygeneruje všetky možné šachovnice ktoré vzniknú tým, že touto figúrkou spravíme jeden ťah.

A teraz sa zamyslite, či sú si tieto funkcie navzájom podobné. Čo to vlastne znamená, že figúrka je v ohrození? No predsa to, že nejaká nepriateľská figúrka má taký ťah, ktorým sa posunie na pozíciu našej figúrky. Inak povedané, na overenie ohrozenosti vlastne chceme vyskúšať všetky ťahy nepriateľských figúrok. je_ohrozeny(kto,kde) teda, opäť odhliadnuc od detailov, vyzerá takto

bool je_ohrozeny(kto,kde)
{
    for nepriatel in nepriatelske_figurky:
        for nova_sachovnica in skus_vsetky_tahy(nepriatel,kde):
            if nova_sachovnica[pozicia kto] == nepriatel:
                return true
    return false
}

Ostáva nám teda už len skus_vsetky_tahy. Máme vlastne dva typy figúrok: tie ktoré majú určitý počet pohybov (kôň a kráľ) a tie ktoré maju určitý počet smerov, v ktorých môžu ísť kým nenarazia na prekážku (okraj šachovnice alebo figúrku). Môžeme teda napríklad zostrojiť dve funkcie, jedna ktorá vyskúša dané pohyby (a použijeme ju pre kráľa a kone), a jednu ktorá vyskúša pohyby v daných smeroch. Pešiakov bude jednoduchšie naprogramovať osobitne. Celé to môže vyzerať zhruba nasledovne

sachovnica[] niekolko_pohybov(figurka kto,sachovnica kde)
{
    sachovnica[] results

    for pohyb in kto.pohyby:
        if mozem(kto.pozicia + pohyb):
            tmp = kde[kto.pozicia + pohyb]
            kde[kto.pozicia] = '.'
            kde[kto.pozicia + pohyb] = kto
            results.append(kde)
            kde[kto.pozicia] = kto
            kde[kto.pozicia+pohyb] = tmp

    return results
}

sachovnica[] pohyb_v_smere(figurka kto,sachovnica kde)
{
    sachovnica[] results

    for smer in kto.pohyby:
        pohyb = smer
        while mozem(kto.pozicia+pohyb):
            tmp = kde[kto.pozicia + pohyb]
            kde[kto.pozicia] = '.'
            kde[kto.pozicia + pohyb] = kto
            results.append(kde)
            kde[kto.pozicia] = kto
            kde[kto.pozicia+pohyb] = tmp
            pohyb += smer

    return results
}

sachovnica[] skus_vsetky_pohyby(figurka kto, sachovnica kde)
{
    if kto == pesiak:
        //riešiť samostatne (zvoliť správny smer podľa farby, útočiť šikmo...)

    if kto == kral or kto == kon:
        return niekolko_pohybov(kto,kde)

    return pohyb_v_smere(kto,kde)

}

Pritom mozem(pozicia) vráti true ak je naša figúrka povolená pohnúť sa na dané políčko (teda nie je mimo šachovnice a nie je na nej priateľská figúrka). Tú tu uvádzať hádam nemusím.

Toto je teda kompletná štruktúra riešenia. Samozrejme, ešte chýba kopa práce utlačiť syntaktické detaily – napríklad pozicia by asi mala byť dvojica súradníc, každej figúrke musíme priradiť množinu pohybov vo forme dvojíc {dx,dy}, čo a ako si pamätáme o šachovnici, a tak ďalej, skúsenejším by však táto časť už nemala robiť veľké problémy.

Ak by ste si mali z tejto úlohy niečo odniesť, tak je to to, že riešenie úlohy nie vždy končí vymyslením algoritmu, naopak, niekedy to len začína. Vtedy je dobré si všetko pomaly dopredu premyslieť – chvíľkou rozvážneho plánovania štruktúry vášho programo si často môžete ušetriť hodiny programovania a najmä debugovania, jednoduchej myšlienky komplikovaným či zdĺhavým spôsobom.