PixlBit

Alright guys, as promised, here's the first of the series of Dev Blogs I've been intending to write. To set the stage, the timeframe for this blog starts around Thanksgiving 2014 and lasts through the rest of the year. 

In an effort to assist Chessa in her quest to create all of the puzzles for PixlCross, I got the brilliant idea that I needed to create an automated way to solve the puzzles. She had been cranking out puzzles, but had no good way to verify if they were any good without sitting down and playing them.

For those who’ve played a Picross game in the past, you’ve undoubtedly come across puzzles with ambiguities. Basically, if you've ever played a puzzle where you had to guess to solve it, you played one with ambiguities. We hate ambiguities. They kind of ruin the spirit of the game. You should be able to follow the hints along the rows and columns of the grid and be able to create the picture without making any guesses.

What Chessa was finding was that many of the puzzles she made had ambiguities. To resolve said ambiguities required a very lengthy process wherein she would play test the puzzle until she hit a wall and then go back, make changes, and retest again, over and over until all issues were resolved. As I’m sure you can imagine, this process was incredibly time consuming for her and with 150+ puzzles on the docket to be made, it was going to be an unreasonably large task.

This ultimately birthed the puzzle solver.

Just like building any piece of software, I sat down and did an analysis on the skills that were leveraged to solve a puzzle. My first prototype of the solver was extremely rudimentary. It could detect blank rows, or rows that were totally filled in. It could figure out rows where the hints all added up to the length of the board. It could even guess partial fills of rows or columns. However, figuring out the solution to simple problems remained elusive.

For example, a row where there are two squares already filled in and there’s only a single hint present (meaning you can connect the dots and likely solve the row) was an extremely hard problem to solve. And that was just one of the issues with my initial solver implementation. It left a lot to be desired and nailing down all the techniques that could be used was slow and inefficient.

As it turns out, it’s a problem that computer scientists have been investigating for some time now. Furthermore, there are a variety of techniques people have developed to make the solvers either fast and efficient, quitting whenever an ambiguity is discovered, or slow and complex, considering any and all solutions possible for the given input. Thankfully, I was looking for the faster, more efficient algorithm as discovering ambiguities was the main thrust of the effort.

I dug around and spotted a very helpful page written by a Dr. Stephen Simpson at Lancaster University in the UK. He had developed a solving technique that was exactly what I needed for PixlCross. I went through his notes and began writing my own Javascript implementation.

Of course, even with the keys to the castle… this was a lot harder than anticipated. The general concept of the solver is that you try to lay out all of the hints as far scrunched to the left as possible and as far to the right as possible, then you see which ones overlap. If the spaces between the same hints overlap, you drop an x, and if the exact hints overlap you drop a block. However, you need to shift the placement of the hints when dropping from the far left or right to account for the existing state of the row. This means lots of looping to push blocks one space at a time till they match with the existing state and dealing with the ramifications of pushing those blocks by pushing subsequent blocks.

Needless to say, perfecting my implementation of this algorithm took 3 full rewrites and then an absolute ton of unit testing. I ran the solver against our entire pool of existing puzzles until each and every one passed the solver test. The huge amount of puzzles Chessa had already built and verified really helped give me the testing pool I needed to make the solver a success.

The icing on the cake is that the solver got integrated right into the Puzzle Editor of PixlCross, as it was the easiest way to leverage it during development. Of course, this worked out for the game as well, because when users decide to make puzzles, they too can leverage the solver to make sure they are creating the best puzzles for other players to download off "the cloud."

The entire solver debacle ultimately set PixlCross back a month or two. Not that I was spending every waking moment working on the Solver, but during my limited time in the holiday season, it was my sole focus. It was quite refreshing to finally finish the solver and get back to the more visual stuff and begin tightening up the actual game.

- Nick

Up Next Time: I’ve Made a Huge Mistake