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.