Головоломка с кубиками
Давайте попробуем решить головоломку с кубиками. Правила этой головоломки следующие:
1. В головоломке используются кубики с шестью гранями, как показано на Рисунке 1.
Рисунок 1. Грани кубика
2. Из двадцати семи таких кубиков строится 3×3×3 куб, как показано на Рисунке 2.
Рисунок 2. 3×3×3 куб
3. При построении куба из кубиков сумма чисел на гранях соседних кубиков, которые соприкасаются друг с другом, должна быть равна семи (см. Рисунок 3). Например, если одна грань пары отмечена "2", то другая грань должна быть "5".
Рисунок 3. Пара граней, соприкасающихся друг с другом
4. Верхний и передний виды куба частично заданы, то есть числа на гранях некоторых кубиков сверху и спереди известны.
Рисунок 4. Верхний и передний виды куба
5. Цель головоломки - найти все возможные расположения кубиков, которые соответствуют заданной информации о верхнем и переднем виде.
Ваша задача - написать программу, которая решает эту головоломку.
Входные данные
Входные данные состоят из нескольких наборов данных в следующем формате.
N
Набор_данных_1
Набор_данных_2
...
Набор_данных_N
N - это количество наборов данных.
Формат каждого набора данных следующий.
T_11 T_12 T_13
T_21 T_22 T_23
T_31 T_32 T_33
F_11 F_12 F_13
F_21 F_22 F_23
F_31 F_32 F_33
T_ij и F_ij (1 ≤ i ≤ 3, 1 ≤ j ≤ 3) - это грани кубиков, появляющиеся на верхнем и переднем видах, как показано на Рисунке 7, или ноль. Ноль означает, что грань в соответствующей позиции неизвестна.
Выходные данные
Для каждого возможного расположения кубиков вычислите сумму чисел, отмеченных на девяти гранях, появляющихся на правой стороне куба, то есть, с обозначениями, данными на Рисунке 2,
Для каждого набора данных вы должны вывести суммы правого вида для всех возможных расположений в порядке возрастания и без дубликатов. Числа должны быть разделены одним пробелом.
Когда для набора данных нет возможных расположений, выведите ноль.
Например, предположим, что верхний и передний виды заданы следующим образом.
Рисунок 5.
Существует четыре возможных правых вида, как показано на Рисунке 6. Суммы правого вида равны 33, 36, 32 и 33, соответственно. После их упорядочивания в порядке возрастания и удаления дубликатов, ответ должен быть "32 33 36".
Вывод должен быть одной строкой для каждого набора данных. Вывод может содержать пробелы в конце строк.
Рисунок 6.