Recentemente, recebi um novo aplicativo Sudoku que produz Sudoku realmente difícil, que não pode ser resolvido usando as estratégias padrão. Então eu tive que aprender alguns novos. Uma dessas estratégias é a estratégia Y-Wing . É classificado em "Estratégias difíceis", mas na verdade não é tão difícil.

Exemplo

Para esta estratégia, apenas 4 células são importantes. Portanto, eu ignorei todas as outras células nas imagens.

Analisamos todos os candidatos para cada célula. No exemplo a seguir, temos uma célula com os candidatos 3 7(isso significa que já rejeitamos os candidatos 1 2 4 5 6 8 9, por exemplo, porque há uma 1na mesma linha, uma 2na mesma caixa 3x3, ...), uma célula com os candidatos 6 7, uma célula com os candidatos 3 6e uma célula com os candidatos 2 6. A estratégia da asa em Y sugerirá que o valor 6pode ser removido dos candidatos da célula direta, deixando apenas um 2como candidato, que você pode preencher. Então, encontramos um número correto e estamos a um passo de resolver o Sudoku completo.

Primeiro Exemplo

Por que o pode 6ser removido?

Explicação

Vamos supor que esse 6seja o número correto para a célula direta. Agora, existe um 6nesta coluna; portanto, podemos remover os 6candidatos da célula superior direita, deixando apenas um 7, que podemos preencher. O mesmo acontece com a célula inferior esquerda. Podemos remover 6e preencher o arquivo 3. Agora, se olharmos para a célula superior esquerda, teremos uma contradição. Como agora já existe um 7na mesma linha e um 3na mesma coluna, podemos remover o 7e 3o candidato, sem deixar nenhum candidato. O que claramente não é possível. Portanto, o 6 não pode ser o número correto da célula direta.

Mais precisamente: se tivermos 4 células com os candidatos [A B] [A C] [C D] [B C](nesta ordem ou rotação circular) e as células estiverem conectadas (pela mesma linha, mesma coluna ou mesma caixa 3x3) em um círculo (a célula 1 está conectada à célula 2, que é conectado à célula 3, que está conectada à célula 4, que está conectada à célula 1), que você pode remover Cda [C D]célula. É crucial, que as três células [A B], [A C]e [B C]contêm apenas dois candidatos cada. Diferentemente, a célula [C D], que pode conter mais ou menos ( Dpode ser zero, um ou mais candidatos).

Exemplo com letras em vez de números

Observe que eu disse explicitamente que eles podem ser conectados de qualquer maneira. No próximo exemplo, você pode ver a estratégia aplicada novamente. Mas desta vez as 4 células não formam um retângulo. As células inferior esquerda e direita são simplesmente conectadas, porque estão na mesma caixa 3x3. Y-Wing diz que podemos remover o 1candidato da célula superior esquerda. Desta vez, ainda restam 2 candidatos nesta célula, então não encontramos um novo número correto. Mas, no entanto, a remoção da 1lata pode abrir portas para diferentes estratégias.

Segundo exemplo, não em um retângulo

Se você quiser mais informações sobre a estratégia ou quiser mais alguns exemplos, visite sudokuwiki.org .

Especificações do Desafio

Você receberá 4 listas como entrada, representando os candidatos das células. As quatro células estão conectadas como um círculo (a célula 1 está conectada à célula 2, que está conectada à célula 3, que está conectada à célula 4, que está conectada à célula 1). Você pode assumir que cada lista é classificada em ordem crescente.

Seu trabalho é remover um candidato (aplicando a estratégia Y-Wing) e retornando as listas de candidatos resultantes na mesma ordem. Se você não pode aplicar a estratégia, basta retornar as mesmas listas de candidatos.

Se houver duas soluções possíveis (você pode remover A da célula B ou C da célula D), retorne apenas uma solução. Não importa qual.

A entrada pode estar em qualquer formato nativo de lista ou matriz. Você também pode usar uma lista de listas ou algo semelhante. Você pode receber a entrada via STDIN, argumento de linha de comando, prompt ou argumento de função e retornar a saída via valor de retorno ou simplesmente imprimindo em STDOUT.

Isso é código-golfe. O código mais curto (em bytes) vence.

Casos de teste

[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] # -||-

code-golf sudoku Jakube
fonte

Vários conjuntos em uma única entrada podem ser exatamente iguais?

Optimizer

@Optimizer Sim, por exemplo, no 8º caso de teste, 7 8são os candidatos para a primeira e a segunda célula. A estratégia Y-Wing ainda pode ser aplicada.

Jakube

@Jakube ah tudo bem, não vi isso.

Otimizador

Se mais de uma solução for possível, posso produzir uma delas?

Optimizer

Sim, esclareci na pergunta.

Jakube

Estratégia Y-Wing para Sudoku

Exemplo

Explicação

Especificações do Desafio

Casos de teste

Respostas:

CJam, 90 bytes

Mathematica, 124 110 bytes