Судоку
О, нет! Билл просто понял, что эта Судоку, над решением которой он провел последние десять минут, по существу, была задачей с прошлой недели, только повернутой против часовой стрелки. Как дешево! Неужели журнал не может позволить себе новую задачу каждую неделю? Конечно, он не имел возможности узнать об этом, прежде чем он начал ее решать, да и пустые места для заполнения цифрами были иными, чем на прошлой неделе. Тем не менее, понимание того, что на этой неделе головоломка была простой производной от задачи на прошлой неделе, конечно, доставило удовольствие большее, чем решение всего остального.
Поле для Судоку состоит из таблицы 9×9 клеток. Они могут быть сгруппированы в 3×3 областях размером 3×3 клетки каждая. Некоторые клетки заполнены цифрами от 1 до 9, а остальные остаются пустыми. Цель игры состоит в том, чтобы заполнить каждую пустую клетку цифрой 1...9 так, чтобы в каждой строке, каждом столбце и в каждой области содержалось каждая из цифр 1...9 только один раз. Правильное судоку всегда имеет ровно одно решение.
Помогите Биллу избежать неприятных сюрпризов, написав программу, которая проверит, являются ли нерешенные Судоку на самом деле производными от более ранних задач, полученные с помощью простых операций.
Разрешенными операциями являются:
Вращение всей головоломки по часовой стрелке или против часовой стрелки.
Обмен двух столбцов в колонке размером 3×9 в одном сегменте.
Обмен двух строк в полосе размером 9×3 в одном сегменте.
Обмен местами сегментов строк и столбцов.
Применение перестановки f цифр 1...9 в каждой клетке (например, замена х на f(x) в каждой клетке).
Считается, что операция выполняется над решённым Судоку (а не над нерешенными задачами), также всегда гарантируется, что если существовало решение до преобразования Судоку, то оно существует и после него.
Входные данные
Входные данные начинаются со строки с указанием количества тестов 0 ≤ N ≤ 50.
Далее для каждого теста следуют девять строк с описанием решения головоломки на прошлой неделе, построчно сверху донизу. Каждая строка соответствует строке в головоломке и состоит из девяти цифр (1...9), описывающих содержимое ячеек слева направо.
После решения на прошлой неделе следуют блоки по девять строк с описанием нерешенных задач на этой неделе. Здесь, кроме того, что каждая строка соответствует строкам головоломки и каждая цифра (0...9) описывает содержимое ячейки, цифра 0 означает, что ячейка пуста. Строки представлены по порядку сверху вниз, по одной в строке, ячейки упорядочены слева направо.
После каждого теста, кроме последнего следует пустая строка. Каждая нерешенная головоломка гарантированно будет однозначно разрешима, как и решение на прошлой неделе, и это всегда будет правильное решение Судоку.
Выходные данные
Для каждого теста выведите Yes, если Судоку может быть получено из заданного решения головоломки с использованием разрешенных операций, или No, если это не представляется возможным.