¿Qué tan difícil es el rompecabezas binario de Sudoku?

Sudoku es un rompecabezas bien conocido que es NP completo. Sudoku binario es una variante que solo permite los números y . Las reglas son las siguientes. $0$ $1$

Cada fila y cada columna deben contener un número igual de ceros y unos.
Cada fila y cada columna es única.
Ninguna fila o columna contiene triples consecutivos de ceros o unos ( es un triple consecutivo de unos). $1 1 1$

La entrada es un cuadrado parcialmente lleno de ceros y unos. Para resolver el rompecabezas, cada celda en el cuadrado debe llenarse con o respetando las reglas anteriores. No pude encontrar ningún resultado de intratabilidad para resolver el rompecabezas Binary Sudoku. $N \times N$ $N \times N$ $0$ $1$

¿Qué tan difícil es resolver el rompecabezas binario de Sudoku? ¿Es NP-completo?

Además, estoy interesado en la complejidad de un problema relacionado.

Dado un cuadrado completamente lleno que respeta solo las reglas 1 y 2 anteriores, $N \times N$

¿Qué tan difícil es encontrar una permutación de filas y columnas de modo que el cuadrado resultante respete la regla 3?

cc.complexity-theory np-hardness puzzles Mohammad Al-Turkistany
fuente

No es el mismo problema, así que lo dejaré como un comentario en lugar de una respuesta, pero hay un resultado de dureza NP para subproblemas de un solo dígito del tipo estándar de rompecabezas de Sudoku en mi artículo arxiv.org/abs/1202.5074

David Eppstein

Como autor de una aplicación de rompecabezas binario (este problema), puedo ofrecerle una observación (no una prueba): todas las instancias de este rompecabezas vistas en la práctica se pueden resolver en tiempo polinómico, pero hay instancias que parecen no tener solución. de esa manera, es decir, exactamente aquellos casos en los que alcanza un estado en el que ninguna de las tres reglas obliga directamente a una celda a tomar un valor específico (es decir, parece que tiene que "intentar algo" y tal vez retroceder a ese punto).

Harold

Hola, he estado tratando de hacer un programa para resolver acertijos binarios, excepto que me resulta difícil completar los acertijos binarios muy difíciles y necesitaría una pista para resolverlo. Mi programa puede hacer fácilmente todos los problemas binarios, excepto los muy difíciles

Respuestas:

EDITAR : Completé rápidamente la prueba de aficionado que comencé hace unos meses y nunca terminé.

Puede descargarlo en formato PDF en mi blog ... nadie lo ha revisado todavía, por lo que las refutaciones, comentarios y sugerencias son bienvenidas.

No sé si hay una prueba oficial, pero hace unos meses construí los dispositivos para imitar una fórmula plana de 3-CNF; por ejemplo, los gadgets OR, SPLIT y TURN son:

ingrese la descripción de la imagen aquí

Construí / verifiqué los gadgets usando un programa simple de resolución de restricciones.

La unicidad de cada fila / columna (regla 2) se puede lograr marcándolas con un "número binario" único utilizando un bloque de 2x2 que actúa como un "dígito":

01 = 0   10 = 1
10       01

Y se puede lograr el mismo número de 1s y 0s (regla 3) reflejando todo el rompecabezas e invirtiendo los 0s con 1s (usando paredes especiales en el medio que permiten la transición sin romper las reglas):

  3CNF simulation    |  wall  | 3CNF sim. with  | 0000 (using 2x2 blocks)
                     |        | 0,1 inverted    | 0001
 --------------------+        +-----------------+ 0010
    wall                        wall            | ....
 --------------------+        +-----------------+ ....
  3CNF sim. with     |  wall  | 3CNF simulation |
  0,1 inverted       |        |                 |
 --------------------+--------+-----------------+
 0101 .... (using 2x2 blocks)
 0011 ....
 0000 ....

$N \times N$

$\{0,1,\bot\}^{N \times N}$

Marzio De Biasi
fuente

Supongo que te refieres al circuito plano SAT?

Mohammad Al-Turkistany

Me refiero a Planar tipo 1 3CNF (el gráfico bipartito entre las cláusulas 3CNF y las variables es plano). Un dispositivo se usa para simular una asignación T / F, otro se usa para forzar una T en cada cláusula, se usan 2 dispositivos OR para simular los dos OR de cada cláusula y el SPLIT para dividir y "transportar" la señal de las asignaciones a las cláusulas Ahora estoy tratando de completar el documento, tan pronto como lo termine, publicaré el enlace en la respuesta.

Marzio De Biasi

Por lo tanto, está reduciendo el problema SAT 1-en-3 monotono cúbico bipartito cúbico plano NP-completo. ¿Derecha?

Mohammad Al-Turkistany

No, "tipo 1" significa la fórmula plana particular 3CNF utilizada (existe una ligera diferencia entre el tipo 1 y el tipo 2). Utilicé una reducción similar para demostrar la completitud NP del juego de rompecabezas Carpa ; puedes echarle un vistazo a ese documento, sin embargo, creo que en 1-2 días publicaré una prueba completa del problema del sudoku binario, también conocido como rompecabezas binario (acabo de completar las instantáneas de los gadgets) (y espero que ' Lo echaré un vistazo para ver si realmente funciona :-)

Marzio De Biasi

Buena suerte, no puedo esperar.

Mohammad Al-Turkistany