I first came across binary puzzles in early 2013 after finding a book of them in a Belgian supermarket, not long after I first came across Haskell. And I believe that I've now published the first solver for binary puzzles written in Haskell. And it only took 3 years ;-)

The puzzles are a little like sudoku. You get a grid which contains a number of ones and zeros and you fill it in with more ones and zeros, until each row and column of the grid

• Has no blank spaces
• Is unique
• Contains an equal number of ones and zeros
• Does not contain a run of more than two ones or zeros

Easy right?

I thought so and started to write some Haskell code that would solve the puzzles. And then I got stuck. I could solve the most trivial puzzles quickly, but the iterative approach I had implemented was far too inefficient to solve the more complex ones. All I had been doing was generating the rows that could fit and then filtering the Cartesian product of them for valid grids. That worked on 8x8 grids, but beyond that things became too slow.

Fast forward to 2016. A couple of days before New Year to be precise. I found the book of puzzles and dug out my 2013-era code. I very quickly realized that I could reduce the problem space significantly simply by applying the simple deterministic rules that you use when solving the puzzles by hand. Those rules are

• The "sandwich rule" — if you see 1_1 or 0_0, you can replace it with 101 or 010
• The "double digit rule" — if you see _11_ or _00_, you can replace the blanks with the other digit, so _11_ becomes 0110.
• The "N identical blanks left rule" — if there are the number of 0s is equal to half of the total row length then the remaining blanks can be replaced by 1s and vice versa
• The "N different blanks left rule" — if you can infer that there is a 1 and a 0 left then if a row with 1 then 0 creates an invalid row the row must be completed with 0 then 1 and vice versa

This got me to being able to solve my test puzzle from the book with my original Cartesian product approach.

However, I now had a test case from binarypuzzle.com which was not feasible to solve. I would have to check around 566558720000 different grids for validity. Generating the grids was fast but checking was slow.

Fortunately, I had come across Richard Bird’s sudoku solver in Pearls of Functional Algorithm Design and was able to use a similar trimming approach to reducing the problem space.

Given a grid, you first apply the simple rules above. Then you generate a "matrix", which is a list in which each element is the rows that could possibly be answers for that grid. If there is only one entry per element, then you have a candidate correct answer. Otherwise take the shortest element with more than one entry and create matrices for each entry, filter for matrices that are filled with single entry elements and generate valid grids and return the first of those. Once you have that the problem is solved.

I went from being unable to solve the puzzle to being able to solve in a few seconds.

I believe that further improvements are possible — parallelizing to take advantage of multicore architectures or implementing more complex rules for example — and will perhaps work on them "at some point".

For now though, my Binary Puzzle solver code is on GitHub and I welcome feedback, criticism or contributions.