Solving a binary puzzle

P.H. Utomo, R.H. Makarim

Research output: Contribution to journalArticleAcademicpeer-review

1 Downloads (Pure)

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 languageEnglish
Pages (from-to)515–526
Number of pages12
JournalMathematics in Computer Science
Volume11
Issue number3-4
DOIs
Publication statusPublished - 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.

  • Cite this