# Optimal Dodecahedron Construction
The dodecahedron origami on [Mathigon](https://mathigon.org/origami/dodecahedron)
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.
1. Number those connecting to it as Units #2-#6, in a clockwise order
starting from the one connecting to the `Nothing` side of #1.
1. In the next layer, number the units as #7-#11, in a clockwise order
starting from the one over the two `Pockets` of #1.
1. Number the top unit as #12.
We also need to define a default orientation:
1. The orientation of Unit #1 is fixed.
1. The first layer is oriented by default such that the `Nothing` side
is at the bottom.
1. The second layer is oriented by default such that the `Nothing` side
is at the top.
1. 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:
![Numbering and orientation](dodecahedron.jpg)
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
```prolog
connect(Unit1, Unit2, Side1, Side).
```
meaning that in default orientation `Side1` of `Unit1` would be
connected to `Side2` of `Unit2`, so for example
```prolog
connect(2,3,1,4).
```
## Simple definitions
A side can be categorized in the following way:
```prolog
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:
```prolog
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:
```prolog
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:
```prolog
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:
```prolog
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:
```prolog
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:
```prolog
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:
```prolog
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`:
```prolog
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 *2*s 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!
```prolog
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
```prolog
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).
```