eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Судоку

Судоку

Лимит времени 15 секунд
Лимит использования памяти 64 MiB

О, нет! Билл просто понял, что эта Судоку, над решением которой он провел последние десять минут, по существу, была задачей с прошлой недели, только повернутой против часовой стрелки. Как дешево! Неужели журнал не может позволить себе новую задачу каждую неделю? Конечно, он не имел возможности узнать об этом, прежде чем он начал ее решать, да и пустые места для заполнения цифрами были иными, чем на прошлой неделе. Тем не менее, понимание того, что на этой неделе головоломка была простой производной от задачи на прошлой неделе, конечно, доставило удовольствие большее, чем решение всего остального.

Поле для Судоку состоит из таблицы 9×9 клеток. Они могут быть сгруппированы в 3×3 областях размером 3×3 клетки каждая. Некоторые клетки заполнены цифрами от 1 до 9, а остальные остаются пустыми. Цель игры состоит в том, чтобы заполнить каждую пустую клетку цифрой 1...9 так, чтобы в каждой строке, каждом столбце и в каждой области содержалось каждая из цифр 1...9 только один раз. Правильное судоку всегда имеет ровно одно решение.

Помогите Биллу избежать неприятных сюрпризов, написав программу, которая проверит, являются ли нерешенные Судоку на самом деле производными от более ранних задач, полученные с помощью простых операций.

Разрешенными операциями являются:

  1. Вращение всей головоломки по часовой стрелке или против часовой стрелки.

  2. Обмен двух столбцов в колонке размером 3×9 в одном сегменте.

  3. Обмен двух строк в полосе размером 9×3 в одном сегменте.

  4. Обмен местами сегментов строк и столбцов.

  5. Применение перестановки f цифр 1...9 в каждой клетке (например, замена х на f(x) в каждой клетке).

Считается, что операция выполняется над решённым Судоку (а не над нерешенными задачами), также всегда гарантируется, что если существовало решение до преобразования Судоку, то оно существует и после него.

Входные данные

Входные данные начинаются со строки с указанием количества тестов 0N50.

Далее для каждого теста следуют девять строк с описанием решения головоломки на прошлой неделе, построчно сверху донизу. Каждая строка соответствует строке в головоломке и состоит из девяти цифр (1...9), описывающих содержимое ячеек слева направо.

После решения на прошлой неделе следуют блоки по девять строк с описанием нерешенных задач на этой неделе. Здесь, кроме того, что каждая строка соответствует строкам головоломки и каждая цифра (0...9) описывает содержимое ячейки, цифра 0 означает, что ячейка пуста. Строки представлены по порядку сверху вниз, по одной в строке, ячейки упорядочены слева направо.

После каждого теста, кроме последнего следует пустая строка. Каждая нерешенная головоломка гарантированно будет однозначно разрешима, как и решение на прошлой неделе, и это всегда будет правильное решение Судоку.

Выходные данные

Для каждого теста выведите Yes, если Судоку может быть получено из заданного решения головоломки с использованием разрешенных операций, или No, если это не представляется возможным.

Пример

Входные данные #1
2
963174258
178325649
254689731
821437596
496852317
735961824
589713462
317246985
642598173
060104050
200000001
008305600
800407006
006000300
700901004
500000002
040508070
007206900

534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
010900605
025060070
870000902
702050043
000204000
490010508
107000056
040080210
208001090
Выходные данные #1
Yes
No