Quão difícil é o quebra-cabeça binário de Sudoku?

Sudoku é um quebra-cabeça conhecido que é NP-completo. O Sudoku binário é uma variante que permite apenas os números e 1 . As regras são as seguintes.$0$$1$

1. Cada linha e cada coluna deve conter um número igual de zeros e uns.
2. Cada linha e cada coluna é única.
3. Nenhuma linha ou coluna contém triplos consecutivos de zeros ou uns ( é um triplo consecutivo de um).$1 1 1$

A entrada é um quadrado parcialmente preenchido com zeros e uns. Para resolver o enigma, cada célula do N × N praça deve ser preenchido por um ou outro 0 ou 1 , respeitando as regras acima. Não consegui encontrar nenhum resultado intratável para resolver o quebra-cabeça do Binary Sudoku.$N \times N$$N \times N$$0$$1$

Quão difícil é resolver o quebra-cabeça do Sudoku Binário? É NP-completo?

Além disso, estou interessado na complexidade de um problema relacionado.

Dada uma totalmente preenchido quadrado que governa os aspectos apenas 1 e 2 acima,$N \times N$

quão difícil é encontrar uma permutação de linhas e colunas de modo que o quadrado resultante respeite a regra 3?

Edição : Eu rapidamente completei a prova amadora de que comecei há alguns meses e nunca terminei.

Você pode baixá-lo em formato PDF no meu blog ... ninguém o verificou ainda, portanto, refutações, comentários e sugestões são bem-vindos.

Não sei se há uma prova oficial, mas alguns meses atrás eu construí os aparelhos para imitar uma fórmula planar de 3-CNF; por exemplo, os gadgets OR, SPLIT e TURN são:

Eu construí / verifiquei os gadgets usando um programa simples de resolução de restrições.

A exclusividade de cada linha / coluna (regra 2) pode ser alcançada marcando-os com um "número binário" exclusivo, usando um bloco 2x2 que age como um "dígito":

01 = 0   10 = 1
10       01

E o número igual de 1s e 0s (regra 3) pode ser alcançado espelhando todo o quebra-cabeça e invertendo os 0s com 1s (usando paredes especiais no meio que permitem a transição sem violar as regras):

  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}$