# Optimal Dodecahedron Construction

The dodecahedron origami on Mathigon has 12 units, each having two flaps and two pockets, so the five sides of each face is in the following order:

``Flap - Pocket - Pocket - Flap - Nothing``

Our goal is to find a connection plan ensuring that the model is stable, and has no visible gaps.

## Representation

First we need to number the units. Any numbering scheme could work, I chose the following:

1. Fix the bottom unit (it will be Unit #1), and look at the dodecahedron from the top.

2. Number those connecting to it as Units #2-#6, in a clockwise order starting from the one connecting to the `Nothing` side of #1.

3. In the next layer, number the units as #7-#11, in a clockwise order starting from the one over the two `Pockets` of #1.

4. Number the top unit as #12.

We also need to define a default orientation:

1. The orientation of Unit #1 is fixed.

2. The first layer is oriented by default such that the `Nothing` side is at the bottom.

3. The second layer is oriented by default such that the `Nothing` side is at the top.

4. The top unit is oriented by default such that the `Nothing` side is over the two `Pockets` of #1.

This is illustrated in this image:

The numbers are rotated so they look right when the `Nothing` side is at the bottom.

We can describe the connections between the units in the form

``connect(Unit1, Unit2, Side1, Side).``

meaning that in default orientation `Side1` of `Unit1` would be connected to `Side2` of `Unit2`, so for example

``connect(2,3,1,4).``

## Simple definitions

A side can be categorized in the following way:

``````flap(1).
flap(4).
pocket(2).
pocket(3).
nothing(5).``````

We can say that a connection has strong support, when one unit has a flap there, and the other a pocket. In contrast, the support is weak, if one unit has a flap, but the other is not a pocket:

``````support_type(A, B, strong) :- flap(A), pocket(B).
support_type(A, B, strong) :- flap(B), pocket(A).
support_type(A, B, weak) :- flap(A), \+ pocket(B).
support_type(A, B, weak) :- flap(B), \+ pocket(A).``````

We also say that a connection is invalid if both units have a flap there:

``invalid(A, B) :- flap(A), flap(B).``

## First attempt

A natural idea is that we want no two adjacent sides without strong support. A “solution” will be a list of rotations for each unit, where each rotation is a number between 0 and 4, representing clockwise rotations (seen from the outside) w.r.t. the default orientation:

``rotate(I, R, I1) :- I1 is (I + 4 - R) mod 5 + 1.``

So e.g. side 4 (a `Flap`) becomes side 3 (a `Pocket`) if we make 1 CW rotation (and not 5 [`Nothing`], which would be a CCW rotation).

Our main rule is as follows:

``````dodecahedron(Rotations) :-
findall(c(U1,U2,S1,S2), connect(U1,U2,S1,S2), Connections),
length(Rotations, 12),
Rotations = [0|_],
maplist(between(0, 4), Rotations),
build(Connections, Rotations, [], Supports),
check_supports(12, Supports).``````

First all connections are collected in `Connections`. There will be 12 rotations, with the first one fixed to 0, and all between 0 and 4. Then we try to build the model - this step will also check the validity of the connections, and find out which sides of the units are supported -, and finally check if there is enough support.

In the `build` rule we go through all connections one by one:

``````build([], _, Supports, Supports).
build([c(U1,U2,S1,S2)|Connections], Rotations, Supports, Supports1) :-
nth1(U1, Rotations, R1),
nth1(U2, Rotations, R2),
rotate(S1, R1, SR1),
rotate(S2, R2, SR2),
\+ invalid(SR1, SR2),
( support_type(SR1, SR2, T) ->
Supports0 = [s(U1,SR1,T),s(U2,SR2,T)|Supports]
; Supports0 = Supports
),
build(Connections, Rotations, Supports0, Supports1).``````

Here `SR1` and `SR2` are the rotated versions of the connecting sides. We check for validity, and also for support. If they are supported, the support type is saved for both units as `s(Unit,Side,Type)`.

Finally, we need to check the supports. We go through all units from #12 to #1:

``````check_supports(0, _).
check_supports(I, Supports) :-
I1 is I - 1,
forall(between(1, 5, J),
( member(s(I,J,strong), Supports)
; L is (J + 3) mod 5 + 1,
R is J mod 5 + 1,
member(s(I,L,strong), Supports),
member(s(I,R,strong), Supports)
)),
check_supports(I1, Supports).``````

In other words, each side (1 to 5) or both of its neighbors should be strongly supported.

Testing the above, we get

``````?- dodecahedron(R).
R = [0, 0, 2, 1, 4, 3, 0, 3, 4, 1, 2, 0]``````

Note that in this version all `Nothing`s are connected to other `Nothing`s. Turns out that this is needed to satisfy the “strong support” requirement above. This is unfortunate, because these connections tend to sink into the model interior.

## Second attempt

So let us forbid `Nothing`-`Nothing` connections:

``````invalid(A, B) :- flap(A), flap(B).
invalid(A, B) :- nothing(A), nothing(B). % New rule``````

This would be too restrictive, so we need to loosen up the “strong support” rule, by allowing weak supports, as well. This can be achieved by changing `check_supports/2`:

``````check_supports(0, _).
check_supports(I, Supports) :-
I1 is I - 1,
forall(between(1, 5, J),
( member(s(I,J,_), Supports)
; L is (J + 3) mod 5 + 1,
R is J mod 5 + 1,
member(s(I,L,_), Supports),
member(s(I,R,_), Supports)
)),
check_supports(I1, Supports).``````

This is the same as before, but allows any type of support.

``````?- dodecahedron(R).
R = [0, 1, 0, 1, 0, 2, 0, 1, 1, 0, 1, 4]``````

This one is better in terms of gaps, but it is much less stable.

## Third attempt

Let us make the support rule a bit stronger, by also requiring that there should be at least 3 strong supports for each unit:

``````check_supports(0, _).
check_supports(I, Supports) :-
I1 is I - 1,
forall(between(1, 5, J),
( member(s(I,J,_), Supports)
; L is (J + 3) mod 5 + 1,
R is J mod 5 + 1,
member(s(I,L,_), Supports),
member(s(I,R,_), Supports)
)),
findall(J, member(s(I,J,strong), Supports), L),
length(L, N),
N >= 3,
check_supports(I1, Supports).``````

This can be solved:

``````?- dodecahedron(R).
R = [0, 1, 0, 1, 1, 2, 4, 0, 4, 4, 3, 0]``````

This seems to be quite stable, but has no `Nothing`-`Nothing` connections.

## Coloring

Another interesting question is how to choose the colors of the units. We don’t want to have two connected units of the same color, but also want some kind of uniformity.

It is easy to see that 3 colors do not suffice, since choosing color 1 for Unit #1, the adjacent units need to be colors 2, 3, 2, 3, 2 … but then there will be two 2s next to each other!

It is also trivial to create a nice symmetric coloring with 6 colors, where each unit is connected to all other colors:

``[1, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 1]``

But what about 4 colors? Let’s ask the computer!

``````coloring(Colors) :-
length(Colors, 12),
Colors = [1|_],
maplist(between(1, 4), Colors),
forall(connect(I,J,_,_),
( nth1(I, Colors, Ci),
nth1(J, Colors, Cj),
Ci \= Cj )).``````

We fix the color of Unit #1 as 1, the others can be anything between 1 and 4. We also require that no connected units should have the same color.

``````?- coloring(C).
C = [1, 2, 3, 2, 3, 4, 4, 1, 3, 4, 1, 2]``````

Note that all colors appear 3 times, which is quite nice.

## The whole program

``````coloring(Colors) :-
length(Colors, 12),
Colors = [1|_],
maplist(between(1, 4), Colors),
forall(connect(I,J,_,_),
( nth1(I, Colors, Ci),
nth1(J, Colors, Cj),
Ci \= Cj )).

dodecahedron(Rotations) :-
findall(c(U1,U2,S1,S2), connect(U1,U2,S1,S2), Connections),
length(Rotations, 12),
Rotations = [0|_],
maplist(between(0, 4), Rotations),
build(Connections, Rotations, [], Supports),
check_supports(12, Supports).

build([], _, Supports, Supports).
build([c(U1,U2,S1,S2)|Connections], Rotations, Supports, Supports1) :-
nth1(U1, Rotations, R1),
nth1(U2, Rotations, R2),
rotate(S1, R1, SR1),
rotate(S2, R2, SR2),
\+ invalid(SR1, SR2),
( support_type(SR1, SR2, T) ->
Supports0 = [s(U1,SR1,T),s(U2,SR2,T)|Supports]
; Supports0 = Supports
),
build(Connections, Rotations, Supports0, Supports1).

rotate(I, R, I1) :- I1 is (I + 4 - R) mod 5 + 1.

check_supports(0, _).
check_supports(I, Supports) :-
I1 is I - 1,
forall(between(1, 5, J),
( member(s(I,J,_), Supports)
; L is (J + 3) mod 5 + 1,
R is J mod 5 + 1,
member(s(I,L,_), Supports),
member(s(I,R,_), Supports)
)),
findall(J, member(s(I,J,strong), Supports), L),
length(L, N),
N >= 3,
check_supports(I1, Supports).

flap(1).
flap(4).
pocket(2).
pocket(3).
nothing(5).

support_type(A, B, strong) :- flap(A), pocket(B).
support_type(A, B, strong) :- flap(B), pocket(A).
support_type(A, B, weak) :- flap(A), \+ pocket(B).
support_type(A, B, weak) :- flap(B), \+ pocket(A).

invalid(A, B) :- flap(A), flap(B).
invalid(A, B) :- nothing(A), nothing(B).

connect(1,2,5,5).
connect(1,3,4,5).
connect(1,4,3,5).
connect(1,5,2,5).
connect(1,6,1,5).
connect(2,3,1,4).
connect(3,4,1,4).
connect(4,5,1,4).
connect(5,6,1,4).
connect(6,2,1,4).
connect(2,9,3,3).
connect(2,10,2,2).
connect(3,10,3,3).
connect(3,11,2,2).
connect(4,11,3,3).
connect(4,7,2,2).
connect(5,7,3,3).
connect(5,8,2,2).
connect(6,8,3,3).
connect(6,9,2,2).
connect(7,8,4,1).
connect(8,9,4,1).
connect(9,10,4,1).
connect(10,11,4,1).
connect(11,7,4,1).
connect(7,12,5,5).
connect(8,12,5,1).
connect(9,12,5,2).
connect(10,12,5,3).
connect(11,12,5,4).``````