20171201
Solving a binary puzzle
Publication
Publication
Mathematics in Computer Science , Volume 11  Issue 34 p. 515 526
A Binary puzzle is a Sudokulike puzzle with values in each cell taken from the set (Formula presented.). Let (Formula presented.) be an even integer, a solved binary puzzle is an (Formula presented.) binary array that satisfies the following conditions: (1) no three consecutive ones and no three consecutive zeros in each row and each column; (2) the number of ones and zeros must be equal in each row and in each column; (3) there can be no repeated row and no repeated column. This paper proposes three approaches to solve the puzzle. The first method is based on a complete backtrackbased search algorithm. The idea is to propagate and fill an unsolved binary puzzle according to the three constraints, followed by a random guess if the puzzle remains unsolved. The second method of solving a binary puzzle is by representing it as an instance of a Boolean satisfiability problem which allows the solution for a binary puzzle to be obtained using SAT solvers. The third approach is based on expressing a binary puzzle as a system of polynomial equations over the binary field (Formula presented.). The set of solutions for the equation system implies the solutions for the binary puzzle and it is obtained by computing a Gröbner basis of the ideal generated by the polynomials. We experimentally compare the three approaches with binary puzzles of various sizes and different numbers of empty cells using a computer algebra system.
Additional Metadata  

, , ,  
doi.org/10.1007/s1178601703224  
Mathematics in Computer Science  
Utomo, P.H, & Makarim, R.H. (2017). Solving a binary puzzle. Mathematics in Computer Science, 11(34), 515–526. doi:10.1007/s1178601703224
