Sudoku is a well-known puzzle that is NP-complete. Binary Sudoku is a variant that only allows the numbers 0 and 1

. The rules are as follows.

- Each row and each column must contain an equal number of zeros and ones.
- Each row and each column is unique.
- No row or column contains consecutive triples of zeros or ones (111
- is a consecutive triple of ones).

The input is a *N*×*N* square partially filled with zeros and ones. To solve the puzzle, each cell in the *N*×*N* square must be filled by either 0 or 1

while respecting the above rules. I was not able to find any intractability result for solving the Binary Sudoku puzzle.

How hard is solving the Binary Sudoku puzzle? Is it NP-complete?

Also, I’m interested in the complexity of a related problem.

Given a fully filled *N*×*N*

square that respects only rules 1 and 2 above,

how hard is it to find a permutation of rows and columns such that the resulting square respects rule 3?

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:

enter image description here

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 2×2 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 2×2 blocks)

| | 0,1 inverted | 0001

——————–+ +—————–+ 0010

wall wall | ….

——————–+ +—————–+ ….

3CNF sim. with | wall | 3CNF simulation |

0,1 inverted | | |

——————–+——–+—————–+

0101 …. (using 2×2 blocks)

0011 ….

0000 ….

So deciding if a partially filled N×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,⊥}N×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).