How hard is binary Sudoku puzzle?
EDIT: I quickly completed the amateur proof that I started a few months ago and never finished.

You can download it in PDF format on my blog ... nobody has checked it yet, so refutations, comments and suggestions are welcome.



I don't know if there is an official proof, but a few months ago I built the gadgets to mimic a planar 3-CNF formula; for example the OR, SPLIT and TURN gadgets are:



I built/checked the gadgets using a simple constraint solver program.

The uniqueness of each row/column (rule 2) can be achieved marking them with a unique "binary number" using a 2x2 block that acts like a "digit":

01 = 0   10 = 1
10       01


And the equal number of 1s and 0s (rule 3) can be achieved mirroring the whole puzzle, and inverting the 0s with 1s (using special walls in the middle that allow the transition without breaking the rules):

  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 ....


So deciding if a partially filled $N \times N$ Binary Puzzle board has a solution, is NP-hard.

Like other similar puzzles it's not immediate to say that it is in NP (see for example the discussion on succinct Nurikabe on cstheory). However if the initial board is given as a full string $\{0,1,\bot\}^{N \times N}$ (the representation is not succinct), and you drop the the unique solution constraint (which is another rule of the game), then the problem is in NP (and thus NP-complete).