Puzzle generation

[sophiebits]

Are the puzzle generation scripts open source? I was thinking about classifying puzzles based on their difficulty – eg distinguishing puzzles where you need to only lock known pieces from ones where you need to take notes about edges from ones where even more complex strategies are needed.

[gereleth]

My solver/generator are in python so they're not part of this repo.

You can find pregenerated puzzle examples used in the game in static/_instances. Each puzzle is defined in a json file, the main thing to look at is the tiles array. It lists initial tile shapes left to right, top to bottom.

Tile shapes are encoded as numbers from 1 to 62. Each number is the sum of powers of two that correspond to directions. 1 is right, 2 is up and right, 4 is up and left, 8 is left and so on. So for example a horizontal straight piece would be 1+8=9.

I'm pretty interested in ranking puzzle difficulty myself but not sure how to do it. We could maybe start by collecting examples of easy/hard puzzles to form a sort of validation set for any approach.

[gordonwoodhull]

I keep finding new tricks that make it possible to lock the first few tiles based on local features (like adjacent 3s). I wonder if this is always possible.

I suppose solve times could be a (really noisy but low effort) way to see which puzzles are hard.

[sophiebits]

My tentative plan (once I find time to finish it) is to write a program that uses human strategies I've enumerated to try to classify which puzzles require more advanced strategies than others.

[gordonwoodhull]

FWIW, of the 6 “evil” dailies published in the last week, only number 4 contained none of the features which I use to lock a few tiles and form the basis of a solution.

That one was really hard - I think I spent 20-30 mins on a 5x5 wow!

[davidjdotorg]

I loved the 6/6 trek. I remember number 4 being hard as well.

On Mon, Nov 21, 2022 at 4:56 PM Gordon Woodhull @.***> wrote:

FWIW, of the 6 “evil” dailies published in the last week, only number 4 contained none of the features which I use to lock a few tiles and form the basis of a solution.

That one was really hard - I think I spent 20-30 mins on a 5x5 wow!

— Reply to this email directly, view it on GitHub https://github.com/gereleth/hexapipes/issues/38#issuecomment-1322855909, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAIIH6EVYP2MEPNY5VII5F3WJQK3JANCNFSM557MBQYQ . You are receiving this because you are subscribed to this thread.Message ID: @.***>

[sophiebits]

One idea I had is that a puzzle might be hard if there are many possible things you can deduce, and then later while solving there is only one or two things you can deduce (possibly repeat). Because then you need to be very eagle-eyed to make progress, needing to find what part of the puzzle to work on without any good ideas.

[gereleth]

I'm close to switching to client-size puzzle generation. No more limits to the amount of puzzles)).

I'd appreciate some testing at this preview link.

How it's supposed to work:

• A page for a certain puzzle size doesn't redirect to a static instance any more but shows a randomly generated puzzle instead.
• You can still open static instances at their urls like before. But the "New puzzle" button and "Next puzzle" link will take you to randomly generated puzzles from there.
• If you have an unfinished static instance then you'll be redirected to that puzzle to avoid interrupting your streak. That should be the only way to get into a static instance by clicking around the new version.
• Random instance and progress is saved to localStorage
• Tracking solve times and stats should work as before

One curious side effect is that you can play puzzle sizes not in the initial set by changing the url manually. So a /hexagonal/4 page will make 4x4 puzzles for you. And a /hexagonal/10000 will probably crash the tab :grinning:.

One thing that's lost is the ability to share a puzzle. Still thinking how to bring it back).

[gordonwoodhull]

I played 3 rounds of 15x15 wrap yesterday.

It seemed easier, like I could guess how it was generated more of the time. Is it the same generation algorithm?

I sometimes had runs where I just knew on the old, but it kept happening yesterday.

And my times were much better. It's only N=3 but my average was 8 minutes vs 21 minutes prior (!)

Will play a few more and see if this holds.

[gordonwoodhull]

As for sharing, you probably know the whole puzzle could go in the URL. https://news.ycombinator.com/item?id=34312546

[gereleth]

@gordonwoodhull Thanks for taking time to test this!

8 minutes vs 21 looks like a very drastic change. My own times for 15x15 wraps weren't that different between static/generated instances (4-5 minutes usually). But I double checked the solver steps metric... And it kinda agrees with you - static instances take more steps per tile on average than the new generated puzzles.

Their generating algorithms are different. Static instances were made by an "unconstrained solver". Basically start out every cell with a full set of 62 possible tiles/orientations and do the usual guess-and-check solving process until some solution emerges. This method isn't performant enough to work online. So I replaced it with Prim's algorithm for maze generation to create the initial solution shape. Both methods then use an additional step of ensuring solution uniqueness, but at this stage there are no differences.

I'll try to look into other maze generation techniques perhaps or maybe tweak the current pregeneration algorithm. I'm pretty surprised that there is such a significant difference in difficulty... I vaguely remember checking for it before and not finding anything big - must have messed up somewhere)).

[gereleth]

I shopped around some maze generation pages and found this gem describing the Growing Tree algorithm.

With different settings it can function either as Recursive Backtracking (producing long winding tunnels) or as Prim's algorithm (producing short corridors and lots of deadends). We can also do various mixes of the two approaches.

So it's like we have a slider control for branching amount. In fact I added such a slider to the custom puzzle page so you can experiment with it.

Here's a chart of puzzle difficulties at different branching amount settings. I can see that wrap puzzles with low branching factor are ridiculously hard)).

It looks to me like the difficulty of static instances falls somewhere between 0.5 and 0.75 branching factor setting. So I tentatively set the default level to 0.6 for now and hopefully the generated puzzles will be a bit more challenging.

[gordonwoodhull]

I’ve played a bunch of rounds with the new generator, and I agree it’s about the same difficulty as the original static puzzles.

Thanks for figuring that out and for adding a knob. Neat stuff!

[gordonwoodhull]

The “character” of the new puzzles is different; I think there may be more high-degree tiles and it seems harder to find patterns to “prove” and lock. In particular I used to look for a straight piece with four ones around it and I feel like I hardly see that anymore. Less pieces with five ones around them too.

I like it; just interesting how many factors there are.

[gereleth]

I did a count of tile types to check. Here are the results:

I only included sizes 5 and 40 here. Hopefully my x labels aren't too confusing)).

It looks like generated puzzles are heavier on turns and lighter on deadends. I'm feeling this generator likes to grow a little evil walk here and there.

[gordonwoodhull]

Interesting!

[gordonwoodhull]

Dailies got significantly harder a couple of weeks ago, appreciated!

They used to be much easier than the regular puzzles. But I actually gave up on one of the hexagons recently.

[gereleth]

I've been experimenting with the generator lately and managed to implement this "avoid obvious tiles" trick that I had in my old python generator. Meaning don't put straight tiles along a border or more generally don't use any tiles that would only have one possible orientation due to borders.

This constraint has a pretty significant effect on the chance of generating an evil puzzle. Here's a chart of difficulties from 10k puzzles generated with and without the constraint. In the no constraint blue set only two puzzles managed to break through my difficulty threshold of 2 steps per tile. While constrained generator that avoids obvious tiles made ~150 hard-ish puzzles.

So it looks like this constraint helps find hidden evil corners of the possible puzzles space. I wonder what other tricks I could use to the same effect =).

Puzzles generated this way go out next week (starting on 2023-02-19).

One other thing the old generator could do that the new one can't is use limited tile sets. I could ask it to do things like "use only turns, deadends and psi tiles" or "don't use straight pieces at all". But I didn't have any difficulty metrics then and chose puzzles based mainly on how I liked the look of the solution. Wish I could combine the approaches and make an evil psi puzzle)).

[mtmail]

"avoid obvious titles" is a great approach