Soutěž: Machr na algoritmy - Sudoku

Jak již název machra napovídá, budete si tentokrát hrát se sudoku. Přesněji řečeno ho budete řešit. Ještě přesněji řečeno napíšete konzolovou aplikaci, která ho vyřeší za vás.

Vstup bude vypadat nějak takto:

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

(mezi znaky jsou mezery, rozložení chybějících čísel může být jakékoli)
Výstup bude stejný, jen místo podtržítek vypíšete doplněné číslice.

Pokud by se stalo, že řešení existuje více, vypište jedno z nich, je jedno které.

Povolené jazyky: C, C++, C#, Pascal, Java, Python
Pokud budete chtít použít jiný (nebo budete mít nějaký dotaz k soutěži), zeptejte se v komentářích.