Solving Binary puzzles with actual computer science
About a week ago I got quite an enthusiastic message from my mother in law. She found a nice puzzle made up of 1’s and 0’s and thought I could explain it to her. But although the Sudoku-like puzzles are called binary puzzles they don’t have much to do with computer science. And instead of solving the puzzle by hand I would do what any sensible engineer would do: spend a lot more time automatizing it! The puzzles intrigued me and before I knew it I was hooked. I kept hacking at an algorithm for solving these puzzles and decided to keep track of the process.
Solving puzzles the hard way.
To solve a problem we need to know the rules and boundaries, these will serve as both restrictions and hints in finding the solution. the rules of a binary puzzle are really simple.
1. Each cell needs to contain either a 0 or a 1.
2. More than 2 equal numbers can’t be immediately next to each other.
3. Each row and each column will contain an equal amount of both 1’s and 0's.
4. No two rows or columns will be the same.
Before trying to make a polished efficient solution we need a simple, naive but working solution. The obvious first step is iterating over each cell in the puzzle an checking if we can determine its value based on its neighbors.
This logic must be followed for every direction, not only left to right but up and down as well. To make things easy we can make groups of 3 cells of which our target cell is a part of. If one of these groups contains the same digit twice we’ll know for sure that our cell will not be that value.
Implementing this logic in python makes quick work of small, easy binary puzzles in no time and preforms not too shabby with only three iterations over this particular puzzle.
This solution works on the easier puzzles but the medium puzzles on binarypuzzle.com won’t go down this easy. Look at this before and after:
Just looking cell by cell isn’t going to cut it. To decide our next step we need to go back to the rules of the puzzle and find that the third rule might help us out. each rows must consist of the same amount of 1’s and 0’s. The second row from the bottom is a great example for where this rule comes in handy. The row currently consists of three 0's and and only one 1 meaning we have 2 one’s left. We can now fill out the row:
Adding this logic to python, repeating it for the columns, repeating all three steps while there are still unknown cells and we’ve cracked the code! The algorithm now easily solves up to 10x10 medium & hard puzzles!
Although the the algorithm solves most puzzels we throw at it there is still room for improvement, we haven’t accounted for the rule of individuality between every row and column and the code isn’t optimized as well.
But i’m content with the results for now and might go over the code and further optimizations in a future post.
Thanks for reading!
