Saturday, August 27, 2016

Generating Shikaku-like puzzles

A very small
in progress.
In my last post, I talked about adding Nonograms to Probably Puzzles.  Now let's talk Shikaku.

In Shikaku your task is to divide a grid into rectangular regions, such that every cell is assigned to a region, every region has exactly one number in it, and that number is the area of the region.

This one turned out to be harder to generate than Hidato, though maybe I haven't found the right algorithm.  The first step was to generate a random division of the grid into rectangles (i.e. to generate the solution).  I didn't find a good algorithm for that, so I made up a mediocre one:
  1. Choose a random cell that isn't yet in a rectangle
  2. Randomly decide on a major axis (horizontal or vertical)
  3. See how far we can stretch from that cell along the major axis (e.g. for horizontal we see how many empty cells there are to the left and right)
  4. Choose a random range from that span, with length no greater than 8
  5. See how far a rectangle of that width can go along the minor axis
  6. Choose a random range from that span, no longer than 8, where the rectangle's area is no bigger than 16
  7. If we were able to pick a rectangle bigger than 1x1, then go back to 1 and repeat until all cells are consumed.
  8. If not, then pick a random rectangle adjacent to the cell and remove it, then go back to 1.
That last step was the key to speed.  At first I had it just give up and start over if it hit an isolated cell, but it had to do a lot of resetting before it randomly ended up perfectly dividing the grid.  The last step allows it to make a small adjustment and try from there, rather than losing all the work it put into the earlier rectangles.

A grid, divided.
 This gives us a divided grid.  A solution in search of a problem.  So now we choose a random cell from each rectangle to use as the hint.  Here things get a little tricky.  To make sure there is only one unique solution for a given puzzle, we need to go ahead and solve it.

I wrote a brute force solver, but it was taking far too much time for puzzles of moderately-large size.  One trick I used to speed it up was to do a first pass on each hint, seeing how many possible rectangles could go there at the beginning of the puzzle.  Then we sort the hints from fewest to most possible rectangles, ensuring that we try all the "forced" ones first.

I suspect I can make the solver even faster if I resort at each decision in the solver tree, because placing one rectangle frequently reduces the number of options for another, and I find that for most of the Shikaku I'm generating, every rectangle is forced at some point or another, leaving the best kind of brute-force tree ever: a straight line to the solution.

There was another problem.  Too often the generator would put two 2x1 rectangles next to each other, and too often the hint-picker would select kitty-corner hints from those rectangles, giving the puzzle multiple solutions.
An ambiguous Shikaku.
When this happens, the solver takes longer to run, and in the end we have to throw all that work away because we won't accept a puzzle with multiple solutions.  So I threw in a pass to detect when this was happening and auto-correct it (by moving one of the hints).

That left me with a fast-enough generator and a not-so-fast-but-maybe-ok solver to verify the puzzles.

A generated Shikoku-like puzzle.
For the other puzzle types, I have a feature that allows you to adjust the "difficulty" of the puzzle, but so far I don't have that for Shikaku.  I could go by the number of choices made in the solver (which is what I did for Numbrix and Hidato), or I might even be able to use "number of initially-forced regions".  However I would need to speed up the solver before I attempted that.  At the highest grid-size setting, 15x15, it currently takes a while just to generate one puzzle, and if it started getting picky about difficulty it might take way too long.

Solving in progress.
The UI is pretty straightforward.  You click and drag to make rectangles.  It colors a rectangle red if it's invalid (i.e. if it contains no number, or more than one number, or doesn't have the right area for the number it contains).

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.

Sunday, August 21, 2016

Generating Numbrix-like Puzzles

Very tiny
We got the kids interested in a simple kind of logic puzzle called Numbrix.  I showed my son a multiplication table and he became obsessed for a time with filling out more and more tables with bigger and bigger numbers.  Since he seemed to like writing numbers into boxes, we looked around for a puzzle we could print off the web that he could do, and found some kids' Numbrix at this "Math in English" site.

Numbrix is apparently a puzzle published in Parade magazine, developed by Marilyn vos Savant, who had the Guinness Book of World Records "Highest IQ" in the late eighties and also a serendipitous surname.  The goal is to complete a Hamiltonian path on a grid with consecutive numbers.  If you've heard of Hidato, it's like that but you can't move diagonally.  The ones at Math in English seem to be randomly generated, but the ones made by vos Savant are cleverly constructed by hand.

Either way, there are a limited number of Numbrices at both places.  I haven't found anything that generates them "while u wait", so I set about writing some code to do that.

A randomly generated Numbrix-like puzzle.
The first step is to generate a random-ish Hamiltonian path.  With a little googling I came across this "HamPath" library, which does the trick well enough.  Next we need to take away random numbers until we have a puzzle we like.  The puzzle has to have a unique solution, so each time we take away a number we have to check to see if there's another solution, so we need a solver.  The solver just runs all the possibilities and stops early if it finds a second solution.

I wanted it to have a difficulty knob, so we need some kind of measurement of difficulty and then we need to make sure when we take a number away we haven't made it too difficult.  I use two measures of difficulty: "choice count" and "stretch".

Choice count is a measure of how many branches were encountered in the solver.  This vaguely represents the number of ways you can go wrong if you just jot down numbers without thinking or looking ahead.  It's not perfect, because sometimes the path forward is obvious to a human but not to the solver.  It measures a choice at each number, but it would be better if it considered sequences of numbers that link two given cells.  For instance, starting with 1 in the above picture, you need to reach the 6.  There are a few ways to get to the 6, and the solver counts those, but it also counts ridiculous choices that never reach the 6, and I don't think humans would count those as making the puzzle more difficult.

The other measure is stretch.  Stretch is just the maximum distance between two given numbers.  A smaller stretch generally means you need to look ahead a smaller distance to find the next number, and it tends to mean fewer paths between one number and the next.  This one also has the benefit that it speeds up the solver; a very large gap in the numbers causes the solver to consider a large number of possible paths and while that might make an interesting puzzle, we need the solver to finish in a reasonable amount of time.

So we take away numbers, making sure the solution is unique and keeping the difficulty in check, and then stop after a certain number of tries, and now we have a puzzle.  The rest is user interface.

Puzzle in progress.

I tried to keep the interface simple.  The Parade site requires you to type the numbers, which I found annoying.  Instead I wanted to just click to place the next number.  There are some edge cases to consider, however.  The user should be able to start at any number, and go in both directions.  Also, the user needs to be able to remove numbers they've entered.  And when you hit a sequence you've already placed, it should skip over that to set you up to put the next number after the sequence.

As you'll guess from the intro menu, I'm thinking of adding more puzzle types later.

Monday, August 15, 2016

It's EELectric! (Junior)

My kids really wanted to play It's EELectric!, but it's way too hard for them.  So I made a new version with simpler rules and easier levels.  You know, for kids.  Or adults who couldn't stand the punishment of the previous version.