Jak trudna jest binarna łamigłówka Sudoku?

Sudoku jest dobrze znaną łamigłówką, która jest kompletna NP. Sudoku Binarne to wariant, który dopuszcza tylko cyfry i 1 . Zasady są następujące.$0$$1$

1. Każdy wiersz i każda kolumna musi zawierać równą liczbę zer i jedynek.
2. Każdy wiersz i każda kolumna jest unikalny.
3. Żaden wiersz ani kolumna nie zawiera kolejnych potrójnych zer lub jedynek ( to potrójne z jedynki).$1 1 1$

Dane wejściowe to kwadrat częściowo wypełniony zerami i zerami. Aby rozwiązać zagadkę, każda komórka w kwadracie N × N musi być wypełniona przez 0 lub 1, przy zachowaniu powyższych zasad. Nie udało mi się znaleźć żadnego trudnego wyniku do rozwiązania zagadki Sudoku Binarnego.$N \times N$$N \times N$$0$$1$

Jak ciężko jest rozwiązać zagadkę Sudoku Binarnego? Czy jest kompletny NP?

Interesuje mnie również złożoność powiązanego problemu.

Biorąc pod uwagę wypełniony kwadrat który jest zgodny tylko z powyższymi zasadami 1 i 2,$N \times N$

jak trudno jest znaleźć permutację wierszy i kolumn, aby wynikowy kwadrat był zgodny z regułą 3?

EDYCJA : Szybko ukończyłem amatorski dowód, że zacząłem kilka miesięcy temu i nigdy nie skończyłem.

Możesz pobrać go w formacie PDF na moim blogu ... nikt jeszcze tego nie sprawdził, więc odrzucenia, komentarze i sugestie są mile widziane.

Nie wiem, czy istnieje oficjalny dowód, ale kilka miesięcy temu zbudowałem gadżety, aby naśladować planarną formułę 3-CNF; na przykład gadżety OR, SPLIT i TURN to:

Zbudowałem / sprawdziłem gadżety za pomocą prostego programu do rozwiązywania ograniczeń.

Unikalność każdego wiersza / kolumny (reguła 2) można osiągnąć, oznaczając je unikalnym „numerem binarnym” za pomocą bloku 2x2, który działa jak „cyfra”:

01 = 0   10 = 1
10       01

Równą liczbę 1 i 0 (reguła 3) można uzyskać odzwierciedlając całą łamigłówkę i odwracając 0 z 1 (używając specjalnych ścian w środku, które umożliwiają przejście bez łamania zasad):

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