A lot of my friends ask me what I do with my spare time. There are a number of ways I could answer that question, but the answer is basically this site. Its full of the thoughts that go through my mind as I’m at work, when I’m on a run, or driving my car or with my kids. Sometimes It’ll be a new idea, or a way of teaching/explaining/visualizing something, or something for my kids or a new way to relax.
A few years back, I added a section to this site called Puzzles. These were basically puzzles that I had seen in passing at some site or in a book that I thought were fun and challenging and wanted to do more of. The site started with the puzzles being offered as a part of the LEARNINGlover.com examples section, and many still are there. But as the site grew and I really enjoyed making the puzzles, I decided to offer a separate page dedicated to the puzzles.
Then we get to the fun part of it. How do we generate puzzles? There are basically two types of puzzles I’m thinking about here. One is where there is some final answer and none of the information that is needed for the answer is given. Instead, hints about the final answer are given. Some puzzles that offer this type of structure are Nonograms, Shade the Cells or the Magical Squares Puzzles. These are very fun and a bit easier to create.
The other type of puzzles I’ve been playing with are the ones where the final answer is generated according to some set of rules, then a subset of this final answer is revealed as a “hint” to direct the user towards the unique final answer. Some examples of these puzzles are Sudoku, Slitherlink, Binary Puzzles, and Corral. These puzzles have been more difficult for me to generate because the question that has puzzled (no I did not mean to have a play on words) me is how do we decide which puzzle cells to remove and still keep a unique solution?
I tried a number of techniques that all left me dissatisfied. Eventually I had left the problem alone and had a technique of removing a large number of cells (allowing for multiple solutions to exist) just added a “reveal” button to give more hints towards the solution if a user was stuck. This left me very unsatisfied as a) I was sure there was a way of doing this since I see it done on so many other sites so often and b) I would often start down a direction and press the reveal button, only to be told that I was headed towards the wrong one of the multiple solutions.
That is what brings me here today. I also spend a lot of time looking at programming challenges and practice exercises to help better understand data structures and algorithms. One of those problems was the maximum submatrix sum problem. The problem asks, given an m by n matrix of integer values (positive or negative) can we find the submatrix that has the maximum sum. I solved this problem years ago and had it sitting in my library as something I was going to develop as a game to play with my kids.
Then the thought hit me of using this to help decide on which cells to remove. The idea is that in most of these puzzles the neighbors of a cell have a direct influence on the contents of a cell. So in a Sudoku puzzle, we know that a cell containing a 9 inside a 3 by 3 subgrid cannot have any more 9’s. The maximum submatrix problem wouldn’t divide the original grid into the 3 by 3 subrids as Sudoku does, but it as still performed reasonably well.
Here is an overview of what we’re doing with the algorithm. Initially I set up a matrix with all positive values. For some puzzles, this is the contents of the cells, for other puzzles like Binary Puzzles I set the matrix to all 1s. Then the generate algorithm will search for the maximum sum of this matrix, and from that submatrix will select a random location. This random location will have its value removed from the puzzle and the value in this matrix will now be a large negative number. Then we simply check to see if there is a unique solution and continue.
That’s the gist of it. I have added a small quirk where I allow for a few misfires – that is, some attempts to remove a cell that leads to multiple solutions. On a misfire we simply put the value back and try again. The problem with misfires is that they are what generally slow down this process as allowing for too many misfires just leads to the generation algorithm repeatedly solving this puzzle.
So what type of results have I seen? I was getting normally about 75% of cells visible on most of these type two puzzles. That does not make a difficult puzzle. There would be the unique time where I would have about 60% of cells visible and those puzzles would be more challenging but they would normally take time to generate. Time is of the essence though so I didn’t like sitting around and waiting. Well, now I’m getting somewhere between 40-50% visibility on a fraction of the time. Sometimes its only a second or two (it was taking minutes under the old algorithm). This is not always true as I do still get sometimes a 75% visibility, but that is by far the exception rather than the norm.