Су-доміно-ку
Вирішивши, що існуючих судоку-подібних головоломок ніби вже не достатньо, у липні 2009 року черговий випуск журналу цієї гри описує наступний варіант, який поєднує у собі аспекти як судоку, так і доміно. Нагадаємо, що звична загадка у вигляді стандартного судоку, полягає у тому, що уся сітка дев'ять на дев'ять повинна бути заповнена, використовуючи лише цифри від 1 до 9. В успішному розв'язку:
Кожен рядок повинен містити кожну з цифр від 1 до 9.
Кожен стовбчик повинен містити кожну з цифр від 1 до 9.
Кожен з вказани три на три квадратів повинен містити кожну з цифр від 1 до 9.
Для Су-доміно-ку, дев'ять довільних клітинок ініціалізуються числами від 1 до 9. Це залишає 72 вільних клітинок. Вони повинні бути заповнені з урахуванням використання наступного набору з 36 плиток доміно. Плитка цього набору доміно включає у себе по одній доміношці з кожною можливою парою з унікальними числами віт 1 до 9 (наприклад, 1+2, 1+3, 1+4, 1+5, 1+6, 1+7, 1+8, 1+9, 2+3, 2+4, 2+5, ...). Також відмітимо, що немає окремо доміношок 1+2 та 2+1 у комплекті, є лише одна така доміношка, але вона може бути повернута у довільній орієнтації. Крім того, зверніть увагу, що доміно можуть перетинати границю квадратів три на три (наприклад, як доміношка 2+9 у наведеному нижче прикладі).
Щоб допомогти вам, ми розпочнемо розв'язання кожної головоломки, визначаючи місцезнаходження деяких з доміно. Наприклад, на рисунку 1 показано приклад головоломки у початковому стані. На рисунку 2 показано єдиний спосіб розв'язати цю головоломку.
Вхідні дані
Опис кожної головоломки розпочинається з рядка, який містить ціле число N, 10 ≤ N ≤ 35, що задає число доміно, які вже розміщено у початковій конфігурації. Після цього йде N рядків, кожен з яких описує одну доміношку як U LU V LV. Значення U є значенням одного з чисел на доміно, і LU складається з двох символів і вказує розміщення значення U на полі, як показано вище на схематичному рисунку 1. Змінні V та LV задають відповідне значення та місце розміщення іншої половинки доміношки. Наприклад, у першому прикладі вхідних даних першу доміношку описано як 6 В2 1 В3. Це відповідає доміношці зі значення 6+1 і її розміщено на полі так, що число 6 буде знаходитись у рядку В та колонці 2, а значення 1 - у рядку B та колонці 3. Два місця для заданої доміношки завжди будуть сусідніми.
Після специфікації N доміношок йде останній рядок, який описує початкове розміщення окремих чисел від 1 до 9, при допомозі такого ж опису рядка та стовбця їх розміщення на полі. Усі початкові цифры та доміношки будут знаходитись в унікальних позиціях.
Вхідні дані завершуються рядком, який містить 0, і цей рядок не опрацьовується.
Вихідні дані
Для кожної головоломки спочатку виведіть рядок з визначенням номера завдання, як показано нижче. Після цього виведіть у матриці 9x9 розв'язання заданого судоку, яке може бути отримано з заданим набором доміно. Гарантується, що розв'язання для кожної головоломки буде унікальним.