My previous post, “Solving fractal mazes” is a prerequisite to this one. Fair warning, this will be long and dense.

Fractal mazes contain infinite paths, but the only solutions permitted are finite. Some people find that disappointing. What’s the point of all that extra maze if we don’t get to traverse it? So my goal is to come up with a variant ruleset for fractal mazes that permits and formalizes infinite solutions. In fact, I will propose two distinct rulesets, provocatively titled Countably Infinite Fractal Mazes and Cantor Fractal Mazes.

Intuition about Infinite Mazes

Let’s start by looking at the most basic infinite fractal maze. This maze contains only two wires labeled 1 and 2, a single smaller copy of itself labeled A. Intuition says that if any fractal maze can be solved with an infinite path, this must be one of them.

In the Simple Infinite Maze, the visual representation shows a gap between the paths from junction 1 and 2. However, if we were to draw in the smaller submaze A, then that would reduce the size of the gap. The gap gets further reduced when we draw submaze AA, and then AAA, then AAAA. If we were to draw all the submazes, we would see that the gap between the two paths goes to zero width. Surely it would be okay if we just hopped across a gap of zero width?

Mathematically speaking, no, it’s not okay. A gap of zero width is still a gap. Jumping across the gap is definitely cheating. So we have to introduce a new rule that basically says jumping across zero-width gaps is allowed.

The question is, how do we formalize our new rule? If you’re solving a maze like this, how do you describe your solution, and how can we verify that it’s correct?

The infinite hop

In order to show that there is a zero-width gap between two paths, we need to show where each of those paths goes, and prove that they converge on the same point. In the simple infinite maze, we know we can go from 1 to A1, and from A1 to AA1, and so on. If we continue to follow this path, it approaches the center of the maze, which is a point in space that can be described with the infinite string “AAA…”. Likewise, we can go from 2 to A2, and A2 to AA2, and so on. This path also converges at the same point “AAA…”. Since paths converge at the same point in the maze, you should be able to hop from one path to the other.

But that’s a lot to write out, and as a solver you’re here to solve mazes, not write out a bunch of proofs. So my goal is to extract the essential conditions required for this proof to hold, and bake it into a special rule.

The Infinite Hop rule: You may hop between two addresses under the following conditions:

• Let S, T, U, and V be arbitrary submaze strings. S, U, and V may be empty strings, but T must be non-empty.
• Let 1 and 2 be arbitrary junctions.
• The two addresses may be expressed as SU1 and SV2.
• You show that there is a path from U1 to TU1.
• You show that there is a path from V2 to TV2.

The idea is that you go from SU1 to STU1 to STTU1, etc. all the way to STTTT… Likewise, there’s a path from SV2 to STV2 to STTV2, all the way to STTTT… These two paths converge to the same point, so an infinite hop is possible.

I know the rule looks a bit complicated, but it’s simple to use in practice. I’m not 100% sure, but I think that you never actually need U and V to be non-empty in order to solve a maze. So I also have a simplified form of the rule that you can use instead.

The Simplified Infinite Hop rule: You may hop between two addresses under the following conditions:

• Let S and T be arbitrary submaze strings. S may be an empty string, but T must be non-empty.
• Let 1 and 2 be arbitrary junctions.
• The two addresses may be expressed as S1 and S2.
• You show that there is a path from 1 to T1.
• You show that there is a path from 2 to T2.

Let’s apply this rule to the Simple Infinite Maze in Figure 1.

• There is an infinite hop from 1 to 2. Proof:
  • Let S = “”. Let T = “A”.
  • 1 connects to A1.
  • 2 connects to A2.

Nested hops

Next, let’s take a look at this fractal maze.

Here’s how I would describe the solution:

• There is an infinite hop from 1 to 2. Proof:
  • Let S = “”. Let T = “A”.
  • 1 connects to A1.
  • 2 connects to A2.
• There is an infinite hop from 1 to 3. Proof:
  • Let S = “”. Let T = “B”.
  • 1 connects to 2 (via the first infinite hop), connects to B1.
  • 3 connects to B3.

Since the first infinite hop is nested within the proof of the second infinite hop, that means you need to repeat the infinite hop at each step. We want to show a path from 1 to B1 to BB1 to BBBB…, but at each step of the way, we need to make an infinite hop. Therefore, the second infinite hop actually requires an infinite number of infinite hops.

However, it’s only a countably infinite number of hops. And in fact, no matter how many times you apply this rule, and have hops nested inside other hops, you will never have more than a countably infinite number of hops. This will prove to be a real limitation.

When a fractal maze follows this ruleset, I call it a Countably Infinite Fractal Maze, because only a countably infinite number of hops are permitted. Next, we’ll establish another ruleset which permits an uncountable number of hops.

Cantor Fractal Mazes

Here’s another simple fractal maze. Intuitively, there should be a path from 1 to 2 to 3. This maze, however, requires an uncountable number of steps.

Why is it uncountably infinite? Consider the set of all “hop points” —the points in space that need to be hopped over. Each hop point is associated with an infinite string. For example, one hop point is associated with the submaze “AABAABBBABB…”. In fact, there is a hop point for every infinite string consisting of “A”s and “B”s. This set is known to be uncountably infinite.

For the math geeks—presumably the only folks still reading this—the hop points form a Cantor Set.

So we want to create a new rule that allows us to solve this maze too. This new ruleset will be called a Cantor Fractal Maze.

The Cantor Hop rule:

• Let S, U, and V, W, etc. be arbitrary submaze strings.
• Let 1, 2, 3, etc. be arbitrary junctions
• Consider a set of two or more addresses, that can be expressed as SU1, SV2, SW3, etc. We seek to prove some set of connections between the addresses. They need not be fully connected, e.g. we might show a connection between the first and second, and another connection between the third and fourth.
• We start by presuming the same set of connections between TU1, TV2, TW3, etc., for all non-empty submaze strings T.
• Under this presumption, we prove that the same set of connections exist between U1, V2, W3, etc.
• Therefore, SU1, SV2, SW3, etc. are connected in the way supposed.

We also have a simplified form of the rule where U, V, W, etc. are all empty strings.

The Simplified Cantor Hop rule:

• Let S be an arbitrary submaze string.
• Let 1, 2, 3, etc. be arbitrary junctions
• Consider a set of two or more addresses, that can be expressed as S1, S2, S3, etc. We seek to prove some set of connections between the addresses. They need not be fully connected, e.g. we might show a connection between the first and second, and another connection between the third and fourth.
• We start by presuming the same set of connections between T1, T2, T3, etc., for all non-empty submaze strings T.
• Under this presumption, we prove that the same set of connections exist between 1, 2, 3, etc.
• Therefore, S1, S2, S3, etc. are connected in the way supposed.

Here’s the solution to the Simple Cantor Maze in Figure 3.

• There is a Cantor hop that connects 1 to 3. Proof:
  • Let S = “”.
  • Presuppose that T1 and T3 are connected for all non-empty submaze strings T.
  • 1 connects to A1, which connects (by presupposition) to A3, which connects to 2, to B1, then B3, and finally 3.

In summary

In a fractal maze, the maze is infinite in extent, but the only allowable solutions are finite. But we like infinity, so we extended the rules of fractal mazes to allow infinite solutions.

We identified two possible extensions of the rules.  The first extension, called an Countably Infinite Fractal Maze, introduces a rule to hop over a gap of zero width. I dubbed this an “infinite hop” and established specific conditions for when you’re allowed to do it. However, the rules only allow you to do this a countably infinite number of times.

The second extension, called a Cantor Fractal Maze, introduces a rule that allows you to hop over an uncountably infinite number of gaps.  I dubbed this a “Cantor hop”.

Both the infinite hop and Cantor hop are based on a form of induction. The infinite hop starts in a larger maze, and uses induction to show that you can go down into successively smaller and smaller mazes, down to infinity.  The Cantor hop presumes that you can make hops at infinite depth, and uses induction to show that this remains true in successively larger and larger mazes.  Strictly speaking, neither of these are “correct” proofs by induction, but they’re allowed here because we made up rules explicitly saying they’re allowed.

I made a good effort to make the rules complete, meaning that the set of solvable mazes under these rules should exactly match intuition.  However, I didn’t prove it, so it’s possible there are edge cases I didn’t think of.  If anyone writes a math thesis about it, I’d love to hear about it, and also this time please credit me if you use my images.

Sample mazes

Now you might be thinking, infinite fractal mazes are cool conceptually, but do they make good puzzles in practice? As fun as they are to talk about, I consider it a major problem that I need to spend all this time explaining the rules before you can even start. But since we’ve already done the work, it seems a shame not to include a couple sample mazes.

 

From what I can tell, the method to solve (and to design) a Cantor Maze is completely different from that of a Countably Infinite Fractal Maze. Also, I personally prefer the latter. I have a computationally efficient method of solving Cantor Fractal Mazes (which I will keep to myself), and I found it difficult to make a Cantor Fractal Maze that I couldn’t immediately solve. On the other hand, I suspect Countably Infinite Fractal Mazes have greater computational complexity, and the design space is more expressive.

That said, both of these mazes were fun to make, and I expect them to be quite challenging.