Binary puzzle
Binary puzzle is an puzzle played on a $n × n$ grid; intially some of the cells contain a zero or a one (fixed cells); the aim of the game is to fill the remaining empty cells according to the following rules:
- Each cell should contain a zero or a one.
- 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.
Decision problem:
Input : A partially filled n×n grid with 0's and 1's.
Question : Can we fill the empty cells with a zero or a one in a way that follow the above mention rules ?
For $n \times n $ this problem known to be NP-complete.
Brute force Algorithm :
- If the given $n \times n$ is empty then it is an yes instance ( use the basis set of $ \mathcal{ R^{n\times n}}$).
- Case I: If only one row is filled and it is an valid row (follow the above mentions rules ) then it is an yes instance. Second row is going to be the complement of first row (make 0 to 1 and 1 to 0).
- Case II : if $k$ rows are filled and they are valid then I can fill the table upto 2k rows by using trick of complement.
Question : How to design a brute force algorithm for the problem stated above ?