Су-домино-ку
Решив, что существующих судоку-подобных головоломок как будто уже не достаточно, в июле 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 решение заданного судоку, которое может быть получено с заданным набором домино. Гарантируется, что решение для каждой головоломки будет уникальным.