12

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).

Set Big O
  • 6,604
  • 3
  • 28
  • 41
  • 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. – Lopsy Dec 18 '14 at 20:13
  • @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 :( – Set Big O Dec 18 '14 at 20:22
  • Is it just me, or is the 3x3 you gave impossible? I probably just misunderstood the rules. – For I In Range Dec 18 '14 at 21:07
  • @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. – Set Big O Dec 18 '14 at 21:10
  • Thanks for clarifying, I didn't think you could have a polyomino without a number in it – For I In Range Dec 18 '14 at 21:12
  • Start with a filled grid and slowly remove 1 number at a time, each time taking a look and making sure it can be solved by looking at the possibilities and determine which move will be impossible. Kinda like reverse engineering soduko, but you know, fillominoe. – warspyking Dec 19 '14 at 01:08

3 Answers3

4

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.)

Joshua Taylor
  • 1,721
  • 9
  • 22
  • 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. – supercat Dec 19 '14 at 18:08
  • 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.) – Joshua Taylor Dec 19 '14 at 20:43
  • 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... – supercat Dec 19 '14 at 20:50
  • ...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. – supercat Dec 19 '14 at 20:52
  • 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. – Joshua Taylor Dec 20 '14 at 20:31
  • The fact that solving the general case is NP-complete actually isn't a problem. You want a puzzle that is solvable completely by a human, using local deductions. So you only need to apply automatically all deductions a human could do. If that solves the puzzle, you can go ahead and try to remove one clue. If the process doesn't solve the puzzle, even if a single solution exists, you might as well reject it as it would be too difficult for humans, and add a clue. You also can measure the difficulty by ranking the difficulty of each deduction and counting how many there are by difficulty. – Florian F Dec 21 '14 at 12:12
  • NP-complete problems aren't too difficult for humans. Almost all of the most popular puzzle games are NP-complete. I don't think this is a coincidence. Also, at least in Sudoku, there are plenty of puzzles out there that require guess-and-check at some point. I don't think you can actually make a 9x9 Sudoku grid that's solvable, but too hard for a human, and I suspect this would hold for any NP-complete puzzle. (After all, NP-completeness is about the increase in complexity with the increase in size, and you can only fit so much on a page.) – Joshua Taylor Dec 21 '14 at 21:20
  • @JoshuaTaylor: An interesting but under-appreciated aspect of puzzle-solving technique for both Sudoku and Fillomino stems from a "rule" that's not always stated: "legitimate" puzzles have a unique solution, so showing that a partial grid couldn't have exactly one solution is sufficient to show that it isn't the solution. I don't know if the "uniqueness" rule reduces the algorithmic difficulty, but it's a key aspect of many human solving techniques. Of course, verifying uniqueness would require a solving technique which didn't exploit it. – supercat Dec 21 '14 at 22:52
  • Unfortunately, I don't think uniqueness is much help algorithmically. While you can occasionally exploit it to show you're on the wrong track (for example, by showing that no further deductions can possibly resolve certain squares), or by building your solver to only use deductions that guarantee uniqueness (though you'd have to be careful that it can still solve all valid puzzles), the question of "is there another solution" is itself generally NP-complete. – Joshua Taylor Dec 22 '14 at 02:47
  • @JoshuaTaylor: If one is only required to find a solution in cases where it is unique, that will make it possible to rule out many local patterns within partial solutions. For example, in a Filomino puzzle, if one ends up with a 2x2 square in the lower-right corner there two opposite corners have different numbers that each have one square unaccounted-for, and the other two corners are blank, and all numbers around that square are filled in, a uniqueness guarantee would allow one to rule out that situation regardless of what appeared elsewhere on the board, since... – supercat Dec 22 '14 at 16:16
  • ...nothing that could appear anywhere else would make it possible to distinguish between two ways of filling in that corner. I suspect that there are probably enough situations where a uniqueness guarantee wouldn't help that the problem would still be NP-complete, but I've certainly found uniqueness-based techniques useful with published puzzles. – supercat Dec 22 '14 at 16:19
2

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.

graaaarg
  • 221
  • 1
  • 3
2

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.

Sp3000
  • 7,527
  • 2
  • 27
  • 60