12
$\begingroup$

I've enjoyed Fillomino for a couple years now. It's a region filling puzzle situated on a grid. The number in each box represents the size of the polyomino it belongs to, and polyominos of the same size cannot touch (except diagonally). Sample puzzle:

sample

Sample credit: Nikoli

Trying my hand at creating them, however, isn't going so well. I can easily create something for an unreasonably small grid, but that isn't fun or challenging. For example,

2..      (completed) 221
..2                  332
31.                  312

is a simple 3x3 puzzle with one distinct answer. The problem is that when I try to expand to a larger grid, the possibilities are overwhelming. It's very easy to lose track of why I put what where and what has already been accounted for.

My first instinct was to start with a "completed" grid and remove numbers until it was sparse enough to seem difficult, but I quickly found that deciding which ones to remove was hit-or-miss.

Looking around the web, there are several sources explaining how to solve these types of puzzles, but basically nothing on creating them.

I have an app on my phone that contains literally thousands of puzzles (of varying difficulty and size), so I'm inclined to believe that they can be easily computer generated, but I haven't seen an outline of an algorithm (by hand or code).

$\endgroup$
  • $\begingroup$ It may help to have one grid where you write the givens, and another on which you draw all deductions you can make from the clues so far. $\endgroup$ – Lopsy Dec 18 '14 at 20:13
  • $\begingroup$ @Lopsy That was my basic method when starting from a filled grid. The main problem was that every removal meant I had to re-solve a significant portion of the puzzle each time (to make sure the deductions didn't change), which is very time-consuming for a 9x9 or 12x12. My eraser is worn to a nub :( $\endgroup$ – Set Big O Dec 18 '14 at 20:22
  • $\begingroup$ Is it just me, or is the 3x3 you gave impossible? I probably just misunderstood the rules. $\endgroup$ – For I In Range Dec 18 '14 at 21:07
  • $\begingroup$ @ForIInRange Edited in the solution. It may be the "implied" 1 in the upper-right that causes confusion. There often isn't a 1-to-1 correspondence between givens and polyominos. $\endgroup$ – Set Big O Dec 18 '14 at 21:10
  • $\begingroup$ Thanks for clarifying, I didn't think you could have a polyomino without a number in it $\endgroup$ – For I In Range Dec 18 '14 at 21:12
4
$\begingroup$

For computers, re-solving the grid over and over is no problem at all, and that's basically how most generators for these types of games work. They either start with a blank grid and add clues or start with a filled grid and remove clues, re-solving the grid at each step to make sure it's working. (These aren't the only approaches, but I think they're the most common.)

Games like this are typically NP-complete (Fillomino is: http://www6.in.tum.de/Main/Publications/Ruepp2010a.pdf) which means that this isn't really practical for very large grids, but since no one plays very large grids anyway, it doesn't come up. Even then, it's not a problem if it takes an hour to generate a new puzzle if you only need one every day or week or if you can wait for a couple days to gather a large collection (not that it usually takes that long).

For making puzzles by hand, the process is similar, but humans (with practice) can take a lot of short cuts and make a lot of decisions based on more aesthetic values. For example, you might pick out a set of givens that make a nice pattern and see how close that gets you to a solution, and then base the addition or removal of givens on how well the previous attempt worked rather than on chance. If you know that there's a lot of ambiguity in one corner, you can guess that you'll need to add another given or two near there. You may not even have to solve the whole grid to know that part of it isn't going to work. Most computer programs won't take such shortcuts.

I can't say from experience, but I'm sure that with practice there are a lot of little things you could learn that would make making new puzzles easier. (Sudoku is popular enough that people have written articles on making sudoku puzzles. Some of that advice would surely translate to other types of puzzles.)

$\endgroup$
  • $\begingroup$ I suspect that the best way to make aesthetically-pleasing and satisfying puzzles would probably be to have a program which could quickly identify whether a particular set of clues would yield a unique solution, and then interactively edit a puzzle until the intended solution is unique. I'm not sure how easy it would be to make such a program run at a good speed; for moderate-sized grids, it would probably help a lot if a program could use information gleaned from checking one puzzle when checking a similar one. $\endgroup$ – supercat Dec 19 '14 at 18:08
  • $\begingroup$ An interactive editor would be a good compromise, but I suspect that proving whether or not a change in one area affects another would also be an NP-complete problem. (Though there's still probably ways to use such information to speed things up some, if it's needed.) $\endgroup$ – Joshua Taylor Dec 19 '14 at 20:43
  • $\begingroup$ The fact that a problem is NP-complete does not mean that there exist data sets for which no polynomial-time solution would exist; it does not imply that polynomial-time solutions won't exist for typical data sets. For any given area of the board, there will be a finite number of ways that it can be filled if one allows the region associated with a number within that area to extend outside it, but requires that any region not associated with the number in that area extend only one square beyond. In many practical cases, that number would be quite small. Subdividing the board into such... $\endgroup$ – supercat Dec 19 '14 at 20:50
  • $\begingroup$ ...areas would mean that a small change to the board would only require reevaluating the areas affected, and then processing the relationship among the areas taken as wholes. One could construct "hard" cases, but the cases which would require NP-hard effort would be hard to solve but not very interesting for humans. $\endgroup$ – supercat Dec 19 '14 at 20:52
  • $\begingroup$ I only suspect that it would be NP-complete. I don't have a proof. What I was saying though is that it seems likely to me that subdividing the board would itself be a hard problem. Now, it's true that NP-complete problems can sometimes be solved on some subset of possibilities, but I think for a puzzle game like this, the hard problems are going to be the most interesting to play. Also, for an interactive level maker, you can't make such a distinction anyway. It needs to give an answer no matter what the user puts in. $\endgroup$ – Joshua Taylor Dec 20 '14 at 20:31
2
$\begingroup$

Here's a possible approach that requires programming a solver:

  1. Start with a blank grid
  2. Pick some cells and assign them values.
  3. Solve the resulting grid and enumerate the solutions. If there are still too many solutions, then repeat step 2. If there are no solutions, either backtrack or start over.
  4. If you reach this step, then there shouldn't be many solutions left. Look at all of the solutions and see where the differences lie, and place appropriate numbers to ensure a unique solution.

You can do step 2 manually or via a program, your choice. I thought this could be a good way to come up with symmetric puzzles, since once you get a nice-looking grid going you can determine the minimum number of givens you have to provide to make the solution unique.

$\endgroup$
2
$\begingroup$

Here's an approach that works well for me when constructing Fillominos by hand:

  1. Choose a grid size, start with a blank grid of that size.
  2. Mark a pattern of givens by placing circles in some cells. (For example, just choose the pattern from the Nikoli example.)
  3. Place two or three numbers in some of these circles that allow making some deductions. (In the example, you might start by placing the 1 and 2 near the top left corner.)
  4. Make the deductions, filling in any cells determined by the clues you have put so far.
  5. Repeat steps 3 and 4 until the grid is filled.

This goes wrong in two ways:

  1. You run out of unused clue cells, and the grid is not filled. Here you can choose to add some more circles, or backtrack and try to fill some clues differently.
  2. You run into a contradiction. Apparently there was some deduction that you missed -- backtrack with this in mind.

There are ways to vary this approach, but you'll find those yourself with practice.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.