Sudo Ku
Национална Олимпиада по Информатика 2010, Кръг 1
Time Limit: 0.1s, Memory Limit: 64MiB
Ели намира за ужасно неуважително към преподавателите това човек да се гримира в час. По тази причина тя се занимава с къде-къде по-уважителни занимания, като например да играе судоку. След определен момент играта става тривиална – тоест винаги има ред, колона или квадратче 3 на 3, в което липсва точно едно число. Елеонора нарича тази фаза само „ку”, тъй като е краят на играта, както и „ку” е краят на думата „судоку”. Вместо да довършва сама тази вече безмислена (за нея) игра, тя я дава на Вас с думите „sudo ku”, като очаква вие да го сторите вместо нея. Вие пък решавате да напишете програма, която да прави това.

За тези от Вас, които не знаят какво представлява играта Судоку, ето накратко правилата: Дадена ви е числова матрица с 9 реда и 9 колони. Някои от позициите могат да бъдат празни – тоест не се знае какво има на тяхно място, други вече попълнени. Вие трябва да допопълните празните позиции така, че във всеки ред и всяка колона от матрицата да има всички числа от 1 до 9. Също така ако разделим матрицата на 9 квадрата 3 на 3, всеки от тях трябва отново да съдържа числата 1..9 (вижте примерния изход за пояснение).
Вход
На стандартния вход Вашата програма ще получи почти-попълнено судоку, което може да бъде довършено като на всеки ход се намери ред, колона или квадратче 3 на 3, в което липсва точно едно число. Судокуто е зададено като матрица от 9 на 9 цифри, всяка от които е нула, ако квадратчето е неизвестно, или от 1 до 9 ако даденото поле е известно.
Изход
На стандартния изход изведете решението под формата на 9 числа на 9 реда.
Примерен Вход Примерен Изход
5 3 4 6 7 8 9 1 2 6 0 2 0 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 0 7 0 1 9 6 3 5 3 4 5 2 8 6 1 7 9 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9
В това Ку липсват 4 числа и можем да го решим със следните стъпки:
  1. В най-горния ляв квадрат, съставен от числата {5, 3, 4, 6, ?, 2, 1, 9, 8}, има точно едно липсващо и то е 7.
  2. Във втора колона вече има точно едно липсващо число и то е 8.
  3. Във втори ред също вече има точно едно липсващо число и то е 1.
  4. В четвърта колона (или в осми ред) има едно липсващо число и то е 4.
Забележете, че има и други начини, по които то може да се дореши, но всички водят до един и същ резултат.
Мрън!