Introducción
Reglas del rompecabezas:
El rompecabezas binario (también conocido como Takuzu o Subiku) es muy simple de entender y solo tiene unas pocas reglas:
dado que el nombre del juego es binario, es bastante obvio, pero solo puede completar ceros y unos.
- No más de dos del mismo dígito pueden ser vertical u horizontalmente adyacentes entre sí
- Cada fila y cada columna debe contener la misma cantidad de ceros y unos (esto implícitamente significa que cada juego binario siempre tendrá dimensiones pares).
- Puede que no haya filas duplicadas ni columnas duplicadas (con exactamente el mismo orden de ceros y unos).
Puedes jugar el juego en www.binarypuzzle.com si quieres.
Táctica:
Debido a la regla 1, siempre podemos completar un dígito si:
- Ya hay dos del mismo dígito adyacentes vertical u horizontalmente entre sí, en cuyo caso podemos completar el dígito opuesto en ambos lados. Es decir, .11...
→ 0110..
.
- Hay dos del mismo dígito vertical u horizontalmente con solo un espacio entre ellos. Es decir .1.1..
→.101..
Debido a la regla 1, cuando quedan tres huecos y no podemos tener tres adyacentes del mismo dígito, podemos completar uno de los huecos. Ie .0.1.0
→ 10.1.0
(Todavía tenemos que completar dos, y no podemos tener tres adyacentes en el medio, por lo que el primer espacio debe ser a 1
.)
Debido a la regla 2, siempre podemos completar los huecos restantes en una fila o columna si la mitad de ellos ya está llena con el dígito opuesto. Es decir .1.011
→010011
Debido a la regla 3, siempre podemos completar los dígitos opuestos si solo quedan dos para resolver en una línea igualmente ordenada. Es decir 101100 & 1..100
→101100 & 110100
Debido a la regla 3, a veces podemos llenar un espacio cuando quedan tres espacios en una línea igualmente ordenada. Ie 010011 & .1.01.
→ 010011 & .1.010
(Aquí no podemos completar 1
a al final, porque eso significaría que tenemos que completar ceros en los otros dos espacios, haciendo que ambas líneas sean iguales en orden).
Ejemplo:
Comenzamos con la siguiente cuadrícula de 6x6 con algunos unos y ceros rellenados (y los puntos son huecos que aún tenemos que rellenar):
.1....
.10.0.
1.11..
.1....
...1.0
......
Debido a las reglas 1 y 2, podemos completar estos dígitos:
.1.01.
.1010.
101100
010011
.0.1.0
.010..
Debido a la regla 1, podemos completar un 1 en la fila 5, columna 1:
.1.01.
.1010.
101100
010011
10.1.0
.010..
Debido a la regla 3, podemos completar un 0 en la fila 1, columna 6 (al mirar la fila 4):
.1.010
.1010.
101100
010011
10.1.0
.010..
Ahora podemos continuar llenando huecos con dígitos debido a las reglas 1 y 2:
.1.010
010101
101100
010011
10.1.0
.010.1
Ahora podemos terminar la fila 5 debido a la regla 3 (cuando miramos la fila 3):
.1.010
010101
101100
010011
100110
.010.1
Y luego podemos terminar el rompecabezas debido a las reglas 1 y 2:
011010
010101
101100
010011
100110
101001
Desafío:
El desafío es simple: dada la cuadrícula inicial, da salida al rompecabezas resuelto.
NOTA: No tiene que implementar las reglas anteriores. Por supuesto que puede, y debería darle pistas sobre cómo implementar este desafío, pero forzar la solución con las reglas en mente está completamente bien.
La forma en que lo resuelva depende de usted, pero el desafío es dar salida al rompecabezas resuelto.
Reglas de desafío:
- El formato de entrada y salida para la cuadrícula es flexible, pero indique lo que usa. (Es decir, conjunto de bytes 2D; cadena con nuevas líneas; etc.)
- Lo anterior también se aplica a los caracteres utilizados. En el ejemplo que he usado
01.
, pero si quieres puedes usarloABx
en su lugar. Indique qué formato de entrada / salida y qué caracteres ha utilizado. - Se puede suponer solamente se utilizarán los siguientes tamaños de cuadrícula:
6x6
;8x8
;10x10
;12x12
;14x14
;16x16
.
Reglas generales:
- Este es el código de golf , por lo que la respuesta más corta en bytes gana.
No permita que los lenguajes de code-golf lo desanimen a publicar respuestas con lenguajes que no sean codegolf. Trate de encontrar una respuesta lo más breve posible para 'cualquier' lenguaje de programación. - Se aplican reglas estándar para su respuesta, por lo que puede usar STDIN / STDOUT, funciones / método con los parámetros adecuados, programas completos. Tu llamada.
- Las lagunas predeterminadas están prohibidas.
- Si es posible, agregue un enlace con una prueba para su código.
- Además, agregue una explicación si es necesario.
Casos de prueba:
Los puntos solo se agregan para facilitar la lectura, siéntase libre de usar espacios o cualquier otra cosa que prefiera para espacios en su lugar. Tanto en formato de salida como en formato flexible.
Input:
1..0..
..00.1
.00..1
......
00.1..
.1..00
Output:
101010
010011
100101
011010
001101
110100
Input:
.1....
.10.0.
1.11..
.1....
...1.0
......
Output:
011010
010101
101100
010011
100110
101001
Input:
.......1..
.00..0..1.
.0..1..0.0
..1...1...
1.1......1
.......1..
.0..1...0.
....11...0
.0.0..1..0
0...0...1.
Output:
0110010101
1001100110
1001101010
0110011001
1010100101
0101010110
1001101001
0110110100
1010011010
0101001011
fuente
Respuestas:
Brachylog , 34 bytes
Pruébalo en línea!
Esto es bastante lento, por lo que el caso de prueba en TIO es 4x4. Actualmente estoy ejecutando el caso de prueba 6x6 en mi computadora para ver cuánto tiempo lleva.
Esto toma una lista de listas como entrada. Los valores desconocidos deben indicarse con variables, es decir, con cadenas en mayúsculas (y todas deben ser diferentes, ya que de lo contrario estaría indicando que algunas celdas deben tener el mismo valor)
Explicación
Restringimos los valores
{0,1}
, luego intentamos crear instancias de las variables hasta que se respeten las 3 reglas. Por eso es tan lento (porque los probará todos hasta encontrar uno; y porque en ese caso Brachylog no se implementa lo suficientemente bien como para que se puedan imponer restricciones antes de intentar una posible matriz).fuente
A
throughY
(conZ
como parámetro de salida). ¿Continúa conAA
,AB
, etc.?AA
es una variable yKEVINCRUIJSSEN
también es una variable.JavaScript (ES6),
274270 bytesToma la entrada como una matriz 2D, donde las celdas vacías están marcadas con
2
. Imprime todas las posibles soluciones a la consola.Cómo funciona
La primera parte del código usa la
M()
función para verificar la validez de la placa actual, tanto horizontal como verticalmente.Asigna una fila o columna completa a la cadena s . Esto es en realidad una matriz coaccionada a una cadena, por lo que parece
"1,2,2,0,2,2"
.Usa:
/(0|1),\1,\1/
para detectar 3 o más dígitos idénticos consecutivos.Si el tablero no es válido, nos detenemos de inmediato. Si el tablero es válido y está completo, lo imprimimos en la consola. De lo contrario, la segunda parte del código intenta reemplazar cada 2 con un cero o uno con llamadas recursivas:
Manifestación
Mostrar fragmento de código
fuente
Jalea ,
5351 bytesToma una lista de listas que representan la cuadrícula, que contienen
0
,1
y2
(los espacios). Devuelve una lista de listas de listas, cada lista de listas está en el mismo formato (aunque sin2
s) y representa una posible solución a la entrada.Pruébalo en línea! (esto no ejecutará ninguno de los casos de prueba de la pregunta debido a limitaciones de memoria; las 2cuadrículas de nSpaces se crean como una lista de listas de enteros, pero he puesto un caso relativamente pesado con una única solución). El pie de página separa y formatea las cuadrículas.
Método de fuerza bruta pura: implementa las reglas y las verifica para cada cuadrícula que podría formarse reemplazando cualquiera de las
2
s con1
s o0
s.fuente