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 ($1 1 1$ is a consecutive triple of ones).
The input is a $N \times N$ square partially filled with zeros and ones. To solve the puzzle, each cell in the $N \times 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 \times 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?