Forgot password?  |  Register  |    
User Name:     Password:    
Blog - General Entry   

Dev Blog #3: To Solve a Nonogram


On 05/19/2015 at 07:44 PM by PixlBit Studios

See More From This User »

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


 

Comments

Cary Woodham

05/19/2015 at 07:59 PM

I sitll want to review this for GamerDad.com when it comes out on Wii U.

When I come across an ambig...abig...ambigi...that big word you said, I just mash on the keyboard and hope for the best!

Nick DiMola Director

05/19/2015 at 09:54 PM

You got it, Cary! We're getting pretty close here. Just need to finish up testing the whole cloud upload/download stuff and it's ready to go through Nintendo's lotcheck process. There's some other housekeeping things too and the whole PR end of the thing, but we're really close to being all done (thank god).

Also, ambiguities are the worst! They've ruined many a good puzzle. We're hoping that longtime fans of this style of game appreciate that there are no puzzles that force you to guess.

Matt Snee Staff Writer

05/19/2015 at 08:31 PM

your game looks so good man, like an honest to God Nintendo game!  

It's cool how you discovered the answer to your problem through some distant professor's work.  That's what the internet was built for, dammit!

Nick DiMola Director

05/19/2015 at 09:59 PM

Thanks man! It's crazy how many iterations we went through to get it looking good (I've got a blog planned to talk all about it!). It's easily been one of the toughest parts of this whole process. You don't think that you're going to obsess over it as much as you actually do.

It is so crazy that some dude in the UK had a super old web page with the exact solution I was looking for. I can't even begin to tell you how nice it was to find that. Of course, it was still a ton of work, but having the conceptual algorithm really helped.

I wanted to contribute my Javascript implementation to him so he could add it to his collection, but oddly his site has disappeared...

Jamie Alston Staff Writer

05/20/2015 at 12:16 PM

Okay...being totallty honest here-- my eyes glazed over after reading about the Javascript implementation.  This stuff just doesn't compute for me.  But that's okay...that's why smart people like you make all the big bucks.

In any case, I can definitely tell that you and Chessa have been working pretty dang hard on Pixlcross.  Can't wait for it to come out.  I'll be there front and center.

Nick DiMola Director

05/22/2015 at 07:19 AM

Thanks Jamie! Yeah, the Javascript stuff is a bit on the complicated side. But quite frankly, without the help of Dr. Simpson's page, there's no damn way I'd have figured it out by myself either.

KnightDriver

05/23/2015 at 03:42 PM

Sounds like another reminder to always keep projects as simple as possible because you never know how complex they will become. 

Log in to your PixlBit account in the bar above or join the site to leave a comment.

Following

Game Collection

Support

Friend Codes