5. Poriadnejšia výzva

Táto úloha sa dá nahradiť riešením sady arrays_cpp na Liahni (betaliahen.ksp.sk) . Ak chceš, aby ti namiesto bodov za riešenie tejto úlohy boli započítané body získané riešením spomínanej sady, na stránke odovdzaj pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Andrejovi na

Výborne! Ani my nevieme skryť nadšenie z toho, koľkí z vás si poradili s našou výzvou – vyriešiť osemsmerovky a pomôcť tým Žabovej babke. Dokonca ste si tým vyslúžili aj jej rešpekt. Nastal však problém, ako to už býva, babka o osemsmerovky z tohto dôvodu stratila záujem a teraz nevie, čo robiť. Nádej prišla až včera ráno, keď zahliadla vo svojich obľúbených novinách nový typ hlavolamu s názvom sudoku. Zo začiatku si s ním nevedela dať rady, ale po chvíli v ňom už bola expertka.

Rozhodla sa, že si s vami tentokrát dá súťaž, keď už vám tie hlavolamy tak idú. Prebiehať to bude tak ako ste zvyknutí. Vy odovzdáte program a ona začne v tom istom čase riešiť. Ak to stihnete skôr ako ona, body sú vaše, ak nie, tak za daný pokus nič nedostanete. Babke trvá vyriešenie každej sudoku presne \(2\) sekundy. Vďaka súbojom s vami možno príde na lepšie metódy riešenia a tie vám po konci tejto série pošle, ako námet na riešenie.

Úloha

Sudoku je hra, v ktorej dostanete mriežku rozmerov \(9\times9\), v ktorej sú zo začiatku doplnené nejaké čísla a nejaké samozrejme chýbajú. Vašou úlohou je doplniť všetky prázdne políčka podľa nasledujúcich pravidiel:

1: do mriežky môžete doplniť iba čísla \(1\) až \(9\)

2: pre každý riadok musí platiť, že sa v ňom nachádza každé čislo práve raz

3: pre každý stĺpec musí platiť, že sa v ňom nachádza každé čislo práve raz

4: ak si rozdelíme túto mriežku \(9\) štvorčekov veľkosti \(3\times3\) tak ako na obrázku, musí platiť, že v každom sa nachádza každé čislo práve raz.

Čísla, ktoré sú na začiatku napísané vo vnútri mriežky samozrejme spĺňajú hore uvedené pravidlá.

Sudoku môže vyzerať napríklad nasledovne.

Na vstupe od nás dostanete jedno takéto sudoku s niekoľkými prázdnymi políčkami. Vašou úlohou je napísať program, ktorý dané sudoku vyrieši a vypíše na výstup.

Vstup

Na vstupe sa bude nachádzať presne \(9\) riadkov, pričom každý bude obsahovať \(9\) čísel. \(j\)-te číslo na \(i\)-tom riadku \(a_{i,j}\), reprezentuje číslo v \(i\)-tom riadku a \(j\)-tom stĺpci mriežky. Pre všetky \(a_{i,j}\) platí \(0 \leq a_{i,j} \leq 9\). Iste ste si všimli, že \(a_{i,j}\) je z rozsahu až \(10\) čísiel. Prázdne políčko budú reprezentované číslom \(0\). To znamená, že dopĺnať budete rovnako ako v pôvodnom sudoku iba čísla \(1\) až \(9\).

Výstup

Na výstup vypíšte správne doplnenú sudoku. Vašou úlohou je teda nahradiť všetky 0 zo vstupu tak, aby boli dodržané hore uvedené pravidlá. V prípade, že dané sudoku má viac riešení, vypíšte ľubovolné z nich. Môžete predpokladať, že každé zadané sudoku má aspoň jedno riešenie.

Sudoku vypisujte na výstup po riadkoch. Medzi jednotlivými číslami sa musia nachádzať medzery. To, či sa aj za posledným číslom v riadku bude nachádzať medzera alebo nie, je na vás, nespôsobí to chybu pri testovaní, avšak nezabudnite každý riadok oddeliť znakom konca riadku “\n”. Výstup má teda obsahovať \(9\) riadkov, pričom v každom sa bude nachádzať presne \(9\) čísel oddelených medzerou, reprezentujúcich jednotlivé políčka v sudoku, za ktorými bude nasledovať znak konca riadku.

Hodnotenie

Vaše riešenie bude ako obyčajne testované na rôznych sadách, ktoré sa budú líšiť obtiažnosťou ich riešenia.

Keďže riešiť menšie sudoku by bolo podvádzanie, sady sa líšia iba tým, koľko čísel v sudoku chýba.

• V prvej sade platí, že v každom riadku chýba práve jedno políčko.
• V druhej sade platí, že v každom stĺpci chýba práve jedno políčko.
• V tretej sade platí, že v každom bloku veľkosti 3x3 chýba práve jedno políčko.
• Vo štvrtej sade platí, že počas riešenia a dopĺňania vždy existuje aspoň jedno políčko, ktoré vieme jednoznačne doplniť z pohľadu na riadok, stĺpec a blok, v ktorom sa nachádza. Inak povedané, pre toto políčko iba jedno číslo spĺňa, že sa nenachádza v rovnakom stĺpci, riadku a bloku.
• V piatej sade neplatia žiadne obmedzenia.

Príklady

Input:

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

Output:

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

Vstup a výstup zodpovedá osemsmerovke zo zadania spolu s riešením.

Input:

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

Output:

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

Vstup, ktorý sa môže vyskytnúť aj v prvej aj v druhej sade.