Can I predict if a randomly-generated puzzle will be solvable?
June 24, 2020 12:34 PM   Subscribe

I enjoy a mobile puzzle game called Fill (Google Play, browser-playable knockoff). You're given a grid with some number of cells blocked out and a starting position. The object is to fill all of the remaining cells using a single continuous line. I can easily generate puzzles of this sort with dice and graph paper, but is there any way that I, a functioning innumerate, can know with certainty if a given configuration is solvable?

I am reasonably good at these, but I have definitely encountered puzzles that I would have given up on if I hadn't known in advance that a solution was possible.

I would like to play a version of this game on paper, generating starting configurations using dice rolls. Easy enough! But what would be involved in predicting whether a given configuration is or isn't actually solvable?

Here are some examples I made. The last three are solved, while each of the first five had an unfilled "extra" cell (yellow) with every route I tried. Short of attempting every possible path through the maze (I understand the principle if not the mechanics of a backtracking algorithm), how would I determine whether those puzzles are in fact unsolvable?

It would be great to have some system for actually doing this, but as much as anything I'm curious to know how a mathematician or programmer or whomever would approach the problem. What concepts are in play? What patterns can I look for? What can these puzzles, which I like, teach me about math, which I stopped taking in grade eleven, twenty years ago?
posted by wreckingball to Science & Nature (23 answers total) 1 user marked this as a favorite
I’m not sure how this would fit your workflow, but the easiest way to generate solvable puzzles for this sort of thing is to start with a solved puzzle and randomly walk it backward until you’ve reached a starting state. If you were willing to sit down and do a bunch backwards you could shuffle them and do them forward again.
posted by Tell Me No Lies at 12:45 PM on June 24

Okay, so this is essentially a graph theory problem. The squares are nodes, and adjacent squares have an edge between them. You want to traverse the graph visiting every node exactly once.

There’s probably a relatively simple theorem about this, but I don’t work with graph theory enough to know the answer off the top of my head. Might take a stab at it later if nobody else comes up with a definitive answer.
posted by mekily at 12:46 PM on June 24 [2 favorites]

Given that the underlying problem is NP-complete, I doubt you'll find a more efficient test than backtracking.
posted by flabdablet at 1:08 PM on June 24 [4 favorites]

I'm a programmer and I'd just brute force that bad boy.

What you are looking for is a Hamiltonian Path. It looks like determining if an arbitrary graph contains a Hamiltonian Path is NP-Complete (technical term. It means "we don't know a fast way to do this") and knowing the starting point won't change that.

Brute force might be the way to go. Alternatively, you can turn your first problems into solvable ones by just blanking out the squares you can't figure out how to include in the solution.
posted by It's Never Lurgi at 1:08 PM on June 24 [2 favorites]

Foiled by flabdablet. I have the same link in my paste buffer. But you might want to start with Hamiltonian path before getting to the problem bit.
posted by zengargoyle at 1:23 PM on June 24 [1 favorite]

Even though the general problem of determining what graphs have a Hamiltonian path is hard, this is not that general problem, it's a very restricted one. This is a planar graph with lots of other properties. I wouldn't be surprised if there was some elegant method to determine which squares to remove so that you would get a solution.

But I am not a mathematician, so if I were doing what you propose, I would take a code book approach. Find a bunch of puzzles that do work and then look for a way to organize them into some kind of generation instruction set where random generated values could choose which way you go in the instructions.
posted by demiurge at 1:31 PM on June 24 [2 favorites]

Brute force might be the way to go.

Yeah, sadly I suspect that the way you know if a given puzzle is solvable is by solving it.
posted by GuyZero at 1:34 PM on June 24

Yes, probably obvious if you've played a few games. If you have one square that only has one traversable edge, then it has to be the final destination. If you have two squares that have only one traversable edge each, one must be the start and the other the end. If you have three of them, it's unsolvable.
posted by zengargoyle at 1:37 PM on June 24 [1 favorite]

As others have mentioned, this is a Hamiltonian path problem on a very specific class of graphs (finite induced subgraphs of the infinite grid). This paper addresses the question of its algorithmic complexity, indicating that it is indeed NP-complete. The proof uses the fact that the Hamiltonian Path Problem is NP-complete even for the restricted set of directed, planar, 3-regular graphs, and shows that any such graph could be converted, via a series of vertex and edge inflations, to an induced subgraph of the grid.
posted by jackbishop at 2:14 PM on June 24 [3 favorites]

The extra constraints due to arrowed squares in later levels are probably enough to sink any really tidy go/no-go check, I fear, because they make the underlying graph a directed one and remove even more symmetries than the blocked squares on the non-arrowed puzzles do.

The problem of finding an elegant way to generate solvable grids does strike me as likely much more tractable than the problem of checking whether any arbitrary grid is solvable. There will be lots of special cases that can be trivially shown to be unsolvable (zengargoyle identifies one, and there's also the case of grids containing squares with no traversable edges at all) but I think the majority of grids will still need a properly exhaustive backtracking search to be sure.
posted by flabdablet at 2:15 PM on June 24

Should have previewed; jackbishop's link points to a paper by people who have clearly thought about this much harder than any of us :-)
posted by flabdablet at 2:20 PM on June 24

There's an easy way to check if a given grid doesn't have a path: imagine coloring the squares in black & white like a chessboard, with your starting square being a black square, and count the number of black and white squares. If a path through the grid exists, it alternates between white and black squares. So the number of white squares must either be equal to the number of black squares (if the path ends on a white square), or one less than the number of black squares (if it ends on a black square). If the numbers of each color of the squares do not satisfy this, no path can exist.

The converse, unfortunately, is not true: if the numbers of each square do satisfy this criterion, it does not necessarily mean that a solution exists.
posted by Johnny Assay at 2:25 PM on June 24 [5 favorites]

Ok, jackbishop has established that the problem is NP-complete, meaning that there's no easy way to check whether a given grid has a solution.

You could, however, generate solvable grids by starting with an empty grid (or one with just a couple squares filled in), drawing a loopy path through it that passes through almost all the squares, then filling in the ones that remain. Now you have a solvable puzzle, and you could rotate or mirror it so it's less recognizable and come back to it later.
posted by mekily at 2:49 PM on June 24

Looking at the examples you provided and applying this criterion, we see the following:
  • First row left: 16 black, 14 white, so no path exists. First row right: 15 black, 17 white, so no path exists.
  • Second row left: 17 black, 16 white, so the criterion is indeterminate. Second row right: 15 black, 15 white, indeterminate.
  • Third row left: 16 black, 15 white, indeterminate. Third row right: 16 black, 16 white, indeterminate.
  • Fourth row left: 18 black, 17 white, indeterminate. Fourth row right: 17 black, 17 white, indeterminate.
("Black" and "white" mean the checkerboard sense that I used above, not the actual colors in your grid. Sorry for the notational overload.)

The argument can be further refined if you know where end of the path must be. For example, in the second row left and third row left grids, there are dead-end squares that are white, so the path must end there; but this is inconsistent with there being more black squares than white.
posted by Johnny Assay at 2:52 PM on June 24

Not to knock the "it's NP-complete" answers, but there _are_ sub-groups of puzzles you can say are solvable. For instance, if you roll two dice to get numbers M and N, then your puzzle is an M×N grid with no cells removed. Not very fun, but solvable for sure.

Is there a more diverse and interesting class of puzzles that will remain solvable? I'm not sure how to identify one for the purposes of manual generation.

The suggestion to generate a path and then try to forget about it, though, makes me think -- maybe you want to trade puzzles with someone, and generate them this way.
posted by the antecedent of that pronoun at 2:54 PM on June 24

As mentioned upthread, it's going to be nearly impossible to predict whether a given configuration is solvable if you just start with (say) a 6X6 grid and then randomly X off squares.

But drawing a legal line on a blank 6X6 (or whatever) grid is super-easy. So just start with a completely blank grid, pick a starting square at random (use dice if you like), draw a legal line of whatever length you like from that square to some other square. Then mark the starting square, X off all the squares that are not on the line, and there is your puzzle.

You've got the starting square marked and all the squares X-ed off that don't belong on the line. And what remains is absolutely guaranteed to be solvable.

If you want to add the little directional arrows, you can even do that: Just mark an arrow on a square here or there along your line, maybe about half way through it. You could use dice or some other random process to decide how many arrows to include and exactly where to include them.

If you want to use dice or some other random process to help generate the path of the line that would easy, too. You could do a "left - right - straight" decision with the dice, or number legal moves around any given position 1 through 4 and use your random process to decide which to move to. You will almost always have some of the moves that are illegal and if your random process happens to land on one of those, just try again until you get a legal move.

Besides using dice or a random process to decide the line, you can try to draw patterns, leave certain squares open in certain patterns, put the arrows along the line in places that look unexpected or hard, and other such things that look like they'll make the puzzle harder to solve.

FWIW I'd bet money that is exactly how the original puzzle designers make their puzzles. The problem becomes less how to generate new puzzles and more how to judge the difficulty of the new puzzles you can (very, very easily) make.

The trouble with this is that you've generated the puzzles by making solutions, so that means you have already seen the solution. But if you were to generate say 100-200 puzzles this way and then shuffle them, then wait a few days or weeks before working them, it might be surprisingly hard to remember the solutions based on merely the end result (which should just be a card with some squares colored and maybe a couple of arrows).

Anyway, this process would definitely result in puzzles that are 100% always solvable!
posted by flug at 3:01 PM on June 24 [4 favorites]

mekily wrote...
You could, however, generate solvable grids by starting with an empty grid (or one with just a couple squares filled in), drawing a loopy path through it that passes through almost all the squares, then filling in the ones that remain. Now you have a solvable puzzle, and you could rotate or mirror it so it's less recognizable and come back to it later.

This is the sort of thing I had in mind when I suggested creating puzzles by working them backwards. Looking at how simply mekily has layed it out, I think you could easily turn out 20 or 30 workable puzzles and then go back and solve them later.

For the computer scientists who have gathered around this thread I just want to note that a much more interesting problem is how to prove there is a unique solution.
posted by Tell Me No Lies at 8:29 PM on June 24

Same way, exhaustive search. You know how long the path has to be, so once you find it the problem is solvable, if you continue and find another path of the required length, then the problem doesn't have a unique solution. The rest is just book-keeping of the current state of the path and the remaining yet to be explored paths. Pretty much any sort of maze solving algorithm could be made to be exhaustive. Pick the start, try NESW, if you can't go N because it's blocked or you've been there try E. Repeat. When you hit a dead end, go back erasing your path until you hit a point where you can go a different direction. Repeat. Keep track of how long your current path is to determine if you've covered all the squares (you've been marking and unmarking them as you move along and backtrack). Repeat until you're back at the starting point and you've tried all directions. Done.
posted by zengargoyle at 12:23 AM on June 25

dailyprogrammer/2015-10-30_H_searching-a-dungeon at master · zengargoyle/dailyprogrammer · GitHub - here's a similar seek-path-to-goal solver. It would just need keeping track of squares visited and no goal to generate every path eventually, then just keep the maximal possible paths and count how many there are.
posted by zengargoyle at 12:34 AM on June 25

Repeat until you're back at the starting point and you've tried all directions. Done.

Or, depending on size, the heat death of the universe has arrived.
posted by Tell Me No Lies at 6:04 AM on June 25

The puzzles in the web-based knockoff were certainly not all uniquely solvable. However, this is _usually_ a constraint that puzzle-makers set for themselves, in my experience.
posted by the antecedent of that pronoun at 8:38 AM on June 25

Were I to try and make unique puzzles of this type I'd ....

Start by making a bunch of small sub-units that have a unique path. Then patch those together like a jigsaw puzzle into a large collection of pieces.

A bunch of mini-mazes, maybe with multiple parallel paths... like if you enter this square the only way out it that square (and vice-versa) but if you enter this square it's a different path and you can only exit that other square. You can rotate and flip these and connect them together like a circuit.

The smaller pieces can be solved/created without worrying about the heat death of the universe. Fit together and you can make a big hard puzzle.
posted by zengargoyle at 6:26 PM on June 25 [1 favorite]

« Older What is there to know about moving to and living...   |   How can I tell what flapper to use for my Toto... Newer »

You are not logged in, either login or create an account to post comments