Hacker News Reader

Comment by Scene_Cast2 | Hacker News Reader

Not to detract from the fun of the game, but I get a strong feeling that this is probably a very studied problem in topology - and that thought keeps on nagging me to write a solver script :)

View on HN

Yes in fact I've spent the past 6 months thinking about whether i could build a level generator that can verify and solve the levels too. The way I see it, with a simple 5x5x5 cube with 5 colors on it, the number of possible combinations to check is 75^5, which might take awhile to brute force, so there needs to be a intelligent way to map lines.

The general case might be something like that, but you only need any given configuration that fits those parameters (that is, you're not trying to solve complete, abstract topological problems). Maybe if you arbitrarily fix the first path, thereby artificially reducing the solution space? Just thinking out loud. Very cool puzzle!

EDIT: or even take a lower-level solution and inject another path into. So every prior level is a seed to future levels. Rotation of the three faces, even cycling the colors, would probably make it hard to recognize the older level within the new one (at least, for casual use).

I think solving any of these can be reduced to a max-flow problem, and thus it is efficiently solvable.

Many of the levels have been designed so that if you follow the path of least resistance to solve them, you will always be left with one line that wont connect. Thats the true puzzle part of the game, and that's the aspect that makes me think it's difficult to solve without resorting to brute force.

I think you are right, it's harder than I thought.

The problem can in fact be modeled with a graph in which you need to find vertex-disjoint paths between pairs of vertices (s1,t1), (s2,t2), and so on, but this problem seems not to be reducible to max-flow, instead it is NP-hard.

My thoughts: what if you select the initial 5 colors, then recursively "extend" one of the colors in one of three possible directions. The sum of results is your level-space. Store results in a DB. Then, select all levels that have a)cell coverage of 85%+ b)min path length of 5 on all paths.

In order to cut down some of the search, you can make the recursion smarter (e.g. extend one color at a time, early cycle / impossibility prediction, etc)

This is an ideal problem for constraint solving. If there is one thing constraint solving does well it is make NP-Hard problems more manageable. I wrote up a quick solution to the first puzzle in sabr (1), you can see what the puzzle result looks like here (2). The key insight is: "each color must be surrounded by exactly two of its color, unless it is on an end, in which case it is surrounded by exactly one" after that it's just a matter of coding it up. It's not much extra work to go from here to a generator, which I may make later if I have time. Cool puzzle game, I like it ;D.

1) https://github.com/dbunker/SABR/blob/master/module/other-tes...

2) https://github.com/dbunker/SABR/blob/master/module/other-tes...

Haha, yes, that's what I thought too.

But that's what makes it fun. It's the perfect combination of familiarity & challenge!

Reply on news.ycombinator.com