Binary Puzzle (also known as Binary Sudoku) is an addictive puzzle played on a $n \times n$ grid; intially some of the cells contain a zero or a one; the aim of the game is to fill the empty cells according to the following rules:
- Each cell should contain a zero or a one and no more than two similar numbers next to or below each other are allowed
- Each row and each column should contain an equal number of zeros and ones
- Each row is unique and each column is unique
We prove that the decision version of Binary Puzzle is NP-complete.
The NP-completeness result is a nice reminder that the cleanest-looking constraint puzzles can hide serious combinatorial structure. The row and column uniqueness rules are especially doing a lot of work here. For anyone who wants to see those constraints play out interactively, https://www.binarypuzzle.space/ offers a straightforward daily Binary Puzzle implementation.