Magic Labyrinth is a cool game suitable for young children where players must navigate a maze to reach a goal, with the complication that the walls of the maze are NOT apparent until you run into them, forcing you to return to your start position.^{1}

Up to 4 players start from the corners of a 6 by 6 board. For each round of the game, the objective is to be the first to reach a randomly selected goal tile – in the picture below, the goal has a sword icon, which refers to a tile near the red token.

The tokens can be moved moved non-diagonally to reach the goal tile. The trick is that underneath the board is a maze consisting of walls that the players can’t see, but which will become evident if they try to move their token across a wall. Each token has a magnet that holds up a metal ball, which will be dislodged by the walls.

Back in 2018, we visited some friends with young kids and played Magic Labyrinth with them. The instructions come with two example mazes – an easier one with 19 walls and a harder one with 24 walls.

With only two example mazes, I thought it’d be interesting to code a tool to generate additional mazes, and to make sure they were relatively fair, regardless of which corner you started in. At the time, I was taking an online Python course, so it gave me an excuse to practice coding in Python. I also analyzed how fair the default example maze was.

## Goal

- randomly generate board mazes
- analyze relative fairness, between each of the 4 corner starting positions

## Plan

- function parameters: what size board (x by y) and how many walls to place
- default board has 24 internal walls on a 6x6 board

- randomly place internal walls
- confirm that all squares are reachable (recursive connectivity search)
- if any squares not reachable, restart

- test each valid goal square
- all squares are potentially valid goal squares, except for the corner squares and the 2 tiles immediately adjacent
- so for a 6x6 board, there are a total of 24 possible goal squares
- for each corner starting position (4), determine the shortest path from each corner to each possible goal (recursive depth-first search)

- compare mean distance to all possible goals from each corner
- if the mean shortest paths are relatively similar, consider it a fair board layout

## Results

- to place 24 internal walls on a 6x6 board, it actually can take a lot of attempts to create a board with all positions reachable
- some boards are REALLY unfair to some corners

## Some examples of generated boards

**A pretty fair one:**

```
Generating 6 by 6 board with 24 walls
Required 514 attempts
_ _ _ _ _ _
| |_ | _|
|_ _ | _|
| _ |_ _|
|_| _ |_| |
| | _| _ _|
|_ _|_ _ _ _|
Average # of steps to goals from (0, 0) = 6.67
Average # of steps to goals from (0, 5) = 7.58
Average # of steps to goals from (5, 0) = 6.25
Average # of steps to goals from (5, 5) = 8.0
Maximum difference of average distances = 1.75
```

**Another very fair one:**

```
Generating 6 by 6 board with 24 walls
Required 717 attempts
_ _ _ _ _ _
|_ _ |_ _|
|_ _ _ |
| | |_ |_| |
| _| _ _|
| _| _|
|_|_|_ _|_ _|
Average # of steps to goal from (0, 0) = 8.0
Average # of steps to goal from (0, 5) = 7.17
Average # of steps to goal from (5, 0) = 6.5
Average # of steps to goal from (5, 5) = 6.92
Maximum difference of average distances = 1.5
```

**A pretty unfair one (stinks to start in the upper left hand corner; lower left hand corner is great):**

```
Generating 6 by 6 board with 24 walls
Required 86 attempts
_ _ _ _ _ _
|_ _ | |_ |
| | _| _|
| _ |_| | |
|_ |_|_ _|
| _| _ |
|_ _ _ _ _|_|
Average # of steps to goal from (0, 0) = 14.25
Average # of steps to goal from (0, 5) = 7.0
Average # of steps to goal from (5, 0) = 9.58
Average # of steps to goal from (5, 5) = 8.58
Maximum difference of average distances = 7.25
```

## Analysis of the default board (with 24 walls)

It turns out that the default board with 24 walls isn’t very fair. I manually generated the board that we played on. You can see that starting out in the bottom right hand corner on average takes 2 more steps to reach the goal.

```
_ _ _ _ _ _
| |_ |_ | |
| _| | |
|_|_ _|_|
|_ _| _ _|
| | _ | |
|_ _|_ _ _|_|
Average # of steps to goals from (0, 0) = 6.83
Average # of steps to goals from (0, 5) = 6.92
Average # of steps to goals from (5, 0) = 6.33
Average # of steps to goals from (5, 5) = 8.83
Maximum difference of average distances = 2.5
```

## How many walls can be placed on a 6 x 6 board?

It also turns out that for a 6x6 board, 24 is close to the maximum number of internal walls you can place and still reach all positions.

- in 100,000 attempts, trying to place 26 internal walls FAILED to generate a connected graph
- trying to place 25 walls can work, but it can take a lot of attempts.

Here’s a really fair 25 wall board. It’s pretty unusual to see such an ‘fair’ board.

```
Generating 6 by 6 board with 25 walls
Required 1777 attempts
_ _ _ _ _ _
| _ | _| |
| |_ _ |_ |
|_ _ _| _ |
| _ | |_|
| |_| |_ _ |
|_ _ _ _ _|_|
Average # of steps to goal from (0, 0) = 7.5
Average # of steps to goal from (0, 5) = 7.83
Average # of steps to goal from (5, 0) = 7.58
Average # of steps to goal from (5, 5) = 8.25
Maximum difference of average distances = 0.75
```

## Python code

Here’s the code used to generate and analyze the boards. I wrote this 6 years ago, and don’t really use Python, so I barely remember how it works…

```
class Square(object):
'''
Define object that represents a square on the board
'''
def __init__(self, name, neighbors):
self.name = name
self.neighbors = neighbors # array of names of reachable adjacent Nodes
def empty_board(num_x, num_y):
'''
Return empty board with all neighbors reachable
'''
= {} # key is tuple of x,y coordinates, contains a Node object
board for x in range(num_x):
for y in range(num_y):
= (x,y)
name = []
neighbors if x != 0: # Add West, unless on left column
- 1, y))
neighbors.append((x if x != num_x - 1: # Add East, unless on right column
+ 1, y))
neighbors.append((x if y != 0: # Add North, unless on top row
- 1))
neighbors.append((x, y if y != num_y - 1: # Add South, unless on bottom row
+ 1))
neighbors.append((x, y = Square(name, neighbors) # create new node with associated neighbors
board[name] return(board)
def check_connectivity(graph, connected, name):
'''
Recursive function to collect set of connected nodes
- 'connected' is recursively extended to include set of node names that are connected
'''
# add current node to set
connected.add(name) for neighbor in graph[name].neighbors: # iterate over current node's neighbors
if neighbor not in connected: # avoid infinite recursion, already visited
# visit the neighbor
check_connectivity(graph, connected, neighbor)
def all_connected(board, num_x, num_y):
'''
Check connectivity
- uses check_connectivity()
- returns True if all connected
'''
= set() # initialize empty set of reached node names
connected 0,0)) # start from node (0,0)
check_connectivity(board, connected, (return(len(connected) == (num_x * num_y))
def add_wall(board, square1, square2):
'''
Add a wall (i.e., remove connections) in 'board' between square1 and square2, bidirectionally
- alternatively, if don't want to 'try / except': if square2 in board[square1].neighbors
'''
= True
success try:
board[square1].neighbors.remove(square2)except: # print(square1, 'is not connected to', square2)
= False
success try:
board[square2].neighbors.remove(square1)except: # print(square2, 'is not connected to', square1)
= False
success return success
def DFS(graph, start, end, path, shortest):
'''
Depth-first search, accessed via shortestPath function
- returns entire path, or None if no path found
- len(path) - 1 would equal number of steps needed
'''
= path + [start]
path if start == end:
return path
for node in graph[start].neighbors:
if node not in path: # avoid cycles
if shortest == None or len(path) < len(shortest):
= DFS(graph, node, end, path, shortest)
newPath if newPath != None:
= newPath
shortest return shortest
def shortestPath(graph, start, end):
'''
Uses DFS() to return shortest path (or None)
'''
return DFS(graph, start, end, [], None)
def print_board(board, num_x, num_y):
'''
Prints out a board (needs a monospace font)
- for each row (y), prints the NS walls and the lower EW walls
- [ ] should group board / num_x / num_y all into an object
'''
# First generate the wall at the north edge of the board
= ' '
s for x in range(num_x):
+= '_ '
s print(s)
# Then generate each row, including the southern walls of each square
for y in range(num_y):
= '|'
s for x in range(num_x):
if (x, y + 1) in board[(x, y)].neighbors:
+= ' '
s else:
+= '_'
s if (x + 1, y) in board[(x, y)].neighbors:
+= ' '
s else:
+= '|'
s print(s)
```

```
def generate_board(num_wall = 24, num_x = 6, num_y = 6, max_attempts = 10000):
# num_wall = 24 # number of internal walls to place; 26 on a 6x6 seems near impossible
# num_x = 6 # width of board
# num_y = 6 # height of board
# max_attempts = 10000
from random import randint
= 0
attempts while attempts < max_attempts:
+= 1
attempts = empty_board(num_x, num_y)
board for i in range(num_wall):
while True:
= randint(0, num_x - 1)
x = randint(0, num_y - 1)
y = (x, y)
square1
= randint(0, 3)
direction if direction == 0:
= (x - 1, y)
square2 elif direction == 1:
= (x + 1, y)
square2 elif direction == 2:
= (x, y - 1)
square2 elif direction == 3:
= (x, y + 1)
square2 else:
print('*** ERROR ***')
if add_wall(board, square1, square2) == True: # successfully added wall
break
if all_connected(board, num_x, num_y) == True:
return(board, num_wall, num_x, num_y, attempts)
return(None, num_wall, num_x, num_y, attempts)
```

Setting up parameters and running the code:

```
= generate_board(num_wall = 24, num_x = 6, num_y = 6, max_attempts = 10000)
(board, num_wall, num_x, num_y, attempts) = [(0, 0), (0, num_y - 1), (num_x - 1, 0), (num_x -1, num_y - 1)]
corners = corners + [ (0,1), (1,0), (0, num_y - 2), (1, num_y - 1), (0, num_x - 2), (1, num_x - 1), (num_x - 1, num_y - 2), (num_x - 2, num_y - 1) ]
invalid_goals
print('Generating', num_x, 'by', num_y, 'board with', num_wall, 'walls')
if board is not None:
print('Required', attempts, 'attempts')
6, 6)
print_board(board, print()
# Set as goal every possible square EXCEPT those adjacent to corners
# - determine mean shortest distances from each corner
= {}
total_distance for corner in corners:
= 0
total_distance[corner]
for x in range(num_x):
for y in range(num_y):
= (x,y)
goal if goal not in invalid_goals:
for start in corners:
+= len(shortestPath(board, start, goal)) - 1
total_distance[start]
for start in corners:
print('Average # of steps to goal from', start, '=', round(total_distance[start] / (num_x * num_y - 12), 2))
= [round(total_distance[start] / (num_x * num_y - 12), 2) for start in corners]
ave_distances print('Maximum difference of average distances =', max(ave_distances) - min(ave_distances))
else:
print('Failed to generate board in', attempts, 'attempts')
```

Quick hack to manually create and analyze the 24-wall default board:

```
# Test default board
print('Default board')
= 6
num_x = 6
num_y = [(0, 0), (0, num_y - 1), (num_x - 1, 0), (num_x -1, num_y - 1)]
corners = corners + [ (0,1), (1,0), (0, num_y - 2), (1, num_y - 1), (0, num_x - 2), (1, num_x - 1), (num_x - 1, num_y - 2), (num_x - 2, num_y - 1) ]
invalid_goals
= empty_board(num_x, num_y)
board
0,0), (1,0))
add_wall(board, (2,0), (3,0))
add_wall(board, (4,0), (5,0))
add_wall(board, (2,1), (3,1))
add_wall(board, (3,1), (4,1))
add_wall(board, (0,2), (1,2))
add_wall(board, (4,2), (5,2))
add_wall(board, (2,3), (3,3))
add_wall(board, (0,4), (1,4))
add_wall(board, (3,4), (4,4))
add_wall(board, (1,5), (2,5))
add_wall(board, (4,5), (5,5))
add_wall(board, (
0,2), (0,3))
add_wall(board, (0,3), (0,4))
add_wall(board, (1,0), (1,1))
add_wall(board, (1,2), (1,3))
add_wall(board, (2,1), (2,2))
add_wall(board, (2,3), (2,4))
add_wall(board, (2,4), (2,5))
add_wall(board, (3,0), (3,1))
add_wall(board, (4,2), (4,3))
add_wall(board, (4,3), (4,4))
add_wall(board, (5,2), (5,3))
add_wall(board, (5,3), (5,4))
add_wall(board, (
6, 6)
print_board(board, print()
# Set as goal every possible square EXCEPT those adjacent to corners
# - determine mean shortest distances from each corner
= {}
total_distance for corner in corners:
= 0
total_distance[corner]
for x in range(num_x):
for y in range(num_y):
= (x,y)
goal if goal not in invalid_goals:
for start in corners:
+= len(shortestPath(board, start, goal)) - 1
total_distance[start]
for start in corners:
print('Average # of steps to goals from', start, '=', round(total_distance[start] / (num_x * num_y - 12), 2))
= [round(total_distance[start] / (num_x * num_y - 12), 2) for start in corners]
ave_distances print('Maximum difference of average distances =', max(ave_distances) - min(ave_distances))
```

## Footnotes

Most images are from the Amazon product page↩︎

From the Magic Labyrinth game instructions↩︎