I recently came across a cute game called https://enclose.horse. In this game, there is a horse in the middle of a field and a bunch of rivers surrounding it. You have to "enclose" the horse by cutting off its access to the boundaries of the map using a limited set of walls. The game is to create the largest possible space you can under those constraints. It's harder to explain in words than if you just go try the game.

What the game is asking you to do, in graph theory terms, is to find a vertex cut that maximizes the number of vertices on a particular side of the cut. A vertex cut is a set of vertices that separates two other sets of vertices. In this image, the set W separates the sets A and B:

In the horse game, A is the square that the horse stands on, B is the set of edge tiles, and there are edges between any two adjacent grass tiles. We are picking a set W when we place walls as we try to find a set that the horse would have to pass through in order to escape.

In school I had the thought that in general, solving computationally difficult problems was probably a good basis for constructing puzzle games. I don't think I was right in general, since my "minimal vertex cover" game was not particularly fun. But I think this game is pretty fun overall! And the presentation is cute and good.

As an armchair game designer, I'm obligated to weigh in that I think this kind of game (including stuff like Wordle and my personal favourite catfishing) would be dramatically improved design-wise by the inclusion of a timer. I think balance-wise ("balance" perhaps not in the sense of like, "game balance" but in the sense of, "the composition of the elements of design being in harmony" sense), the strategy of "spending a really, really long time thinking about it" is much too strong and not that much fun, and negates a lot of strategies one might otherwise develop to quickly identify possible solutions and learn more about the underlying problem structure. I recognize that this kind of element would probably make for a less popular game, but I think it would make for a more sound game.

Anyway. Playing this game made me think about a cool theorem from graph theory that is a useful such strategy for quickly convincing yourself of certain facts about the playing field. Go play the game first, and then come back, so I don't have to explain in more detail how it works.

Menger's Theorem says that in a graph, the number of vertices you need to delete to disconnect two vertices is equal to the number of disjoint paths between those vertices. By disjoint paths I mean paths that connect A and B and don't share any vertices (besides those in A and B).

One direction of Menger's theorem, that you need to delete at least as many vertices as disjoint paths, is very easy. The other direction is harder and more surprising.

Consider this region in day 6:

Specifically the yellow exit. It's probably not too hard to convince yourself with some trial and error that it's not possible to block that exit off from the red zone with fewer than three walls, but we can use the easy direction of Menger's theorem to prove it quickly and easily by finding three disjoint paths from the red zone to the exit:

These three paths constitute a proof that you need at least three walls to block that exit off.

However, since we can block off the horse specifically from going that way with only two walls:

Menger's theorem tells us that there are at most two disjoint paths from the horse to the exit (going that way, we can actually walk around in this particular map.

Tools like this are why I think this kind of game would benefit from a stricter time limit: building up these quick heuristics is fun! And can let you quickly prune parts of the search space without having to do an exhaustive search. But without a time limit, become a bit less useful, since doing things quickly is not especially valuable. I'd like to see future games of this nature explore this sort of thing a bit more.