Počet bodov:
Popis:  6b
Program:  4b

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átov1.

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í.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.