1
$\begingroup$

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 ?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.