Quelle est la difficulté du puzzle binaire Sudoku?

Sudoku est un puzzle bien connu qui est NP-complet. Le Sudoku binaire est une variante qui n'autorise que les chiffres et 1 . Les règles sont les suivantes.$0$$1$

1. Chaque ligne et chaque colonne doit contenir un nombre égal de zéros et de uns.
2. Chaque ligne et chaque colonne est unique.
3. Aucune ligne ou colonne ne contient de triplets consécutifs de zéros ou de uns ( est un triple consécutif de uns).$1 1 1$

L'entrée est un carré partiellement rempli de zéros et de uns. Pour résoudre le casse-tête, chaque cellule du carré N × N doit être remplie par 0 ou 1 tout en respectant les règles ci-dessus. Je n'ai pas pu trouver de résultat d'intractabilité pour résoudre le puzzle de Sudoku binaire.$N \times N$$N \times N$$0$$1$

Quelle est la difficulté à résoudre le puzzle Sudoku binaire? Est-il NP-complet?

Je m'intéresse également à la complexité d'un problème connexe.

Étant donné un carré entièrement rempli qui ne respecte que les règles 1 et 2 ci-dessus,$N \times N$

est-il difficile de trouver une permutation de lignes et de colonnes telle que le carré résultant respecte la règle 3?

EDIT : J'ai rapidement complété la preuve amateur que j'ai commencé il y a quelques mois et que je n'ai jamais terminé.

Vous pouvez le télécharger au format PDF sur mon blog ... personne ne l'a encore vérifié, donc réfutations, commentaires et suggestions sont les bienvenus.

Je ne sais pas s'il existe une preuve officielle, mais il y a quelques mois, j'ai construit les gadgets pour imiter une formule planaire 3-CNF; par exemple, les gadgets OR, SPLIT et TURN sont:

J'ai construit / vérifié les gadgets à l'aide d'un simple programme de résolution de contraintes.

L'unicité de chaque ligne / colonne (règle 2) peut être obtenue en les marquant avec un "nombre binaire" unique en utilisant un bloc 2x2 qui agit comme un "chiffre":

01 = 0   10 = 1
10       01

Et le nombre égal de 1 et de 0 (règle 3) peut être obtenu en reflétant l'ensemble du puzzle et en inversant les 0 avec des 1 (en utilisant des murs spéciaux au milieu qui permettent la transition sans enfreindre les règles):

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