Seberapa keras teka-teki biner Sudoku?

Sudoku adalah teka-teki terkenal yang dilengkapi NP. Binary Sudoku adalah varian yang hanya memungkinkan angka dan 1 . Aturannya adalah sebagai berikut.$0$$1$

1. Setiap baris dan setiap kolom harus mengandung jumlah nol dan yang sama.
2. Setiap baris dan setiap kolom adalah unik.
3. Tidak ada baris atau kolom yang berisi tiga atau tiga kali berturut-turut ( adalah tiga kali berturut-turut).$1 1 1$

Inputnya adalah persegi yang sebagian diisi dengan nol dan satu. Untuk memecahkan teka-teki, setiap sel dalam N × N persegi harus diisi dengan 0 atau 1 sambil menghormati aturan di atas. Saya tidak dapat menemukan hasil yang sulit untuk dipecahkan dalam memecahkan teka-teki Binary Sudoku.$N \times N$$N \times N$$0$$1$

Seberapa sulitkah memecahkan teka-teki Binary Sudoku? Apakah ini NP-lengkap?

Juga, saya tertarik pada kompleksitas masalah terkait.

Diberikan persegi penuh yang hanya menghormati aturan 1 dan 2 di atas,$N \times N$

seberapa sulitkah untuk menemukan permutasi baris dan kolom sedemikian rupa sehingga persegi menghasilkan aturan 3?

EDIT : Saya dengan cepat menyelesaikan bukti amatir yang saya mulai beberapa bulan yang lalu dan tidak pernah selesai.

Anda dapat mengunduhnya dalam format PDF di blog saya ... belum ada yang memeriksanya, jadi sanggahan, komentar, dan saran dipersilahkan.

Saya tidak tahu apakah ada bukti resmi, tetapi beberapa bulan yang lalu saya membuat gadget untuk meniru formula 3-CNF planar; misalnya gadget OR, SPLIT dan TURN adalah:

Saya membuat / memeriksa gadget menggunakan program pemecah kendala sederhana.

Keunikan setiap baris / kolom (aturan 2) dapat dicapai dengan menandai mereka dengan "angka biner" yang unik menggunakan blok 2x2 yang bertindak seperti "angka":

01 = 0   10 = 1
10       01

Dan jumlah 1s dan 0s yang sama (aturan 3) dapat dicapai mencerminkan seluruh puzzle, dan membalikkan 0s dengan 1s (menggunakan dinding khusus di tengah yang memungkinkan transisi tanpa melanggar aturan):

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