Су-су-судоку
Су-су-судоку
В даний час практично усі грали в судоку: вам задано таблицю з комірок 9 на 9, яку ви повинні заповнити цифрами від 1 до 9 так, що
кожен рядок містить усі дев'ять цифр,
кожен стовбець містить усі дев'ять цифр, і
усі дев'ять підквадратів 3 на 3 містять усі дев'ять цифр.
Перед початком гри ви отримуєте частково заповнену таблицю, і вас просять заповнити ту частину квадрата, що залишилась. Одну з таких ломиголовок наведено нижче.
У цій задачі вам буде надано майже завершену таблицю Судоку, ви заповнили до цього майже усі клітинки, за винятном п'яти. Вас попросили завершити заповнення таблиці, або визначити, що це неможливо (Ви, можливо, вже зробили помилку!).
Вхідні дані
Перший рядок вхідних даних буде містити натуральне число, яке вказує на кількість наступних тестів. Кожен тест буде являти практично завершену таблицю Судоку, складатись з 9 рядків, кожен з яких містить 9 символів з набору цифр від 0 до 9. Там буде рівно п'ять 0 у кожному тесті, які вказують на п'ять незаповнених клітинок.
Вихідні дані
Для кожного тесту потрібно вивести
Could not complete this grid.
якщо неможливо виконати заповнення таблиці у відповідності з правилами гри, або вивести заповнену таблицю у форматі, наведеному нижче (у вихідних даних відсутні пропуски). Якщо є спосіб завершити заповнення сітки, то він буде унікальним. Відокремлюйте різні тести порожнім рядком.
Приклад
2 481253697 267948105 539671204 654389712 908704563 173562849 702136958 315897426 896425371 481253697 267948105 539671284 654289710 908704562 173562849 702136958 315897426 896425371
481253697 267948135 539671284 654389712 928714563 173562849 742136958 315897426 896425371 Could not complete this grid.