Программист и шестиугольник
Цель этой задачи - решить головоломку, состоящую из 7 деревянных кусков шестиугольной формы (далее будем их просто называть "шестиугольниками"), которые необходимо положить на 7 колышек, закрепленных в деревянной основе. Колышки пронумерованы, как показано на Рисунке 1. Колышки пронумерованы (от 0 до 6) для удобства дальнейшего изложения. Шестиугольники пронумерованы заглавными буквами от 'A' до 'G' (как на Рисунке 2). У каждой стороны шестиугольника приписано целое число (от 0 до 9 включительно).
Можно заметить, что когда 7 шестиугольников положить на 7 колышек, то 3 ребра каждого внешнего шестиугольника и все ребра шестиугольника на колышке 0 являются соседними со сторонами некоторых других шестиугольников. Для решения головоломки необходимо найти расположение и ориентацию всех 7 шестиугольников таким образом, чтобы числа, записанные на прилегающих друг к другу сторонах шестиугольников, были одинаковыми. (см. Рисунок 3).
Рисунок 3 - Вид сверху на решенную головоломку
Программа должна прочитать описание семи шестиугольников, найти решение используя эти 7 шестиугольников (если такое существует), и вывести описание решения головоломки. Если решение не единственно, то можно вывести любое из них (когда найдено одно решение, то можно вращать шестиугольник на колышке 0 и соответственно другие шестиугольники, попробовав получить другие решения). Если решения не существует, то программа должна выдать соответствующее сообщение. После вывода решения на одну головоломку, программа должна считать данные следующей, и так следует продолжать до конца входных данных.
Входные данные
Входные данные состоят из нескольких тестов, каждый из которых задает описание набора шестиугольников. Каждая из первых 7 строк содержит по 6 цифр (без пробелов). Это цифры, которые записаны на 6 сторонах каждого шестиугольника. В первой строке приведены числа, записанные на шестиугольнике 'A'. Числа второй строки соответствуют шестиугольнику 'B', и так далее до 7 строки, числа которой принадлежат шестиугольнику 'G'. Первая цифра в каждой строке - это цифра на стороне, находящейся в положении "12 Часов" или "Верх". Следующие 5 цифр - числа на сторонах, расположенных по часовой стрелке от стороны "TOP". Например, шестиугольник на рисунке 2 можно представить строкой 123456. Как можно заметить на рисунке 3, стороны шестиугольника НЕ обязательно содержат разные числа.
После 7 строк, описывающих множество шестиугольников, имеется строка из одной звездочки (*) в колонке 1, которая используется для разделения между множествами шестиугольников. После нахождения ответа для текущего множества шестиугольников, и до конца файла, Ваша программа должна прочитать следующие 7 строк представляющие собой описание следующего множества шестиугольников - следует решать новую головоломку. Звездочка следует после каждого множества, включая последнее.
Выходные данные
Вывести решение для каждого входного множества шестиугольников. В решении следует указать, какой шестиугольник должен быть надет на колышек 0, на колышек 1, на колышек 2, ... и на колышек 6. Для каждого шестиугольника следует также описать его ориентацию. Таким образом, следует вывести 3 колонки информации. Колонка 1 содержит список колышек от 0 до 6. Колонка 2 содержит список букв, описывающих какие шестиугольники кладутся на колышек 0, на колышек 1, ... и на колышек 6, именно в таком порядке. В колонке 3 представлен список чисел на сторонах шестиугольника, номер которого записан в колонке 2. Цифры должны начинаться со стороны в позиции "ВЕРХ", когда головоломка решена. Следующие 5 цифр соответствуют сторонам в порядке обхода по часовой стрелке. Каждая колонка должна иметь название. Название первой колонки "PEG". Название второй колонки "HEX", а третьей "POSITION".
Если для некоторого множества шестиугольников решения не существует, то следует вывести сообщение: "No solutions possible". После описания каждого решения вывести строку из 36 звездочек "*" (или после сообщения "No solutions possible") для отделения решений головоломок друг от друга.