Overview:

Problem summary:

We must mark each cell of the 20×20 grid as either inside or outside.

To help us the grid contains some special cells with the following rules:

Arrow cells:

Arrow cells are per definition outside.

Arrow cells can have one or more arrows, these arrow point in cardinal directions.

Arrow cells force the first inside cells in the pointing-directions to be equidistant from the arrow cell, and no closer inside cell can exist in any direction.

Numbered cells:

Numbered cells are per definition inside.

Numbered cells contain a number, this number specifies the total count of inside cells in the 3×3 neighborhood centered around the cell itself (so a maximum of 9 = itself + 8 neighbors).

Global constraints:

Every inside cell must be connected to every other inside cell.

Every outside cell must be connected to the edge of the grid (so it can be “cut away”).

Definitions:

• We define a cell to be inside if this cell is part of the final box

• We define a cell to be outside if this cell is not part of the final box

• We use “the shape“ or “shape” to refer to the 2 dimensional shape to be folded into a box

• We use “arrow distance“ to refer to the distance between an arrow cell and its corresponding closest inside cells

Solving:

You could solve the puzzle using two different methods.

The first being purely visual using excalidraw or writing a custom tool using something like pygame.

The second being solving the puzzle algorithmically, the simplest approach here is trying to convert the constraints of the puzzle into boolean expressions and using a sat-solver like Z3 to satisfy these constraints.

Z3-Powered solver

So how does one convert the different puzzle constraints?

We start by modelling the grid as an array of integers (“g_{x}_{y}”) with the constraint of each int being >= 0 and <= 1.

I used integers rather than booleans because summing a 3×3 neighborhood becomes trivial with integers.

The neighborhood-constraint:

As specified the neighborhood constraint is rather trivial.

# Constraints for the neighbor counts
for (r,c), val in numbers.items(): # Numbers is an array of positions of number-cells
    neighs = []
    for dr in (-1,0,1):
        for dc in (-1,0,1):
            rr, cc = r+dr, c+dc
            if is_in_grid(rr, cc):
                neighs.append(grid[rr][cc])
    s.add(Sum(neighs) == val) # s is the z3 solver

This code just loops through all numbers and sets the constraint that the amount of inside cells in the 3×3 area must equal the number value.

The arrow-constraint:

The arrow constraint was more tricky to implement.

The basic idea is to generate a distance expression in each direction with nested if conditions.

# Arrow constraints
# Helper to get distance expression by building a ray of Ifs
# It walks backwards from the edge to the cell, building an If chain
# the chain reads if the current cell is inside, return distance, else (if chain)
def get_dist_expr(row, col, dx, dy):

    # Build a list of cells along the specified direction
    cells = []
    curr_row, curr_col = row + dx, col + dy
    while is_in_grid(curr_row, curr_col):
        cells.append((curr_row, curr_col))
        curr_row += dx
        curr_col += dy

    # Start with an arbitrary large distance
    if_chain = 999

    # Iterate backwards to build the If chain, otherwise the last element would have priority
    for i in range(len(cells)-1, -1, -1):
        rr, cc = cells[i]
        dist = i + 1
        # If the cell is inside, return distance, else continue the chain
        if_chain = If(grid[rr][cc] == 1, dist, if_chain)
    return if_chain

dir_map = {"NORTH": (-1, 0), "SOUTH": (1, 0), "EAST": (0, 1), "WEST": (0, -1)}

for (r,c), dirs in arrows.items():
    # Define the target distance of the arrow
    target = Int(f"arrow_target_{r}_{c}")

    s.add(target > 0, target < GRID_SIZE)

    for d_name, (dx, dy) in dir_map.items():
        dist_expr = get_dist_expr(r, c, dx, dy)

        # If the arrow points in this direction, distance must equal target
        # Else distance must be greater than target
        if d_name in dirs:
            s.add(dist_expr == target)
        else:
            s.add(dist_expr > target)

The inside-connectivity-constraint:

This is the constraint that took by far the most time to implement, since I didn’t really know how to describe the idea of connectivity in expressions.

The approach ended up being:

1. Selected one cell that is guaranteed to be inside (I simply used the first number cell), we will call it root

2. Create a new distance grid and set the distance of the root cell to 0

3. Now if a cell is connected it must have a neighbor with a distance of its own distance - 1

# Constraint to force all inside cells to be connected
# Select the first number cell as root (since it is an inside cell per definition), so all inside cells must connect to it
root_r, root_c = list(numbers.keys())[0]

# Idea:
# We check connectivity by essentially doing a flood fill with distance values
# Then if a cell is inside it must have a cardinal neighbor with dist = d-1 otherwise there does not exist a path to the root

# Create a new distance grid for connectivity
d_in = [[Int(f"d_in_{r}_{c}") for c in range(COLS)] for r in range(ROWS)]

for r in range(ROWS):
    for c in range(COLS):
        # If outside, dist is -1
        s.add(Implies(grid[r][c] == 0, d_in[r][c] == -1))

        # If the cell is the root cell, set the distance to 0
        if (r,c) == (root_r, root_c):
            s.add(d_in[r][c] == 0)
            continue

        # Since the cell is not the root cell, its distance must be > 0 if inside
        s.add(Implies(grid[r][c] == 1, d_in[r][c] > 0))

        # Get the cardinal neighbors
        neighs = []
        for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
            rr, cc = r+dr, c+dc
            if is_in_grid(rr, cc):
                neighs.append(d_in[rr][cc])

        # Since the cell is inside, there must exist a neighbor with dist = d-1
        s.add(Implies(grid[r][c] == 1, Or([n == d_in[r][c] - 1 for n in neighs])))

The outside-connectivity-constraint:

The approach of outside-connectivity is similar to the process for inside connectivity. The only difference being is we set a cell to have a distance of 0 if it is on the edge of the grid.

# Connected to edge constraint
# Create a new distance grid for outside connectivity
d_out = [[Int(f"d_out_{r}_{c}") for c in range(COLS)] for r in range(ROWS)]

# Idea:
# If a cell is on the outside and on the boundary, dist = 0
# If a cell is outside and not on the boundary, there must exist a neighbor with dist = d-1

for r in range(ROWS):
    for c in range(COLS):
        s.add(Implies(grid[r][c] == 1, d_out[r][c] == -1))
        s.add(Implies(grid[r][c] == 0, d_out[r][c] >= 0))

        is_boundary = (r == 0 or r == ROWS-1 or c == 0 or c == COLS-1)

        if is_boundary:
            s.add(Implies(grid[r][c] == 0, d_out[r][c] == 0))
            continue

        # If outside and not boundary, dist > 0
        s.add(Implies(grid[r][c] == 0, d_out[r][c] > 0))

        neighs = []
        for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
            rr, cc = r+dr, c+dc
            neighs.append(d_out[rr][cc])

        # If the cell is outside, then there must exist a neighbor with dist = d-1
        s.add(Implies(grid[r][c] == 0, Or([n == d_out[r][c] - 1 for n in neighs])))

The finished grid

After running the code there were 72 different solutions.

To produce a single “consensus” I combined these solutions cell-wise:

• If a cell was inside in all solutions → mark it as inside (green)

• If a cell was outside in all solutions → mark it as outside (white)

• Otherwise → mark it as unsure (grey)

This resulted in the following grid:

Folding

I experimented with automatic folding but ended up simply just folding a printed copy by hand.

This was surprisingly straightforward, because of the rather distinct edge geometry making only some folds possible. I marked the unsure cells to remind me that they don’t have to be included.

After a half an hour of fiddling around with scissors and tape, I managed to fold the shape into a box, adding together the numbers on each face and multiplying the sum gave me the following solution: 16414860

Code

Or view to full code here.