Generating Nonograms

In my last post, I discussed a generator for Numbrix-like puzzles.  Since then I've extended Probably Puzzles with three more puzzle types.

Hidato is very similar to Numbrix.  The only difference is that the path can move diagonally.  To get that I had to drop the Hamiltonian path generator I scrounged up, and replace it with one that generalizes to accept the diagonal connections.  The new path generator is based on this stackoverflow answer.  Hidato is interesting, the path can cross itself and that seems to lead to some surprises while I'm solving it.

Another puzzle type I added is Nonogram (a.k.a. "Paint by Numbers", "Griddler", and lots of other names).  This one is the most popular of the ones I've done so far (but will certainly drop to second place if I add Sudoku).  In this puzzle you color in the cells of a grid to draw a "picture".  There are numbers along the left and top of the grid which constrain which cells you can fill in.  They tell you how many sequences there are on each row and column, and the lengths of those sequences, but not exactly where those sequences go.

A randomly-generated 9x9 nonogram.

On the one hand, generating these is easier than Numbrix/Hidato.  We don't need to pick a subset of the hints that leaves the puzzle uniquely solvable, we just need to generate a picture.  The hints are determined directly from that.  On the other hand, how do we generate "a picture"?  I considered pulling from a library of images, or scattering various geometric shapes around, but I though it would be better for this particular site if the puzzles were completely random.  In the end, I decided to use simplex noise, which generates basically a bunch of random blobs.  At low difficulty, you get very big blobs, and a high likelihood that some rows or columns are completely determined by the hints.  At the highest difficulty, each cell is independently random, and it ensures that no rows or columns are completely determined.

Nonogram in progress.

For the play interface, I took some advice from my wife, who is an avid nonogram puzzler.  You left click to fill the cells, and right-click to place little dots in the cells which you can use as a reminder to yourself that you've decided that particular cell must be empty.

The third puzzle type I added was Shikaku, which I'll describe in the next post.

Probably Puzzles