Using GIS to solve the puzzle
The solution is brute force. Beginning with an appropriate representation of the Star, we first constructed all possible connected figures that can be drawn. We needed to compute important properties of any possible figure: whether indeed it is connected, how many sides it has, and (for the final display) its relationship to other figures via symmetries of the star. Finally, we needed to display the solutions that were found.
Representation
The key to our approach lies in the Star's representation. We conceive it as a collection of twelve small triangles. The boundary of any subset of triangles constitutes a figure (possibly disconnected) that can be drawn. Conversely, any figure will circumscribe a set of these triangles. This sets up a one-to-one correspondence between subsets of the triangles and possible figures.
 |
Here's our Star. The
colors differentiate the little triangles. We needed to name them,
so they received numbers from 0 through 11, as shown. The sequence
corresponds to the order in which we created the stars; it would have
been nice to name them in a more systematic way. We figured that
out too late.
The GIS tools used to create the star included the ability to create points at specified locations and then to draw figures (the little triangles) whose vertices "snap" to the predefined points. |
Constructing all figures
The brute force approach constructed each of the 212 -1 = 4095 possible nonempty subsets of the twelve triangles. We found it most convenient to represent each subset (in Avenue, the language of ArcView desktop GIS) as a list of its triangles. To make such a list, we began with a list of them all: {Triangle 0, Triangle, 1, ..., Triangle 11}.
The main loop to explore all possible solutions simply incremented an integer from 1 to 4095. Its twelve-digit binary representation therefore began at 000000000001B and sequenced through all twelve-digit binary sequences until it reached 111111111111B (= 4095). At each state, the set of 1's determined which triangles to pick.
For example, when the loop index was 67 = 00001000011B = 20 + 21 + 26, the corresponding subset was represented by the list {Triangle 0, Triangle 1, Triangle 6}.
Finding connected figures
Now the GIS capabilities came to the fore. Having produced a list of triangles, we first merged them into a single polygon (potentially disconnected). The GIS immediately identified whether the merged polygon was disconnected. In such a case we knew it could not correspond to a solution, so we went on to the next iteration. This left only the connected polygons to deal with. The GIS easily produced the boundaries of these polygons for further processing.
Counting sides
The question originally dealt with hexagons, so we needed a way to determine which connected collections of triangles are hexagons. The trick is not to count sides: when two sides of little triangles occur successively along a straight line, we really want to count them only once. You count angles instead. (Indeed, the very word "poly-gon" derives from ancient Greek words for "many-angle"). The GIS provides methods to march around the boundary of a polygon, retaining the coordinates of successive vertices, so that the angle at any vertex can be computed.
Indeed, we did not actually have to compute angles. Suppose you are examining the angle at the ith vertex along the boundary of a polygon. Let P be the vector pointing from the (i-1)st to the ith vertex and Q be the vector pointing from the ith to the (i+1)st. There is a simple test to see whether P and Q are parallel: form their wedge product. That is,
(P ^ Q) = (Px * Qy - Py * Qx)
where P = (Px, Py) and Q = (Qx, Qy). Vectors P and Q are parallel exactly when their wedge product is zero. Since floating point arithmetic may introduce a little imprecision, the appropriate test was to establish that the size of (P ^ Q) (that is, its absolute value) was sufficiently small.
Here's a fragment of the Avenue code we used. The variable lstPts represents the sequence of points around the boundary of the polygon; its subscripts range from 0 through K+1, with the K+1st entry "wrapping around" to the zeroth entry. The variable nSides counts the angles.
nSides = 0
for each i in 1..K
ptU = lstPts.Get(i) - lstPts.Get(i-1)
ptV = lstPts.Get(i+1) - lstPts.Get(i)
if ((ptU.GetX*ptV.GetY - (ptU.GetY*ptV.GetX)).Abs > 0.001) then
nSides = nSides + 1
end
end
Pretty straightforward: no trigonometry needed (thankfully).
Relating figures by symmetry
You can solve the puzzle without using the symmetry of the star, but the answer is much more interesting when the symmetry is used. Compare our presentation of the hexagons (which just lists them without regard to symmetric relationships) to our presentation of all the polygons (372 Kb) (which organizes them by symmetry) to see what a difference it makes.
Symmetries of the star
There are twelve symmetries of the star. Six, including the identity, are rotations by multiples of 60 degrees. The other six are a reflection about the vertical axis followed by one of the six rotations. A clockwise rotation by 60 degrees ("Sigma") and the reflection ("Tau") are therefore generators of the group. Specifically, every group element can be written in the form Sigmak * Tauj where k is one of 0, 1, ..., 5 and j is one of 0, 1. (This fact was used to loop over all group elements below.)
We began by representing the generators as permutations of triangles:
sSigma = "(1 2 3 8 7 6)(10 4 11 9 5 0)"
sTau = "(1 3)(6 8)(0 4)(5 11)"
In this notation, a sequence of numbers (triangle names) within parentheses designates a cyclic permutation. For example, "(1 3)" interchanges triangles 1 and 3; "(1 2 3 8 7 6)" sends triangle 1 to the position formerly occupied by triangle 2, triangle 2 to triangle 3, ..., and triangle 6 goes back to where triangle 1 used to be. (Any triangles not specifically referenced will remain in place.) You can readily check that these two permutations indeed describe the generators Sigma and Tau.
Representing symmetries in a program
This cycle notation may be a convenient, compact representation for the programmer, but not for the computer. The computer program benefits from a data structure that explicitly describes where each triangle is sent by a permutation. An array would be a natural data structure for this, but the language we used ("Avenue") does not support arrays. However, Avenue does support an "associative array," or dictionary. A dictionary is an efficient implementation of a collection of matchings from one set (the "keys" or "index" elements) into another set (the "values").
Using some string-processing operations, we could break sSigma and sTau into their basic cycles and then process each cycle into a dictionary. For example, the dictionary for sSigma associates the value "2" with the value "1", indicating that Sigma sends triangle 1 into triangle 2's position. Let's write "1-->2" for that. We therefore wrote a small section of code that is capable of taking a cycle such as "(10 4 11 9 5 0)" and turning it into 10-->4, 4-->11, 11-->9, 9-->5, 5-->0, and 0-->10. This is a simple programming exercise.
It turned out to be helpful to write a group multiplication routine. This routine is given the dictionary representations of two permutations and returns the dictionary representation of their product. It's easy to write: if A and B are the permutations, then to find where A*B sends triangle i, we just apply B to i, then apply A to that. More explicitly, if i-->j is part of permutation B and j-->k is part of permutation A, then i-->k is part of permutation A*B. So here's the entire multiplication program in Avenue:
dctA = SELF.Get(0)
dctB = SELF.Get(1)
dctC = Dictionary.Make(dctA.Count)
for each i in dctB.ReturnKeys
dctC.Set(i, dctA.Get(dctB.Get(i)))
end
return dctC
Notice that this algorithm is perfectly general: dctA and dctB could be any permutations, of 12 elements or of 1,000.
Finding related figures
In our application, figures are represented by lists of triangles. The image of such a figure under some symmetry is obtained simply by applying the symmetry to each element of the list. For example, the list we saw earlier--{Triangle 0, Triangle 1, Triangle 6}--is mapped to {Triangle 4, Triangle 3, Triangle 8} by Tau.
To collect related figures together (that is, to compute the group orbits), we simply used the one figure in each orbit with the smallest binary value. For any given figure this meant applying each group element to the list, computing the binary value, and retaining the smallest among the twelve as the orbit's representative. At the same time this told us exactly which group element transformed a given figure into the representative.
(This is where we used the group multiplication routine. The loop was coded by looping over all possible values 0, 1, ..., 5 of Sigma's exponent and 0, 1 of Tau's exponent in the most general expression Sigmak *Tauj of a group element. This meant we began with the identity element and repeatedly multiplied by Sigma until we reached Sigma5; then we started over with Tau and repeatedly multiplied by Sigma until we reached Sigma5 * Tau.)
The techniques just described generalize readily to exploring the action of any small finite group on sets of objects, provided that
- The group is presented in terms of generators.
- The generator actions are defined by permutations given in cycle-product notation.
Displaying the answers
To display the answers, we simply used the GIS's capabilities to displace any arbitrary figure by a determined amount. We elected to displace a figure upwards by an amount determined by its orbit and to the right by an amount determined by the group element that maps the figure into the smallest orbit representative. Done!
Summary
A good GIS can provide a rich assortment of tools for geometric construction, manipulation, and analysis. This Star of David puzzle provides a nice illustration of the power and utility of these tools.
--Bill Huber, 12 June 2000
