# Solving a binary puzzle

P.H. Utomo, R.H. Makarim

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)

## Abstract

A Binary puzzle is a Sudoku-like puzzle with values in each cell taken from the set {0,1}
{0,1}. Let n≥4 be an even integer, a solved binary puzzle is an n×n 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 backtrack-based 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 F2. 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.
Original language English 515–526 12 Mathematics in Computer Science 11 3-4 https://doi.org/10.1007/s11786-017-0322-4 Published - Dec 2017

## Keywords

• Gröbner basis
• NP-complete
• Puzzle
• SAT problem

## Fingerprint

Dive into the research topics of 'Solving a binary puzzle'. Together they form a unique fingerprint.