Generating Shikaku-like puzzles

A very small
Shikaku
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).

Probably Puzzles