# Algorithm for creating a “Dot” logic maze

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. 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 !

• I would pay more attention to the nodes when generating the maze. You start at 0 and can pick 0-2 as your ending node. You can treat each intersection as a node with 2-4 links. Some paths won't contain a color and therefore won't change your value. You can treat all nodes connected this way as one large node. – Jason Goemaat Apr 20 at 12:13

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.