• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

در این سوال شما باید جدول سودوکو $9 \times 9$ داده‌شده را حل کنید. جدول سودوکو جدولی‌ست که اعداد ۱ تا ۹ در هر سطر آن و ستون آن و در ۹ ناحیه $3 * 3$ آن بدون تکرار چیده شده‌اند.

توجه: برای جدول داده‌شده در ورودی لزوماً یک حل وجود ندارد و یک ورودی می تواند چندین حل داشته باشد. شما کافی‌ست که یک‌ حل را بیابید. در ضمن تضمین می‌شود که جداول ورودی حتماً قابل حل هستند.

ورودی

۹ خط که هر خط شامل ۹ عدد میباشد. عدد صفر به منزله خالی بودن آن خانه است که در واقع الگوریتم شما باید آن خانه را پر کند.

خروجی

۹ خط که هر خط شامل ۹ عدد می‌باشد و جدول حل‌شده کامل ورودی است.

مثال

ورودی نمونه ۱

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

خروجی نمونه ۱

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