1. Zuzkino sudoku vzorové riešenie

Zadanie

Zuzka rada rieši a ešte radšej vytvára sudoku. Vo svojom rodnom meste dokonca vytvárala každý týždeň jedno sudoku pre miestny časopis.

Jedného dňa jej napísal vydavateľ celoslovenského denníka s ponukou, či by nechcela sudokami zásobovať celé Slovensko každý deň. Na každý deň by musela vytvoriť ľahkú, strednú aj ťažkú variantu. To je ale veľa práce, však? Ak by Zuzka ponuku prijala, síce by si zarobila, no nemala by čas na školu, spánok a kamarátov¹.

Zuzka je ale programátorka, a preto nebude sudoku vyrábať ručne, ale programom. Nie je to však také jednoduché. Pri tvorbe si totiž treba dať záležať na tom, aby mali riešitelia z riešenia sudoku dobrý zážitok. Sudoku, v ktorom chýbajú iba jednotky, je veľmi nezáživné. Také, do ktorého treba počas riešenia doplniť rôzne čísla je rozhodne zaujímavejšie.

Pomôžte Zuzke zistiť, ktoré sudoku sú tie zaujímavejšie. Napíšte program, ktorý pre dané sudoku zistí, koľko ktorých čísel treba do sudoku doplniť pre jeho vyriešenie.

Úloha

Sudoku sa hrá nasledovne. Dostanete tabuľku s \(9 \times 9\) políčkami. Tabuľka je rozdelená na \(3 \times 3\) bloky po \(3 \times 3\) políčkach. Na každom políčku je buď číslo od 1 po 9 alebo je políčko voľné. Úlohou v sudoku je doplniť čísla na všetky prázdne políčka tak, aby sa v žiadnom riadku, stĺpci ani v bloku nezopakovalo žiadne z čísel 1 až 9 viac ako raz.

Vašou úlohou je pre daný popis sudoku zistiť, koľko ktorých čísel doň treba doplniť.

Formát vstupu

Na vstupe dostanete 9 riadkov. V každom z nich bude 9 čísel v rozsahu od 0 po 9 oddelených medzerami. Čísla 0 reprezentujú nevyplnené políčka sudoku.

Môžete predpokladať, že sudoku zo vstupu sa dá vyriešiť – teda napríklad v žiadnom riadku, stĺpci ani v bloku sa nezopakuje to isté číslo (okrem nuly).

Formát výstupu

Vypíšte 9 riadkov. Ak riadky očíslujeme od 1 po 9, na \(i\)-tom z nich sa má nachádzať jedno celé číslo – počet čísel \(i\), ktoré treba do sudoku doplniť.

Príklad

Input:

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

Output:

2
0
1
2
1
2
1
1
3

Jednotka chýba v piatom a v šiestom riadku. Dvojky sú všade tam, kde majú byť, …

---

1. Veľa ľudí sa aj bez vytvárania sudoku sťažuje, že majú čas len na dve zo spomenutých troch vecí.↩

Vzhľadom na to, že každý vstup obsahoval iba \(9\times9\) čísel (čiže každý vstup bol malý), mohli ste v tejto úlohe robiť všeličo. Mohli ste rekurziou vyriešiť sudoku, mohli ste pre každý riadok zisťovať, čo v ňom chýba…

Na vyriešenie tejto úlohy však nebolo nič z toho potrebné a stačilo spraviť jediné pozorovanie: v každom vyriešenom sudoku sa nachádza každé číslo (1-9) práve deväťkrát. Raz v každom stĺpci a stĺpcov je 9. Raz v každom riadku a riadkov je 9. Raz v každom bloku a blokov je 9.

Preto nám bude stačiť prečítať vstup, spočítať, koľko je v zadaní jednotiek, dvojok, …, deviatok a vypísať čísla \(9 - pocet\_jednotiek, 9 - pocet\_dvojok, \dots, 9 - pocet\_deviatok\).

Na pamätanie počtov jednotlivých čísel môžeme použiť 9 premenných, ale krajšie riešenie je použiť pole pocet_cisel[], ktoré si inicializujeme na samé nuly. Potom načítame zo vstupu 81 čísel a zakaždým zvýšime dané políčko poľa.

#include <cstdio>

int main(){
    int pocet_cisel[10] = {0};

    for(int i = 0; i < 9 * 9; i++){
        int c;
        scanf(" %d", &c);
        pocet_cisel[c]++;
    }
    
    for(int i = 1; i <= 9; i++)
        printf("%d\n", 9 - pocet_cisel[i]);

    return 0;
}

Veľmi podobným spôsobom si môžeme v poli pamätať, koľko čísel \(i\) treba doplniť. Pole inicializujeme na samé deviatky a pri čítaní vstupu odčítame jednotku za každý výskyt čísla.

treba_doplnit = [9] * 10

for i in range(9):
    cisla_v_riadku = map(int, input().split())
    for cislo in cisla_v_riadku:
        treba_doplnit[cislo] -= 1

print("\n".join(map(str, treba_doplnit[1:])))

Časová zložitosť

Hoci vstup je konštantnej (vždy rovnakej) veľkosti, a mohli by sme povedať, že program pracuje v konštantnom čase \(O(1)\)¹, tak informatívnejšie by bolo povedať niečo takéto: Ak si dĺžku štvorca sudoku označíme ako \(n\), potom náš algoritmus pracuje v čase \(O(n^2)\).

Z takéhoto tvrdenia sa dá usúdiť, že rovnakým algoritmom by ste vedeli vyriešiť úlohu, v ktorej by bolo sudoku veľkosti \(18\times18\), no trvalo by to 4-krát dlhšie.

Všimnite si rozdiel medzi pojmami \(program\) a \(algoritmus\). Hoci vyššie uvedené programy by vstupy veľkostí \(18 \times 18\) nevyriešili, rovnaká myšlienka, postup – algoritmus – sa dá použiť aj na riešenie vstupov rôznych veľkostí. Preto má zmysel hovoriť o časovej zložitosti algoritmu aj v tejto úlohe.

Pamäťová zložitosť

V našich riešeniach využívame len jedno pole veľkosti \(10\) (v riešení, ktoré je napísané v Pythone, si ešte pamätáme jeden riadok vstupu) a niekoľko jednoduchých premenných. Mohli by sme teda, takisto ako v časti o časovej zložitosti, povedať, že pamäťová zložitosť je konštantná od veľkosti vstupu, \(O(1)\). Informatívnejšie by ale bolo uviesť pamäťovú zložitosť lineárnu od dĺžky strany sudoku, \(O(n)\).