Algorithm for creating a "Dot" logic maze

Question

I've been looking at Robert Abbott's logic mazes, in particular his Dot maze, and I'm trying to understand how they can be constructed so I can write an algorithm to do this automatically for arbitrary size and colours.

For now, I'm sticking to a small size with three colours. I don't yet have his book SuperMazes which reviews suggest may contain instructions on building such logic mazes.

Here's the maze, where you must go from the start to the goal stepping on dots in the order Red, Green, Yellow, Red, Green, Yellow, ...

My question is how do you go about constructing such a logic maze, or what are the principles behind building such a logic maze? Is there a description of an algorithm to generate them perhaps?

I noticed that for the first part the player must go through 3 red dots, which isn't possible in direct order, so this requires making some loops until the player gets beyond the last of the three red dots. I guess there must be some kind of "wall" of dots prohibiting the player from proceeding beyond the last of the three red dots in any other way. The remainder seems plain sailing where the player just alternates naturally between coloured dots, except for a small detour near the end. Moreover, if we step backwards Green, Red, Yellow, ... from the goal we see that it's plain sailing (i.e. there is no option but to travel along one path) back to the last red dot mentioned above. Then there appears to be multiple yellow dot options.

Answer 1

To avoid cluttering up the main question I've moved my work so far to an answer which I'll add to as I improve the solution. This is just a partial answer at the moment.

I created the dual graph of the dots (vertices), to see if I can work anything out from that. Clearly the graph and its dual will always be planar, and we're looking for a walk around the graph where we can only step along edges in the weight order 1, 2, 3, 1, 2, 3, ...

What seems to make such a walk "interesting" is the traversal of all edges of a multi edge pair of vertices. As you can see the two pairs of multi edge vertices above are fully traversed in the solution walk. These multi edge vertices have the ability to land you back on a vertex with a different colour (edge weight) than you left with, which I'd say is a big factor in the perceived puzzle complexity.

So a solution walk $$W=v_0e_0v_1e_1v_2\cdots v_{n-1}e_{n-1}v_n$$ needs to contain some of these loops. For example, to find such a walk, make another graph with all multi edges removed, then find a path from start to goal passing through the corresponding multi edge vertices in the original graph, then extract the corresponding multi edge subgraph and number the edges from start to finish.

Now assume we've found an interesting walk $W$, like the one from the original puzzle highlighted in green below.

Next we need to add deflecting weights to any edge $e\not\in W$ joining to a vertex $v_i\in W$, such that $$w(e)+1\not\equiv w(e_i).$$ These are the blue and red edges in the diagram below. Blue edges show the weight options which will deflect from the green solution. No such options exist for the red edges since any choice could lead the player down $W$.

We can then start to make our choices. By experimenting I've found that the choice made should attempt to increase the number of different weights incident on the vertex belonging to $W$, or if the number is maximised then pick a random available weight. For the red edges, pick a weight that would lead the player down the green path furthest from the goal.

Going to code this up next !

Answer 2

Your first question is whether you're going to do this by hand or with a computer. I would do the latter and that's the assumption of this answer. If you want to do it by hand, then you need to use all the craftiness of a human solver to take short cuts. Even so, I would consider getting a computer to solve the mazes.

So. First, you need a maze solver!

To solve a maze like this you need to change it into a graph.

The graph would not necessarily look like the maze. In particular, this maze has "states", meaning you can arrive at the same physical location but be in a different state (meaning what is the next color you must cross). So each "node" (meaning the entire area between dots) is actually 3 nodes (one for each color).

This is a very common idea for mazes that have a "state". See my recent puzzle as an example. Or www.clickmazes.com.

To be clear, there would be three nodes in each of the places that I've marked with a diamond and they would be connected with 1-way arrows (so we'd be using a directed graph, aka digraph). By the way, there are many places where you might be tempted to take a short cut, for example in the bottom right-hand corner. I would recommend against that. The computer won't mind the extra step or two to solve the maze and it will keep it cleaner for when you start varying the colors.

Then an algorithm like Dijkstra's will solve your maze or determine it to be unsolvable very rapidly.

Now you have a number of choices, depending on details. You could start with a layout and have the computer vary only the color of the dots. Each maze you get could be checked and you could select those that have a good score (eg steps to complete or some complexity measure).

Computers are very good at varying a solution and seeing what changes, so once you get a decent solution, you could vary each dot through all the colors (or each pair of dots or whatever) and find optimal solutions near to the one you've found already.

You can also get the computer to just generate mazes at random and test them, and then use ones that happen to be good to do slight variations. You can use a kind of evolutionary approach, where you mate two reasonable mazes that you find randomly and keep the "better" ones.

And you can just go through all the possibilities (this is relatively rare). For example, you have 30 dots in your simple maze and each can be 3 colors, so there are $3^{30}$ mazes to check. This is not really a feasible number to check by brute force in general, so you need some way to whittle it down. In a maze like yours, you could break the maze down to multiple components and maximize each component separately, but that would take a bit of thought and care.

You can also think about how you varying the topology. It can be done in a similar way. I would recommend that you do it in a two-stage process. Define the topology (either randomly generating it, or do it by hand to get things started in a way that is pleasing to you as the puzzle creator), and then do all the above.

I personally use python for this, but almost anything will do.

Answer 3

This kind of maze can be understood as finding a path from a given starting vertex to a given ending vertex in a graph whose vertices are states, where each state specifies the current region between dots and the next colour that must be reached, and there is an edge v→w iff from state v you can move to state w on the next step. Then all you need to solve such a maze is just to perform a BFS (breadth-first search) from the starting vertex and see if it reaches the ending vertex.

Once you have a solver, you can design a heuristic for how hard it is, and then randomly construct mazes and choose a solvable one that maximizes the hardness heuristic. One hardness heuristic might be to count the number of branches during the BFS up to the point that the ending vertex is reached. That makes a non-branching maze have zero hardness, and a maze that needs more branches to be harder. This heuristic applies to any BFS-solvable maze.

Note that if you really want a hard puzzle you have to be careful to have a hardness heuristic that can defeat good puzzle solvers. For instance, I could easily solve your example instance by doing a BFS from the ending vertex (i.e. green→red→yellow→...)! So if you had based your hardness on a BFS from the starting vertex you may fail to see that a puzzle is easy using a BFS from the ending vertex. There is no systematic way of creating hardness heuristics, and in general how good heuristics you can create is limited by how skilled you are at solving puzzles.

Now the biggest problem is how to efficiently construct hard mazes according to a given hardness heuristic. Well, that is in general an even harder problem (and even skill at solving puzzles would not help much), because it is often is an instance of combinatorial optimization over an exponential search space, which is extremely hard for very discontinuous objective functions. Here the objective function is the hardness heuristic.