Abdul Rahman Sibahi | The Hanging Gardens Problem

This is an interesting puzzle inspired by Christian Freeling's tile set The China Cube. As it really has nothing to do with China, I call it the Hanging Gardens Problem . Imagine each cube as a section of the Garden, and connections to other cubes are paths and stairways.1

Here is a nice drawing showing the full set of 64 Cubes, from Freeling's site.

Problem Formulation

There are 64 cubes.

Each cube is unique.

Each cube has a specific number of Red and Blue faces.

Cubes do not rotate or change orientation in anyway.

Direction of the faces is specific: North, East, South, West, Top, Bottom.

It follows from these that there is

One cube with all Red faces (the Red cube, bottom Cube in the earlier drawing.)

One cube with all Blue faces (the Blue cube, top Cube in the earlier drawing)

Six cubes with one Red face.

Six cubes with one Blue face.

... etc.

All possible permutations of Red and Blue faces are represented (hence 64 cubes).

Here is the puzzle: Assemble the cubes so the Blue faces touch each other, and all the Red faces are exposed. 2

In other words, a Blue face must always face, touching, another Blue face. A Red face must not do that. However, a Red face might wave to another Red face from a distance (at least one cube far.)

There is most likely is a solution.

The solution does not have to be one big shape. It actually cannot, because of the Red Cube.

tl;dr I gave up on the problem due to time and memory constraints. However, while I was at it, I found solutions to two, equally interesting, sub problems, and nice graphics.

Wave Function Collapse

I asked around in a number of Discord servers on how to approach solving the problem programmatically, outside of 3-D printing the set and physically assembling it by hand. The Gorilla Sun Creative Coding server suggested that using the Wave Function Collapse algorithm might be the best fit for the problem, and suggested a very excellent YouTube video from the Coding Train implementing the algorithm in Javascript. It is a very good video that I suggest watching.

As explained at the start of the video, this is simply the Sudoku solving algorithm, generalized to creating random tile sets. Apparently, the Quantum Mechanics inspired name is simply for flavor and searchability.

So, how does one solve a Sudoku?

First, identify the connection rules and the tile set. (Which, in Sudoku, need no explaining.)

Second, Observation: mark each empty cell in the grid with the candidate tiles numbers that go in them.

Third, the Collapse in Wave Function Collapse: identify the cells with the fewest number of candidates. 1. Any cell with 1 candidate "collapses" into that candidate, and the number is inked in. 2. If there are not any cells with one candidate, pick one cell with the fewest number of candidates and pick a candidate at random, "collapsing" it.3

Fourth, Propagation: with the new state of things, update the candidates in each call. Here is where Sudoku people use X-wings and Swordfishes and what have you.

Repeat the Collapse, until the grid is full.

If there ever, after Propagation, a cell with zero candidates, this means an illegal state was reached. Either Backtrack to the last random choice, (and, well, choose another branch), or simply start the whole thing over.

This approach can work just fine for the Hanging Gardens. The Tile set and the connection rules are clearly defined. It is only a matter of putting it into code and .. running it. The problem most apparent to me, however, is that the search space is potentially huge. So, I first need to try this approach with a smaller problem set.

Square Gardens

Phrasing the problem in terms of Squares, and 2D connections, rather than Cubes, shrinks the problem space by an order of magnitude. Plus, there is a known solution given by Freeling!

Tiles and Air

First, I need to formulate the tiles. There are two kinds of Tiles. The first kind is the actually Squares. This is a finite set. The second kind, is an "Air" tile. This empty tile is infinitely available, and is automatically placed at the Propagation phase connected to every Red face. A Red face must connect to an Air tile, and a Blue face can never connect to one. An Air tile can connect from any side to any Air tile with no restriction.

I am still having fun with Odin, so I will try this solution in it first. Here are the starting types:

Side :: enum { North, East, South, West }<br>Tile :: distinct bit_set[Side]

Air :: distinct struct {}

Cell :: union { Air, Tile }<br>I am not too happy about this because while the data can neatly fit into one byte, Odin puts this in two. This looks cleaner and easier to understand than weird hacks, so I will stick to it for the time being. Odin's union is nice here, semantically, as it actually has three states: nil, Air and Tile, exactly as much as needed.

The Squares are only 16 (count them in the image above). It is possible to safely ignore the...