takuzu

Takuzu , también conocido como Binairo , es un rompecabezas de lógica que consiste en colocar dos símbolos, generalmente 1 y 0, en una cuadrícula rectangular. El objetivo es llenar la cuadrícula con 1 y 0, de manera que haya la misma cantidad de ambos números en cada fila y columna, y que no aparezcan más de dos de cada número juntos en una misma fila o columna. Además, no puede haber filas ni columnas idénticas. Al igual que el Sudoku , cada rompecabezas comienza con varias casillas de la cuadrícula ya llenas.

El juego se conoce como Binairo, Takuzu, Binero, ^{[ 1 ] [ 2 ]} Tohu-Wa-Vohu (Sin forma y vacío), Eins und Zwei (Uno y dos), Binary Puzzles, Binoxxo, Zernero, ^{[ 3 ]} Tic-Tac-Logic, ^{[ 4 ]} Binox, ^{[ 5 ]} y Sudoku Binario. ^{[ 6 ]} Los nombres "Binairo" y "Takuzu" son marcas comerciales en la Unión Europea. ^{[ 7 ] [ 8 ]} El nombre "Binero" es una marca comercial en Francia por Editions Megastar. ^{[ 9 ]} LinkedIn también publica una versión de este juego, llamada Tango. ^{[ 10 ]}

Algunos nombres implican el uso de símbolos específicos. Por ejemplo, los rompecabezas binarios usan 1 y 0 (es decir, números binarios ) , el juego de tres en raya usa X y O , Eins und Zwei usa 1 y 2, y Tohu-Wa-Vohu usa los símbolos T y V. Sin embargo, muchos nombres se usan para cualquier variación de símbolos. Los círculos (o cuadrados) blancos y negros son otro par de símbolos de uso común. Cualquier variación de dos números, letras, colores o imágenes puede funcionar como los dos símbolos, aunque generalmente es común que los símbolos sean 1, X o figuras geométricas.

El tamaño de las cuadrículas rectangulares puede variar considerablemente. Dado que el objetivo es tener el mismo número de símbolos en cada fila y columna, el número de filas y columnas suele ser par. Aunque no es obligatorio, las cuadrículas suelen ser cuadradas. Los tamaños comunes van desde 4x4 hasta 20x20. ^{[ 11 ] [ 12 ]} También se fabrican rompecabezas más grandes, incluyendo algunos que utilizan una cuadrícula de 30x40. ^{[ 13 ]}

Algunas variantes permiten filas y columnas idénticas. ^{[ 3 ]} Otra variante, Odd Binairo, tiene un número impar de filas y columnas, cada una con un 1 más que 0 (es decir, en una cuadrícula de 11x11, cada fila y columna tiene 5 ceros y 6 unos). ^{[ 14 ]}

Existen dos orígenes contrapuestos para el rompecabezas, ambos creados aproximadamente al mismo tiempo. Tohu wa Vohu fue inventado por el italiano Adolfo Zanellati. ^{[ 3 ]} Binairo fue creado por los belgas Peter De Schepper y Frank Coussement en 2009. ^{[ 1 ] [ 14 ]}

Tic-Tac-Logic afirma tener su origen en la creación de una versión para un solo jugador del tres en raya. Al igual que el tres en raya, utiliza X y O. El objetivo del juego para dos jugadores es formar tres en raya, mientras que en Tic-Tac-Logic, el objetivo es evitar que se formen tres en raya. ^{[ 4 ]}

• 
  Una cuadrícula de Takuzu de 4×4 sin resolver
• 
  La misma cuadrícula, resuelta

• Cada fila y cada columna debe contener la misma cantidad de 0 y 1. Por lo tanto, si se alcanza la cantidad requerida de 0 o 1 en una fila o columna, las celdas restantes deben contener el otro dígito (1xx101 → 100101).
• No puede haber más de dos dígitos iguales en celdas adyacentes. Por lo tanto, si dos celdas adyacentes contienen el mismo dígito, las celdas contiguas deben contener el otro dígito (xxx00x → xx1001). Del mismo modo, si dos celdas contienen el mismo dígito con una celda vacía entre ellas, esta celda vacía debe contener el otro dígito, ya que de lo contrario aparecerían tres dígitos iguales (x1x1xx → x101xx).
• Elimine lo imposible. Por ejemplo, si la sexta celda en 110xxx se convierte en un 1, al equilibrar la cantidad de 0s y 1s se forma un trío (110xxx → 110xx1 → 11 000 1), por lo que no puede ser un 1. Por lo tanto, la sexta celda debe contener un 0 (110xxx → 110xx0).
• Cada fila y columna es única (100101 y 1001xx → 100101 y 100110).

En junio de 2016 se publicó una prueba de conocimiento cero para el rompecabezas. ^{[ 15 ] [ 16 ]}

El rompecabezas fue adaptado para modelar agentes cuánticos. ^{[ 17 ]}

Los matemáticos de la universidad holandesa (PH Utomo y RH Makarim) propusieron tres enfoques diferentes para resolver rompecabezas binarios: usando búsqueda basada en retroceso, solucionadores SAT y algoritmos de bases de Gröbner. ^{[ 18 ]} Los dos últimos enfoques reducen el problema de resolver un rompecabezas binario a un problema de satisfacibilidad booleana y a la resolución de sistemas de ecuaciones polinómicas sobre el campo binario.

• Solucionador Takuzu en Python