7. Daj het vzorové riešenie

1
5
15 12 14 14 24 
10 20 18 14 17
7 3 2 5 1
3 5 4 3 3
5 3 3 9 5
5 6 4 3 4
4 9 8 8 7

7 0 2 5 1
3 5 4 0 0
0 0 0 9 5
0 6 4 0 4
0 9 8 0 7

Inšpiráciou pre túto úlohu bola logická hra Rullo. Zadania, ktoré dostali vaše programy, len boli o čosi väčšie, ako tie, ktoré riešia ľudia.

Riešenie hrubou silou

Ako dať z mriežky preč tie správne čísla? Zamyslíme sa nad niečím šikovným, nič nevymyslíme, a tak sa rozhodneme vyskúšať hrubú silu.

Aj pri hrubej sile je ale veľa možností. Všetkých možností, ako z tabuľky rozmerov \(n\times n\) niektoré čísla vyhodiť a niektoré nechať je až \(2^{n^2}\), a to už od \(n=6\) začína byť nezvládnuteľne veľa možností.

Omnoho lepšie sú riešenia založené na tzv. backtrackingu (prehľadávaní s návratom). Pri takýchto riešeniach sa rozhodujeme postupne, políčko po políčku. Výhodou je, že po každom rozhodnutí môžeme spraviť rôzne kontroly a ak zistíme, že už určite nevieme vyrobiť žiadne platné riešenie, môžeme sa z aktuálnej “vetvy” prehľadávania rovno vrátiť a tak ušetriť veľa ďalšieho skúšania možností.

Pri našej úlohe si napríklad pre každý riadok aj stĺpec môžeme zvlášť pamätať súčet čísel, ktoré sme sa v ňom už rozhodli nechať, a zvlášť súčet čísel, o ktorých sme sa ešte nerozhodli. Potom vždy, keď spravíme nejaké rozhodnutie o ďalšom políčku, upravíme si tieto súčty pre jeho riadok a stĺpec, a následne pomocou nich zistíme, či ešte želané súčty pre ne ležia v zostrojiteľnom rozsahu.

Ďalšie zefektívnenie takéhoto typu riešení môže spočívať v šikovnejšej voľbe poradia, v ktorom sa o jednotlivých políčkach rozhodujeme. V princípe platí, že čím skôr o nejakej vetve zistíme, že k riešeniu nevedie, tým viac času ušetríme.

Kombinácia hrubej sily a dedukcie

Keby túto úlohu riešil človek, často by používal dedukciu: “Toto číslo nemôžem použiť, lebo by mi nesedela posledná cifra, tamto zas použiť musím, lebo by inak bol súčet primalý, a hento tiež, lebo by mi v stĺpci nesedela parita.” A vždy, keď nám z takejto dedukcie niečo vypadne, tak nám to môže pomôcť. Ak napríklad z pohľadu na riadok zistíme, že nejaké jeho políčko treba odstrániť, môžeme sa potom pozrieť na stĺpec a v ňom zrazu máme tiež o políčko menej.

Našou druhou cestou k riešeniu bude snaha spraviť program, ktorý bude vedieť robiť takéto dedukcie. Vopred síce nevieme, či nám pomôžu, ale za pokus to stojí – ak sa ukáže, že áno, máme lepšie riešenie, ak sa ukáže, že nie, aspoň sme sa naučili niečo nové o vlastnostiach tejto úlohy.

Hja, ale ako naučiť program robiť takéto dedukcie? K plnohodnotnej AI máme ďaleko a implementácia nejakých jednoduchých pravidiel nám asi žiadne ohromujúce výsledky nedá.

Existuje ale pekný systematický spôsob, ktorý môžeme použiť a ktorý zahrnie všetky možné veci, ktoré sa dajú vydedukovať len z toho jedného riadku či stĺpca. Trik je jednoduchý: Pozrieme sa na všetkých \(2^n\) možností, čo spraviť s dotyčným riadkom (respektíve menej, ak už sme o niektorých jeho políčkach rozhodnutí). Spomedzi všetkých možností si vyberieme všetky tie, ktoré vyrobia správny súčet. No a teraz sa pozrieme na to, na ktorých políčkach sa všetky tieto možnosti zhodujú. Takto sa dozvieme aj to, ktoré políčka určite musíme nechať, aj to, ktoré určite zahodiť.

(Elegantná implementácia je pomocou bitových vzoriek. Na čísla od \(0\) po \(2^n -1\) sa môžeme dívať ako na všetky možné \(n\)-tice bitov, teda ako na všetky možné postupnosti hovoriace, ktoré políčka zahodiť a ktoré zobrať. Keď si potom zoberieme všetky čísla, ktoré zodpovedali platným riešeniam pre dotyčný riadok, z ich bitového ANDu vidíme, kde mali všetky 1, a z ich bitového ORu zase to, kde mali všetky 0.)

Vyššie popísanú úvahu vieme postupne opakovať pre všetky riadky a stĺpce, až kým buď celú tabuľku nevyriešime, alebo sa nedostaneme do situácie, kedy už v žiadnom riadku ani stĺpci nevieme nič nové odvodiť. No a čo spravíme v tomto druhom prípade? Použijeme predchádzajúce riešenie – teda vyberieme si nejaké nerozhodnuté políčko a postupne rekurzívne vyskúšame obe možnosti preň.

Pri implementácii si potom ešte treba dať pozor na to, že vždy, keď sa ideme z rekurzie vrátiť, treba zabudnúť nie len na stav políčka, o ktorom sme sa priamo rozhodli, ale tiež na stav všetkých políčok, o ktorých sme po tom rozhodnutí vyššie popísanou dedukciou zistili, že zrazu už sú jednoznačne určené.

#include <bits/stdc++.h>
using namespace std;

int N;
vector< vector<int> > original_table;
vector<int> desired_row_sums, desired_col_sums;

vector< vector<int> > state;        // o kazdom policku: -1 este neviem, 0 zahodit, 1 nechat
vector< vector<int> > change_depth; // pomocne pole kde si pamatame, na ktorej urovni rekurzie sme zmenili stav pre toto policko

int min_row_sum(int r) { int answer=0; for (int c=0; c<N; ++c) if (state[r][c]==1) answer += original_table[r][c]; return answer; }
int max_row_sum(int r) { int answer=0; for (int c=0; c<N; ++c) if (state[r][c]!=0) answer += original_table[r][c]; return answer; }
int min_col_sum(int c) { int answer=0; for (int r=0; r<N; ++r) if (state[r][c]==1) answer += original_table[r][c]; return answer; }
int max_col_sum(int c) { int answer=0; for (int r=0; r<N; ++r) if (state[r][c]!=0) answer += original_table[r][c]; return answer; }

bool is_solved() {
    for (int r=0; r<N; ++r) for (int c=0; c<N; ++c) if (state[r][c] == -1) return false;
    for (int r=0; r<N; ++r) if (min_row_sum(r) != desired_row_sums[r]) return false;
    for (int c=0; c<N; ++c) if (min_col_sum(c) != desired_col_sums[c]) return false;
    return true;
}

void deduce_row(int r, int depth, bool &was_change, bool &was_contradiction) {
    vector<int> indices;
    for (int c=0; c<N; ++c) if (state[r][c] == -1) indices.push_back(c);
    vector<int> good_subsets;
    int S = indices.size();
    for (int subset=0; subset<(1<<S); ++subset) {
        for (int s=0; s<S; ++s) state[r][ indices[s] ] = (subset >> s) & 1;
        if (min_row_sum(r) == desired_row_sums[r]) good_subsets.push_back(subset);
    }
    for (int s=0; s<S; ++s) state[r][ indices[s] ] = -1;
    if (good_subsets.empty()) { was_contradiction = true; return; }

    int bitwise_and = (1<<S) - 1;
    for (int subset : good_subsets) bitwise_and &= subset;
    for (int s=0; s<S; ++s) if (bitwise_and & 1<<s) {
        state[r][ indices[s] ] = 1;
        change_depth[r][ indices[s] ] = depth;
        was_change = true;
    }

    int bitwise_or = 0;
    for (int subset : good_subsets) bitwise_or |= subset;
    for (int s=0; s<S; ++s) if (!(bitwise_or & 1<<s)) {
        state[r][ indices[s] ] = 0;
        change_depth[r][ indices[s] ] = depth;
        was_change = true;
    }
}

void deduce_col(int c, int depth, bool &was_change, bool &was_contradiction) {
    vector<int> indices;
    for (int r=0; r<N; ++r) if (state[r][c] == -1) indices.push_back(r);
    vector<int> good_subsets;
    int S = indices.size();
    for (int subset=0; subset<(1<<S); ++subset) {
        for (int s=0; s<S; ++s) state[ indices[s] ][c] = (subset >> s) & 1;
        if (min_col_sum(c) == desired_col_sums[c]) good_subsets.push_back(subset);
    }
    for (int s=0; s<S; ++s) state[ indices[s] ][c] = -1;
    if (good_subsets.empty()) { was_contradiction = true; return; }

    int bitwise_and = (1<<S) - 1;
    for (int subset : good_subsets) bitwise_and &= subset;
    for (int s=0; s<S; ++s) if (bitwise_and & 1<<s) {
        state[ indices[s] ][c] = 1;
        change_depth[ indices[s] ][c] = depth;
        was_change = true;
    }

    int bitwise_or = 0;
    for (int subset : good_subsets) bitwise_or |= subset;
    for (int s=0; s<S; ++s) if (!(bitwise_or & 1<<s)) {
        state[ indices[s] ][c] = 0;
        change_depth[ indices[s] ][c] = depth;
        was_change = true;
    }
}

void print() {
    for (int pr=0; pr<N; ++pr) {
        for (int pc=0; pc<N; ++pc) {
            if (state[pr][pc] == 1) cout << original_table[pr][pc];
            if (state[pr][pc] == 0) cout << 0;
            if (state[pr][pc] == -1) cout << original_table[pr][pc] << "?";
            cout << (pc==N-1 ? "\n" : " ");
        }
    }
}

bool go(int depth) {
    // zisti, ci nahodou nie je zjavne, ze aktualna vetva nevedie k rieseniu
    for (int r=0; r<N; ++r) if (min_row_sum(r) > desired_row_sums[r]) return false;
    for (int r=0; r<N; ++r) if (max_row_sum(r) < desired_row_sums[r]) return false;
    for (int c=0; c<N; ++c) if (min_col_sum(c) > desired_col_sums[c]) return false;
    for (int c=0; c<N; ++c) if (max_col_sum(c) < desired_col_sums[c]) return false;
    // dokola prechadzaj riadky a stlpce a rob pre ne dedukcie
    while (true) {
        bool was_change = false, was_contradiction = false;
        for (int r=0; r<N; ++r) deduce_row(r,depth,was_change,was_contradiction);
        for (int c=0; c<N; ++c) deduce_col(c,depth,was_change,was_contradiction);
        if (was_contradiction) {
            for (int r=0; r<N; ++r) for (int c=0; c<N; ++c) if (change_depth[r][c] == depth) state[r][c] = -1;
            return false;
        }
        if (!was_change) break;
    }
    // ak uz si vsetko vyriesil, vypis riesenie, inak rekurzivne skusaj dalsie policko
    if (is_solved()) {
        print();
        return true;
    }
    int nr=0, nc=0;
    while (state[nr][nc] != -1) { ++nc; if (nc==N) { nc=0; ++nr; } if (nr==N) break; }
    change_depth[nr][nc] = depth;
    state[nr][nc] = 1;
    if (go(depth+1)) return true;
    state[nr][nc] = 0;
    if (go(depth+1)) return true;
    for (int r=0; r<N; ++r) for (int c=0; c<N; ++c) if (change_depth[r][c] == depth) state[r][c] = -1;
    return false;
}

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> N;
        desired_row_sums.clear(); desired_row_sums.resize(N);
        desired_col_sums.clear(); desired_col_sums.resize(N);
        original_table.clear();   original_table.resize(N, vector<int>(N));
        state.clear();            state.resize(N, vector<int>(N,-1));
        change_depth.clear();     change_depth.resize(N, vector<int>(N,-1));
        for (int n=0; n<N; ++n) cin >> desired_row_sums[n];
        for (int n=0; n<N; ++n) cin >> desired_col_sums[n];
        for (int r=0; r<N; ++r) for (int c=0; c<N; ++c) cin >> original_table[r][c];
        go(0);
    }
}

Nechám oboje na niekoho iného

“Robenie dedukcií” a “skúšanie možností” sú natoľko bežné súčasti riešenia problémov, že už zrejme niekto prišiel na to, ako spraviť špecializované nástroje, ktoré sú fakt dobré v jednom aj druhom.

Jedným zo základných typov takýchto nástrojov sú tzv. SAT solvery. Ich použitie funguje nasledovne: Zoberieme problém, ktorý chceme vyriešiť, zakódujeme jeho “pravidlá” do jedného veľkého logického výrazu, a potom poprosíme SAT solver, aby nám našiel, pre aké ohodnotenie premenných je celý tento výraz splnený. Ak to nedáva zmysel, nebojte sa, o chvíľu začne.

Ako môžeme našu úlohu zapísať ako logický výraz? Keď máme tabuľku \(n\times n\), začneme tým, že budeme mať \(n^2\) boolovských premenných: pre každé políčko jednu premennú, ktorá nám hovorí, či je súčasťou riešenia.

Logický výraz, ktorý sme pred chvíľou spomínali, bude veľkou konjunkciou (t.j. logickým ANDom) veľa podmienok, ktoré musia tieto premenné spĺňať, aby sme dokopy dostali platné riešenie. Presnejšie, vstup pre bežný SAT solver musí byť v špecifickom tvare, tzv. konjuktívnej normálnej forme. To znamená, že musí byť vyššie popísaného tvaru a navyše môžeme používať len veľmi jednoduché podmienky. Každá podmienka musí byť tvaru “spomedzi týchto premenných a týchto ich negácií musí byť aspoň jedna pravdivá”. Teda napríklad môžeme mať v našej úlohe podmienku tvaru “zober políčko (3,2) alebo zober políčko (3,7) alebo zahoď políčko (3,1)”.

Logický výraz, ktorý zostrojíme, bude ANDom \(2n\) sád podmienok: jedna sada pre každý riadok aj stĺpec. Každá sada podmienok bude hovoriť “táto sada premenných musí byť taká, aby sedel súčet tohto riadku / stĺpca”. Ako toto dosiahnuť? Jednoducho tak, že si hrubou silou vygenerujeme všetky zlé kombinácie premenných a každú z nich jednou podmienkou zakážeme. (Ak nechceme, aby nastala situácia “zahoď (3,2) a zahoď (3,7) a zober (3,1)”, pridáme podmienku, ktorá je jej negáciou – čiže podmienku, ktorú sme uviedli ako príklad v minulom odseku.) Pre každý riadok a stĺpec takto vygenerujeme najviac \(2^n\) zlých kombinácií, každú s najviac \(n\) premennými a celkovo teda bude mať logický výraz dĺžku \(O(n^2 \cdot 2^n)\). Logický výraz – vstup pre SAT solver – musíme, samozrejme, skonštruovať pomocou vlastnoručne napísaného programu.

Viac o tejto téme sa dozviete v zadaní a riešení staršej úlohy KSP: úloha “Ono to rieši samo!” (31. ročník KSP, úloha 5 v prvom kole zimnej časti).

Za záver

Riešenie už síce skončilo, my si ale povieme ešte niečo navyše. Prečo sme sa uspokojili len s riešeniami používajúcimi hrubú silu a nehľadali sme napríklad lepšie riešenie, ktoré by úlohu vždy vyriešilo v čase \(O(n^2)\)? Preto, že vieme dokázať, že táto úloha je ťažká.

Jednou zo známych algoritmických úloh, o ktorých sa vie, že sú ťažké (natoľko, že sa všeobecne verí, že nemajú žiadne polynomiálne riešenie) je úloha SubsetSum: “Tu máš sadu prirodzených čísel \(a_0,\dots,a_{n-1}\) a cieľovú hodnotu \(s\), existuje nejaká podmnožina daných čísel, ktorá má súčet presne \(s\)?” No a riešiť našu úlohu je aspoň tak ťažké, ako riešiť SubsetSum. Totiž ľubovoľné zadanie SubsetSum vieme prerobiť na zadanie našej úlohy. Stačí si spraviť tabuľku, kde v riadku \(i\) a stĺpci \(j\) máme číslo \(a_{(i+j)\bmod n}\), a predpísať, že v každom riadku aj stĺpci chceme dostať súčet \(s\).

Ak by teda existoval efektívny algoritmus pre našu úlohu, dostali by sme aj efektívny algoritmus pre SubsetSum. A keďže ten zrejme neexistuje, nemá zmysel sa snažiť ani pre našu úlohu.

(To, čo sme si práve predviedli, bola redukcia, ktorá dokazuje, že náš problém je rovnako ako SubsetSum jedným z tzv. NP-ťažkých rozhodovacích problémov.)