Су-доміно-ку#3108

Су-доміно-ку

1 секунда

64 мегабайти

Складна

Ніби вже й так не було достатньо головоломок, схожих на судоку, у випуску журналу Games Magazine за липень 2009 року описано варіант, що поєднує елементи як судоку, так і доміно. У стандартному судоку є сітка розміром $9 \times 9$ 9 \times 9, яку потрібно заповнити, використовуючи лише цифри від $1$ до $9$ . У правильному розв'язку:

Кожен рядок має містити кожну з цифр від $1$ до $9$ .
Кожен стовпець має містити кожну з цифр від $1$ до $9$ .
Кожен із зазначених квадратів $3 \times 3$ 3 \times 3 має містити кожну з цифр від $1$ до $9$ .

У су-доміно-ку девʼять довільних клітинок ініціалізовані числами від $1$ до $9$ . Це залишає $72$ клітинки. Їх потрібно заповнити, використовуючи набір із $36$ доміно. Набір містить одне доміно для кожної можливої пари різних чисел від $1$ до $9$ (наприклад, $1 + 2$ 1+2, $1 + 3$ 1+3, $1 + 4$ 1+4, $1 + 5$ 1+5, $1 + 6$ 1+6, $1 + 7$ 1+7, $1 + 8$ 1+8, $1 + 9$ 1+9, $2 + 3$ 2+3, $2 + 4$ 2+4, $2 + 5$ 2+5, ...). Зверніть увагу, що у наборі немає окремих доміно $1 + 2$ 1+2 та $2 + 1$ 2+1; одне доміно можна обертати в будь-який бік. Доміно може перетинати межі квадратів $3 \times 3$ 3 \times 3 (наприклад, доміно $2 + 9$ 2+9 у зразку).

Щоби допомогти, кожну головоломку на початку подано з кількома вже розміщеними доміно. Наприклад, рисунок 1 показує зразок головоломки у початковому стані. Рисунок 2 показує єдиний розв'язок цієї головоломки.

Вхідні дані

Кожен опис головоломки починається з рядка, що містить ціле число $N$ , $10 \leq N \leq 35$ 10 \leq N \leq 35, яке відповідає кількості доміно, розміщених на початку. Далі йдуть $N$ рядків, кожен з яких описує одне доміно у вигляді $U$ $LU$ $V$ $L V$ . Значення $U$ — одне з чисел на доміно, а $LU$ — двосимвольний рядок, що позначає розташування $U$ на полі, як показано на рисунку 1. Змінні $V$ і $L V$ — відповідно значення й розташування другої половинки доміно. Наприклад, у першому зразку вхідних даних перше доміно описано як $6$ $B 2$ $1$ $B 3$ . Це відповідає доміно з числами $6 + 1$ 6+1, розміщеному так, що $6$ знаходиться у рядку $B$ , стовпці $2$ , а $1$ — у рядку $B$ , стовпці $3$ . Для будь-якого доміно дві його частини завжди будуть у сусідніх клітинках.

Після опису $N$ доміно останній рядок описує початкові розташування одиночних номерів від $1$ до $9$ , використовуючи ту саму систему позначень рядок-стовпець. Усі початкові числа та доміно будуть на унікальних позиціях.

Введення закінчується рядком, що містить $0$ ; цей рядок не обробляється.

Вихідні дані

Для кожної головоломки виведіть рядок, що ідентифікує номер головоломки, як показано нижче. Далі виведіть розв'язок у вигляді матриці $9 \times 9$ 9 \times 9. Для кожної головоломки існує лише один розв'язок.

Приклади

Приклад 1