# Binary Puzzle is NP-complete

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.