Recientemente recibí una nueva aplicación Sudoku que produce Sudoku realmente difícil, que no se puede resolver usando las estrategias estándar. Así que tuve que aprender algunos nuevos. Una de estas estrategias es la estrategia Y-Wing . Está clasificada en "Estrategias difíciles", pero en realidad no es tan difícil.

Ejemplo

Para esta estrategia, solo 4 celdas son importantes. Por lo tanto, ignoré todas las otras celdas en las imágenes.

Nos fijamos en todos los candidatos para cada celda. En el siguiente ejemplo tenemos una celda con los candidatos 3 7(eso significa que ya hemos rechazado a los candidatos 1 2 4 5 6 8 9, por ejemplo porque hay una 1en la misma fila, una 2en el mismo cuadro de 3x3, ...), una celda con los candidatos 6 7, una celda con los candidatos 3 6y una celda con los candidatos 2 6. La estrategia Y-Wing sugerirá que 6se puede eliminar de los candidatos de la celda franca, dejando solo un 2candidato, que puede completar. Así que encontramos un número correcto y estamos un paso más cerca para resolver el Sudoku completo.

¿Por qué se 6puede eliminar?

Explicación

Supongamos que 6es el número correcto para la celda franca. Ahora hay una 6en esta columna, por lo tanto, podemos eliminar la 6de los candidatos de la celda superior derecha, dejando solo una 7, que podemos completar. Lo mismo ocurre con la celda inferior izquierda. Podemos eliminar el 6y completar el 3. Ahora, si miramos la celda superior izquierda, obtenemos una contradicción. Porque ahora ya hay un 7en la misma fila y un 3en la misma columna, por lo que podemos eliminar el 7y el 3de los candidatos, sin dejar candidatos en absoluto. Lo que claramente no es posible. Por lo tanto, el 6 no puede ser el número correcto de la celda francamente.

Más precisamente: si tenemos 4 celdas con los candidatos [A B] [A C] [C D] [B C](en este orden o circular rotados) y las celdas están conectadas (a través de la misma fila, la misma columna o la misma caja de 3x3) en un círculo (la Celda 1 está conectada a la Celda 2, que es conectado a la celda 3, que está conectada a la celda 4, que está conectada a la celda 1), que puede eliminar Cde la [C D]celda. Es crucial, que las tres celdas [A B], [A C]y [B C]solo contengan dos candidatos cada una. De manera diferente, la célula [C D], que puede contener más o menos ( Dpuede ser cero, uno o incluso más candidatos).

Tenga en cuenta que explícitamente dije que se pueden conectar de cualquier manera. En el siguiente ejemplo, puede ver la estrategia aplicada nuevamente. Pero esta vez las 4 celdas no forman un rectángulo. Las celdas de abajo a la izquierda y de abajo están simplemente conectadas, porque están en el mismo cuadro de 3x3. Y-Wing dice que podemos eliminar al 1candidato de la celda superior izquierda. Esta vez todavía quedan 2 candidatos en esta celda, por lo que en realidad no encontramos un nuevo número correcto. Sin embargo, la eliminación de la 1lata puede abrir puertas a diferentes estrategias.

Si desea más información sobre la estrategia o desea algunos ejemplos más, visite sudokuwiki.org .

Especificaciones de desafío

Recibirá 4 listas como entrada, que representan a los candidatos de las celdas. Las cuatro celdas están conectadas como un círculo (la celda 1 está conectada a la celda 2, que está conectada a la celda 3, que está conectada a la celda 4, que está conectada a la celda 1). Puede suponer que cada lista está ordenada en orden ascendente.

Su trabajo es eliminar a un candidato (aplicando la estrategia Y-Wing) y devolver las listas de candidatos resultantes en el mismo orden. Si no puede aplicar la estrategia, simplemente devuelva las mismas listas de candidatos.

Si hay dos posibles soluciones (podría eliminar A de la celda B o eliminar C de la celda D), entonces devuelva solo una solución. No importa cuál.

La entrada puede estar en cualquier lista nativa o formato de matriz. También podría usar una lista de listas o algo similar. Puede recibir la entrada a través de STDIN, argumento de línea de comando, argumento de solicitud o función y devolver la salida a través del valor de retorno o simplemente imprimiendo en STDOUT.

Este es el código de golf. El código más corto (en bytes) gana.

Casos de prueba

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

CJam, 90 bytes

Ugghhh, esto es demasiado largo debido a la restricción de que las otras 3 celdas deberían tener solo 2 candidatos.

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

Esto espera entrada como una lista de lista en formato CJam. Por ej .:

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

da salida en una lista CJam de formato de lista:

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

Agregaré una explicación una vez que termine de jugar al golf.

Pruébelo en línea aquí o pruebe todo el conjunto de pruebas aquí .

Mathematica, 124 110 bytes

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])&

Ejemplos:

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}, {}}