TAOCP 7.2.2.1 Exercise 143
Stopped thinking
Section 7.2.2.1: Dancing Links
Exercise 143. ▶ [M25] $[M25]$ The graph $simplex(n, a, b, c, 0, 0, 0)$ in the Stanford GraphBase is the truncated triangular grid consisting of all vertices $xyz$ such that $$x + y + z = n,\quad 0 \le x \le a,\quad 0 \le y \le b,\quad 0 \le z \le c.$$ Two vertices are adjacent if their coordinates all differ by at most 1. The boundary edges always define a convex polygon. For example, $simplex(7, 7, 5, 3, 0, 0, 0)$ is illustrated here.
a) What simplex graphs correspond to the three shapes in exercise 140?
b) The examples in (a) have 24 interior triangles, but $\mathit{simplex}(7,7,5,3,0,0,0)$ has 29. Can any other convex polygons be made from 24 triangles, connected edgewise?
c) Design an efficient algorithm that lists all possible convex polygons that can be formed from exactly $N$ triangles, given $N$. Hint: Every convex polygon in a triangular grid can be characterized by the six numbers in its boundary path $x_0x_1x_2x_3x_4x_5$, which moves $x_k$ steps in direction $(60k)°$ for $k = 0, 1, \ldots, 5$. For example, the boundary of $\mathit{simplex}(7,7,5,3,0,0,0)$ is 503412.
d) Can every convex polygon in a triangular grid be described by a simplex graph?
Verified: no
Solve time: 7m02s
Stopped thinking