eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

Giriş verilənləri

Описание каждой головоломки начинается со строки, содержащей целое число N, 10N35, представляющее число домино, которые первоначально уже помещено в начальной конфигурации. После этого идёт N строк, каждая из которых описывает одну доминошку как ULU V LV. Значение U является значением одного из чисел на домино, и LU состоит из двух символов и указывает расположение значения U на поле, как показано выше на схематическом рисунке 1. Переменные V и LV представляет соответствующее значение и место расположения другой половинки доминошки. Например, в первом пример входных данных первая доминошка описана как 6 В2 1 В3. Это соответствует доминошке со значением 6+1 и она помещена на поле так, что число 6 будет находится в ряду В и колонке 2, а значение 1 - в строке B и колонке 3. Два места для заданной доминошки всегда будут соседними.

После спецификации N доминошек идёт последняя строка, описывающая начальное расположение отдельных чисел от 1 до 9, с помощью такого же описания строки и столбца их расположения на поле. Все начальные цифры и доминошки будут находится в уникальных позициях.

Входные данные заканчиваются строкой, содержащей 0, и эта строка не обрабатывается.

Çıxış verilənləri

Для каждой головоломки сначала выведите строку с определением номера задания, как показано ниже. После этого выведите в матрице 9x9 решение заданного судоку, которое может быть получено с заданным набором домино. Гарантируется, что решение для каждой головоломки будет уникальным.

Nümunə

Giriş verilənləri #1
10
6 B2 1 B3
2 C4 9 C3
6 D3 8 E3
7 E1 4 F1
8 B7 4 B8
3 F5 2 F6
7 F7 6 F8
5 G4 9 G5 
7 I8 8 I9
7 C9 2 B9
C5 A3 D9 I4 A9 E5 A2 C6 I1
11
5 I9 2 H9
6 A5 7 A6
4 B8 6 C8
3 B5 8 B4
3 C3 2 D3
9 D2 8 E2
3 G2 5 H2
1 A2 8 A1
1 H8 3 I8
8 I3 7 I4
4 I6 9 I7
I5 E6 D1 F2 B3 G9 H7 C9 E5
0
Çıxış verilənləri #1
Puzzle 1
872643195
361975842
549218637
126754983
738169254
495832761
284597316
657381429
913426578
Puzzle 2
814267593
965831247
273945168
392176854
586492371
741358629
137529486
459683712
628714935
Mənbə ACM Mid-Central Regional Programming Contest 2011