Brute force algorithm for “Binary Puzzle”

Question

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 :

1. If the given $n \times n$ is empty then it is an yes instance ( use the basis set of $ \mathcal{ R^{n\times n}}$).
2. 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).
3. 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 ?

Answer 1

For $k$ fixed cells, you try all $2^{n^2-k}$ possibilities of filling the remaining $n^2-k$ cells and check for each fully filled board whether it fulfills all stated constraints.