Недавно я получил новое приложение Судоку, которое производит действительно тяжелые Судоку, которые не могут быть решены с помощью стандартных стратегий. Поэтому мне пришлось выучить несколько новых. Одна из этих стратегий - стратегия Y-Wing . Он относится к категории «Жесткие стратегии», но на самом деле это не так сложно.
пример
Для этой стратегии важны только 4 клетки. Поэтому я игнорировал все остальные ячейки на изображениях.
Мы смотрим на всех кандидатов для каждой ячейки. В следующем примере у нас есть ячейка с кандидатами 3 7(это означает, что мы уже отклонили кандидатов 1 2 4 5 6 8 9, например, потому что есть 1в той же строке, a 2в том же блоке 3x3, ...), ячейка с кандидатами 6 7, ячейка с кандидатами 3 6и ячейка с кандидатами 2 6. Стратегия Y-Wing предполагает, что их 6можно удалить из кандидатов в прямую ячейку, оставив только 2кандидата в качестве кандидата, который вы можете заполнить. Таким образом, мы нашли правильное число и на шаг ближе к решению полной судоку.
Почему можно 6удалить?
объяснение
Предположим, что 6это правильное число для прямой ячейки. Теперь 6в этом столбце есть a , поэтому мы можем удалить 6из кандидатов в верхней правой ячейке, оставив только a 7, который мы можем заполнить. То же самое происходит с левой нижней ячейкой. Мы можем удалить 6и заполнить 3. Теперь, если мы посмотрим на верхнюю левую ячейку, мы получим противоречие. Потому что теперь уже есть 7в той же строке и 3в том же столбце, так что мы можем удалить 7и 3из кандидатов, не оставляя кандидатов вообще. Что явно не возможно. Следовательно, 6 не может быть правильным числом прямой ячейки.
Точнее: если у нас есть 4 ячейки с кандидатами [A B] [A C] [C D] [B C](в этом порядке или повернутыми по кругу), и ячейки соединены (через одну и ту же строку, тот же столбец или тот же ящик 3x3) в круг (ячейка 1 подключена к ячейке 2, которая является подключен к ячейке 3, которая подключена к ячейке 4, которая подключена к ячейке 1), чем вы можете удалить Cиз [C D]ячейки. Очень важно, что три клетки [A B], [A C]и [B C]содержит только два кандидата каждых. Иными словами, ячейка [C D], которая может содержать больше или меньше ( Dможет быть ноль, один или даже несколько кандидатов).
Обратите внимание, что я прямо сказал, что они могут быть подключены в любом случае. В следующем примере вы можете увидеть, что стратегия применяется снова. Но на этот раз 4 ячейки не образуют прямоугольник. Внизу слева и прямо ячейки просто связаны, потому что они находятся в той же коробке 3x3. Y-Wing говорит, что мы можем удалить в 1качестве кандидата верхнюю левую ячейку. На этот раз в этой ячейке осталось 2 кандидата, поэтому мы не нашли нового правильного числа. Но тем не менее удаление 1может открыть двери для разных стратегий.
Если вы хотите получить больше информации о стратегии или еще несколько примеров, посетите sudokuwiki.org .
Технические требования
В качестве входных данных вы получите 4 списка, представляющих кандидатов в ячейки. Четыре ячейки связаны как круг (Ячейка 1 связана с Ячейкой 2, которая связана с Ячейкой 3, которая связана с Ячейкой 4, которая связана с Ячейкой 1). Можно предположить, что каждый список отсортирован в порядке возрастания.
Ваша задача - удалить одного кандидата (применив стратегию Y-Wing) и вернуть полученные списки кандидатов в том же порядке. Если вы не можете применить стратегию, просто верните те же списки кандидатов.
Если есть два возможных решения (вы можете удалить A из ячейки B или C из ячейки D), тогда верните только одно решение. Неважно, какой.
Ввод может быть в любом родном списке или формате массива. Вы также можете использовать список списков или что-то подобное. Вы можете получать ввод через STDIN, аргумент командной строки, приглашение или аргумент функции и возвращать вывод через возвращаемое значение или просто печатая в STDOUT.
Это код-гольф. Самый короткий код (в байтах) выигрывает.
Тестовые случаи
[3 7] [6 7] [2 6] [3 6] => [3 7] [6 7] [2] [3 6] # Example 1
[6 7] [2 6] [3 6] [3 7] => [6 7] [2] [3 6] [3 7] # Example 1, different order
[2 6] [3 6] [3 7] [6 7] => [2] [3 6] [3 7] [6 7] # Example 1, different order
[3 6] [3 7] [6 7] [2 6] => [3 6] [3 7] [6 7] [2] # Example 1, different order
[1 2 8] [1 8] [8 9] [1 9] => [2 8] [1 8] [8 9] [1 9] # Example 2
[3 8] [4 8] [3 4 8] [3 4] => [3 8] [4 8] [3 8] [3 4]
[1 3 6 7 8] [3 8] [3 4] [4 8] => [1 3 6 7] [3 8] [3 4] [4 8]
[7 8] [7 8] [4 7] [4 8] => [7 8] [8] [4 7] [4 8] or [7] [7 8] [4 7] [4 8]
[4 7] [7 8] [4 8] [4] => [4 7] [7 8] [4 8] [] # Fictional example
[3 7] [2 6] [6 7] [3 6] => [3 7] [2 6] [6 7] [3 6] # Y-Wing can't be applied here
[4 7] [2 7 8] [4 8] [1 4] => [4 7] [2 7 8] [4 8] [1 4] # -||-
7 8это кандидаты в первую и вторую ячейку. Стратегия Y-Wing все еще может быть применена.Ответы:
CJam, 90 байтов
Угу, это слишком долго из-за ограничения, что в остальных 3 ячейках должно быть только 2 кандидата.
Это ожидает ввода в виде списка списка в формате CJam. Например:
дает вывод в виде списка в формате CJam:
Добавлю объяснение, как только я закончу играть в гольф ..
Попробуйте онлайн здесь или попробуйте весь набор тестов здесь .
источник
Mathematica,
124110 байтПримеры:
источник