4D Maze Creation!

Question

I have a problem for anybody who cares to try.

You're job is to take a 10x10x10x10 size tesseract and design a maze that fits. The maze must be a perfect maze (no loops, one path cannot be followed and find the start of its path without having the solver turn around), and must have at least 25 dead ends, and at least 8 branching off of other dead ends.

The answer you provide should be an image, and at most of the tesseract (if not all) should be used.

note; The fun is in creating the 4D maze! 2D and even 3D is too easy for you puzzlers, I'm going to challenge you!

To limit the possibilities of answers, in order for your maze to be accepted, it has to be the shortest possible maze that meets all the requirements already stated. By shortest I mean the maze with the least area of the tesseract filled.

Answer 1

Here it is. Access the direct link to see it in its full size (or zoom-in the image).

This is a plane of boards (horizontal is $w$ and vertical is $z$) where each board is a 2D-plane (horizontal is $x$ and vertical is $y$). To change your $x$ and $y$ positions, just walk around in the current board.

The arrows allows you to change your $w$ and $z$ positions. They make you jump one board up (blue), down (yellow), left (red) or right (green), accordingly to its direction.

So, if you are in a particular $(a, b)$ position of a board:

• By using the up (blue) arrow you will land in the $(a, b)$ position of the board immediately above of the current one.
• By using the down (yellow) arrow you will land in the $(a, b)$ position of the board immediately below of the current one.
• By using the left (red) arrow, you will land in the $(a, b)$ position of the board immediately to the left of the current one.
• By using the right (green) arrow, you will land in the $(a, b)$ position of the board immediately to the right of the current one.

To generate this, I created this Java program:

import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import javax.imageio.ImageIO;

/**
 * @author Victor
 */
public class Tesseracter {
    public static void main(String[] args) throws IOException {
        TesseractMaze maze = new TesseractMaze(10, 10, 10, 10);
        BufferedImage im = maze.draw();
        ImageIO.write(im, "png", new File("maze.png"));
    }

    public static final class Coordinate4D {
        private final TesseractMaze maze;
        private final int w, x, y, z;

        public Coordinate4D(TesseractMaze maze, int w, int x, int y, int z) {
            Objects.requireNonNull(maze);
            if (w < 0 || w >= maze.wSize || x < 0 || x >= maze.xSize || y < 0 || y >= maze.ySize || z < 0 || z >= maze.zSize) throw new IndexOutOfBoundsException();
            this.maze = maze;
            this.w = w;
            this.x = x;
            this.y = y;
            this.z = z;
        }

        @Override
        public int hashCode() {
            return Objects.hash(maze, w, x, y, z);
        }

        @Override
        public boolean equals(Object another) {
            if (!(another instanceof Coordinate4D)) return false;
            Coordinate4D c4d = (Coordinate4D) another;
            return maze == c4d.maze && w == c4d.w && x == c4d.x && y == c4d.y && z == c4d.z;
        }

        public int squareDistance(Coordinate4D another) {
            Objects.requireNonNull(another);
            if (maze != another.maze) throw new IllegalArgumentException();
            int dw = Math.abs(w - another.w);
            int dx = Math.abs(x - another.x);
            int dy = Math.abs(y - another.y);
            int dz = Math.abs(z - another.z);
            return dw + dx + dy + dz;
        }

        public Coordinate4D minusW() { return w == 0              ? null : new Coordinate4D(maze, w - 1, x, y, z); };
        public Coordinate4D plusW()  { return w == maze.wSize - 1 ? null : new Coordinate4D(maze, w + 1, x, y, z); };
        public Coordinate4D minusX() { return x == 0              ? null : new Coordinate4D(maze, w, x - 1, y, z); };
        public Coordinate4D plusX()  { return x == maze.xSize - 1 ? null : new Coordinate4D(maze, w, x + 1, y, z); };
        public Coordinate4D minusY() { return y == 0              ? null : new Coordinate4D(maze, w, x, y - 1, z); };
        public Coordinate4D plusY()  { return y == maze.ySize - 1 ? null : new Coordinate4D(maze, w, x, y + 1, z); };
        public Coordinate4D minusZ() { return z == 0              ? null : new Coordinate4D(maze, w, x, y, z - 1); };
        public Coordinate4D plusZ()  { return z == maze.zSize - 1 ? null : new Coordinate4D(maze, w, x, y, z + 1); };
        public TesseractMaze getMaze() { return maze; }
    }

    public static final class TesseractMaze {
        private final int wSize, xSize, ySize, zSize;
        private final Map<Coordinate4D, Node> nodes;
        private final Node start;

        public TesseractMaze(int w, int x, int y, int z) {
            this.wSize = w;
            this.xSize = x;
            this.ySize = y;
            this.zSize = z;
            nodes = new HashMap<>(w * x * y * z);
            fill();
            this.start = chooseRandomNode();
            growMaze();
        }

        private void fill() {
            for (int a = 0; a < wSize; a++) {
                for (int b = 0; b < xSize; b++) {
                    for (int c = 0; c < ySize; c++) {
                        for (int d = 0; d < zSize; d++) {
                            Coordinate4D coord = new Coordinate4D(this, a, b, c, d);
                            nodes.put(coord, new Node(coord));
                        }
                    }
                }
            }
        }

        public Node nodeAt(Coordinate4D coord) {
            if (coord == null) return null;
            return nodes.get(coord);
        }

        private Node chooseRandomNode() {
            int n = (int) (Math.random() * wSize * xSize * ySize * zSize);
            return new ArrayList<>(nodes.values()).get(n);
        }

        private void growMaze() {
            List<Node> frontier = new ArrayList<>(wSize * xSize * ySize * zSize);
            frontier.add(start);
            start.linked = true;
            while (!frontier.isEmpty()) {
                Collections.shuffle(frontier);
                Node n = frontier.get(0);
                Node next = n.linkRandomUnlinkedNeighbour();
                if (next != null) {
                    frontier.add(next);
                } else {
                    frontier.remove(0);
                }
            }
        }

        public BufferedImage draw() {
            int cellWidth = 16;
            int cellHeight = 16;
            int boardWidth = cellWidth * (xSize + 1);
            int boardHeight = cellHeight * (ySize + 1);
            int arrowSize = 3;
            int margin = 2;
            Color red = Color.RED;
            Color blue = Color.BLUE;
            Color yellow = new Color(128, 128, 0);
            Color green = new Color(0, 128, 0);
            BufferedImage im = new BufferedImage(wSize * boardWidth + cellWidth - 1, zSize * boardHeight + cellHeight - 1, BufferedImage.TYPE_INT_ARGB);
            Graphics2D g = im.createGraphics();
            for (int w = 0; w < wSize; w++) {
                for (int z = 0; z < zSize; z++) {
                    for (int x = 0; x < xSize; x++) {
                        for (int y = 0; y < ySize; y++) {
                            Coordinate4D c = new Coordinate4D(this, w, x, y, z);
                            Node n = nodeAt(c);
                            int x1 = cellWidth * x + boardWidth * w + cellWidth - 1;
                            int y1 = cellHeight * y + boardHeight * z + cellHeight - 1;
                            int x2 = x1 + cellWidth;
                            int y2 = y1 + cellHeight;
                            int x3 = (x1 + x2) / 2;
                            int y3 = (y1 + y2) / 2;
                            g.setColor(Color.BLACK);
                            if (!n.isLinkedTo(n.minusY())) g.drawLine(x1, y1, x2, y1);
                            if (!n.isLinkedTo(n.plusY()))  g.drawLine(x1, y2, x2, y2);
                            if (!n.isLinkedTo(n.minusX())) g.drawLine(x1, y1, x1, y2);
                            if (!n.isLinkedTo(n.plusX()))  g.drawLine(x2, y1, x2, y2);
                            if (n.isLinkedTo(n.minusW())) { // Board left, left arrow.
                                g.setColor(red);
                                for (int i = 0; i < arrowSize; i++) {
                                    g.drawLine(x1 + margin + i, y3 - i, x1 + margin + i, y3 + i);
                                }
                            }
                            if (n.isLinkedTo(n.plusW())) { // Board right, right arrow.
                                g.setColor(green);
                                for (int i = 0; i < arrowSize; i++) {
                                    g.drawLine(x2 - margin - i, y3 - i, x2 - margin - i, y3 + i);
                                }
                            }
                            if (n.isLinkedTo(n.minusZ())) { // Board up, up arrow.
                                g.setColor(blue);
                                for (int i = 0; i < arrowSize; i++) {
                                    g.drawLine(x3 - i, y1 + margin + i, x3 + i, y1 + margin + i);
                                }
                            }
                            if (n.isLinkedTo(n.plusZ())) { // Board down, down arrow.
                                g.setColor(yellow);
                                for (int i = 0; i < arrowSize; i++) {
                                    g.drawLine(x3 - i, y2 - margin - i, x3 + i, y2 - margin - i);
                                }
                            }
                        }
                    }
                }
            }
            return im;
        }
    }

    public static final class Node {
        private final Coordinate4D coord;
        private final List<Node> linkedNeighbours;
        private List<Node> neighbours;
        private boolean linked;

        public Node(Coordinate4D coord) {
            Objects.requireNonNull(coord);
            this.coord = coord;
            linkedNeighbours = new ArrayList<>(8);
        }

        public Node linkRandomUnlinkedNeighbour() {
            List<Node> list = new ArrayList<>(getNeighbours());
            list.removeIf(n -> n.linked);
            if (list.isEmpty()) return null;
            Collections.shuffle(list);
            Node next = list.get(0);
            next.getNeighbours();
            linkedNeighbours.add(next);
            next.linkedNeighbours.add(this);
            next.linked = true;
            return next;
        }

        @SuppressWarnings("ReturnOfCollectionOrArrayField")
        public List<Node> getNeighbours() {
            if (neighbours == null) {
                List<Node> nodes = new ArrayList<>(Arrays.asList(minusW(), plusW(), minusX(), plusX(), minusY(), plusY(), minusZ(), plusZ()));
                nodes.removeIf(x -> x == null);
                neighbours = Collections.unmodifiableList(nodes);
            }
            return neighbours;
        }

        public boolean isDeadEnd() {
            return linkedNeighbours.size() == 1;
        }

        public boolean isBranch() {
            return linkedNeighbours.size() > 2;
        }

        public boolean isLinkedTo(Node node) {
            return linkedNeighbours.contains(node);
        }

        public TesseractMaze getMaze() { return coord.getMaze(); }
        public Coordinate4D getCoord() { return coord; }
        public Node minusW() { return getMaze().nodeAt(coord.minusW()); };
        public Node plusW()  { return getMaze().nodeAt(coord.plusW());  };
        public Node minusX() { return getMaze().nodeAt(coord.minusX()); };
        public Node plusX()  { return getMaze().nodeAt(coord.plusX());  };
        public Node minusY() { return getMaze().nodeAt(coord.minusY()); };
        public Node plusY()  { return getMaze().nodeAt(coord.plusY());  };
        public Node minusZ() { return getMaze().nodeAt(coord.minusZ()); };
        public Node plusZ()  { return getMaze().nodeAt(coord.plusZ());  };
    }
}

^{I am sorry that this site has no syntax-coloring.}

There are hundreds or thousands of dead-end and branching points. Much more than just 25 and 8 required by the OP.

For each two locations there is exactly one path to each other location. There are no cycles in the graph and it is connected. The program ensures that (growMaze method).

There is no defined starting or end point. Just randomly get any two points and try to find a path. As you see, manually finding a path here should be hard, since there is ten thousand positions in this maze and looking around the $w$ and $z$ dimensions to find a useful path is harder for human eyes than it is in the $x$ and $y$ dimensions.

You may use the program to randomly generate other mazes. Changing its size is easy too: They are those four tens in the start of the main method. In the main method you may change to which file the generated maze is saved. To show that, here it is a much smaller and simpler $4 \times 5 \times 3 \times 2$ maze generated by the program:

By the way, by setting $w$ to 1 and $z$ to 1, you may use it to generate 2D mazes. If you set only one of them to 1, it will be a 3D maze.

Answer 2

Now that this has been reopened I want to post the "solution" I had for this in the night before Victor's answer. Victor has beaten me to it, and Warspyking has modified the victory conditions since, so it is no longer a valid answer. I still wanted to post this for commenting (and verification/disproving.)

The answer works for n-dimensional mazes and it is also a algorithm not a specific maze. I do not post code here, but the algorithm concept.

---

My solution is based on the idea that each pixel/voxel/n-dim-element ( called voxel from now on) can either be a path (0) or a wall (1). This is different from what Victor made, but it can be turned into each other rather easily. (Just convert walls&openings into additional voxels or the other way around.)

• The data dimensions sizes are called n,m,k,l...
• Indexing starts with 0 for the first voxel

Initialize data:

• Create the maze-data as Boolean array of needed dimensionality

• Initialize all voxels as 0 (empty)

• Create a list for voxel-indices of walls (empty)

• Set every voxel with at least one even index to 1 (wall)

• Store the wall-voxel index in the list.

• From now on, whenever a wall is removed:

  • remove the according index from the list
  • set the according Boolean to 0 (empty)

Define start & end position:

Essentially set the two opposing "corners" to be start and end.

• Set the voxel of index (0,0,...) to be the starting location
• Set the voxel of index (n,m,...) to be the goal destination
• If the destination voxel is a wall, remove the wall. (All dimensions are even-sized)

Create the maze:

The current maze is a grid with isolated empty spaces.

• Label all empty spaces with a unique label.

Now go iteratively (WHILE-loop):

• Randomly choose a wall from the index list.
• Remove the index form the list (never test a wall twice)

Test: Will removing this wall merge two empty spaces of different label? NO: next iteration. ELSE:

• Remove wall

• Of all involved labels choose the one with lowest value

• Set all voxels having involved labels to this chosen value (=merge empty spaces)

• next iteration

Stop iteration when no indices are in the list.

Without proofing it, I think this algorithm will give you:

- a non-looping maze from start to end 

- maximize the size of the maze within the volume

- The identical algorithm could be used for arbitrary amount of dimensions

Originally I was intending to code this algorithm and then think of a nice way of displaying the 4D case, but Victor has done a great job of that already, so I'll leave it with this.