Binary Puzzle is NP-complete

Net puzzleBinary 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.

click here to download the paper

Leave a Reply

Your email address will not be published. Required fields are marked *