Y-Wing стратегия для судоку

11

Недавно я получил новое приложение Судоку, которое производит действительно тяжелые Судоку, которые не могут быть решены с помощью стандартных стратегий. Поэтому мне пришлось выучить несколько новых. Одна из этих стратегий - стратегия 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] # -||-
Jakube
источник
Могут ли несколько наборов в одном входе быть одинаковыми?
Оптимизатор
@Optimizer Да, например, в 8-м тесте, 7 8это кандидаты в первую и вторую ячейку. Стратегия Y-Wing все еще может быть применена.
Якуб
@ Якуб, ну ладно, не видел этого.
Оптимизатор
Если возможно более 1 решения, могу ли я вывести одно из них?
Оптимизатор
Да, я уточнил это в вопросе.
Якуб

Ответы:

3

CJam, 90 байтов

Угу, это слишком долго из-за ограничения, что в остальных 3 ячейках должно быть только 2 кандидата.

l~_:_(a+2/::&_{,}$2>:&:Y;{:PY&Y{P1<}?~}%:X,3>1${,}$W=_,2>\Y&,1?*{X:_(+2/{~:I=}#)_2$=I-t}&p

Это ожидает ввода в виде списка списка в формате CJam. Например:

[[2 6] [3 6] [3 7] [6 7]]

дает вывод в виде списка в формате CJam:

[[2] [3 6] [3 7] [6 7]]

Добавлю объяснение, как только я закончу играть в гольф ..

Попробуйте онлайн здесь или попробуйте весь набор тестов здесь .

оптимизатор
источник
3

Mathematica, 124 110 байт

Cases[e@n_:>n]/@(Plus@@e/@#&/@#/.NestList[RotateLeft/@#&,{x:a_+b_,y:b_+c_,z:c_+a_,w:a_+_.}->{x,y,z,w-a+1},3])&

Примеры:

In[1]:= yWing = Cases[e@n_:>n]/@(Plus@@e/@#&/@#/.NestList[RotateLeft/@#&,{x:a_+b_,y:b_+c_,z:c_+a_,w:a_+_.}->{x,y,z,w-a+1},3])& ;

In[2]:= yWing[{{3, 7}, {6, 7}, {2, 6}, {3, 6}}]

Out[2]= {{3, 7}, {6, 7}, {2}, {3, 6}}

In[3]:= yWing[{{4, 7}, {7, 8}, {4, 8}, {4}}]

Out[3]= {{4, 7}, {7, 8}, {4, 8}, {}}
alephalpha
источник