Prihlásenie Registrácia  

SVK-B - Sudoku

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Hra Sudoku sa hrá na mriežke 9 x 9, ktorá je navyše rozdelená do 9 navzájom neprekrývajúcich sa štvorcov 3 x 3. V niektorých políčkach mriežky sa nachádzajú celé čísla od 1 do 9, ostatné sú prázdne. Úlohou je doplniť prázdne políčka číslami 1-9 tak, aby sa v každom riadku, v každom stĺpci a v každom malom štvorci každé číslo vyskytovalo práve raz.

Keďže táto úloha je pomerne ťažká, budeme sa zaoberať zjednodušenou verziou hry Sudoku. Mriežka bude mať rozmery 4 x 4 a bude rozdelená na 4 štvorce rozmerov 2 x 2. Do políčok sa vpisujú len čísla 1-4.

Úloha

Daná je čiastočne zaplnená mriežka 4 x 4. Úlohou je zistiť, či sa dajú do prázdnych políčok vpísať čísla 1-4 tak, aby výsledná matica obsahovala v každom riadku, v každom stĺpci a vo všetkých 4 malých štvorcoch 2 x 2 každé číslo práve raz a ak áno, vypísať jedno riešenie.

Vstup

Vstup obsahuje 4 riadky, na každom 4 čísla oddelené jednou medzerou. Prázdne políčka matice sú označené nulou. Môžete predpokladať, že vstup obsahuje aspoň jednu nulu.

Výstup

Ak sa dajú čísla vpísať, obsahuje výstup vyplnenú maticu v rovnakom formáte, ako bola zadaná na vstupe. V opačnom prípade obsahuje len jeden riadok s textom "Neda sa" (bez úvodzoviek).

Príklad

Vstup:

1 2 3 4
3 4 1 2
2 1 4 3
4 3 2 0

Výstup:

1 2 3 4
3 4 1 2
2 1 4 3
4 3 2 1