3-Trees and a Triangle

by Leslie E. Shader, Ph.D.

[A paper from the Gathering for Gardner 2 or 3 (1996 or 1998).]

In a paper, “Polysticks”, J. Recreatinal Mathematics, vol. 22(3) 1990, Brian Barwell introduced a new type of puzzle. Instead of tiling a region in the plane or packing a region in 3-space, Barwell considered a rectangular lattice (graph paper) and used “Polysticks” to cover certain subsets of the lattice. There has also been a puzzle called “845”, I believe produced by International Puzzles and Games in Taiwan. This used 10 polysticks each with 4 unit lengths. (A polystick of length n, is a set of n unit segments joined at the ends at an angle of 90, 180, or 270 degrees.) The “845” puzzle did not allow the pieces to cross.

For “3-Trees and a Triangle” we will use 3 unit lengths joined at the ends at angles of 60, 120, 180, 240, or 300 degrees. There are exactly 12 such pieces. In the language of mathematics (graph theory), each of the pieces is either a “tree” or a “triangle”. Actually we should say Euclidean Tree since angles as well as length are important. Since we wish a physical model of this puzzle we will not allow crossings. The pieces may be rotated or turned over.

The pieces are: [sketch of the 12 tritrigs, which see]

I am including with my submission, a list of more than 300 different lattices that can be covered by subsets of the set of all pieces above. I also have included a set of solutions for each of these. But the solutions are sealed! Please try some of the puzzles before looking at the solutions. I have included a smaller set of my favorite puzzles. Those puzzles with 6 or fewer pieces are relatively easy. I classify the puzzles using 7-9 pieces as [moderately] difficult, and if the puzzle requires 10-12 pieces the puzzle is difficult. Some of the 10-12 pieces have taken me up to 20 hours to solve by hand. Of course, I didn’t now if a solution existed or not, which means an exhaustive search had to be done. Within the sealed envelope marked “solutions”, there is also a set of six puzzles that cannot be solved. I am sure there are other interesting puzzles that I have not included inthe set that I am submitting to you.

Some thoughts on the technical aspects of the puzzles. I think that the unit length should be either 7/8 in. or 1 in., the individual pieces should be injection molded with width 1/8 in and 1/2 in. deep. Care must be given to fit at the vertices where more than 1 piece come together. Several rough sketches are included. I prefer rounded corners to sharp corners. A universal base can also be injection molded and should be large enough to make most of the puzzles I have included. There should be raised traingles (corners rounded) to hold the pieces in position. The “845” puzzle used circles but I think the triangles would be better.

Finally, although the use of the trees and triangle looks entirely new, the pieces can be “fleshed out” allowing an isoceles triangle, base angle 30 degrees, to “grow” on each edge. I have included a page with two examples. Actually, we are now very close to Damert’s “Bees” puzzle except that crossings are still not allowed. Perhaps the idea of joining pieces at the vertex and not the edge (two dimensional) or at an edge and not a face (three dimensional) is an idea whose time has come. Have you seen the Rubik’s Blocks puzzle?

Monotrig

There is only one monotrig (order-1 polytrig):

Name	Image	Aspects	One-Sided
I1		3

Ditrigs

There are 3 ditrigs (order-2 polytrigs):

Name	Image	Aspects	One-Sided
I2		3
L2		6
V2		6

Tritrigs

There are 12 free tritrigs (order-3 polytrigs) and 19 one-sided tritrigs:

Name	Image	Aspects	One-Sided
C3		6
E3		6
I3		3
J3		12	yes
L3		12	yes
O3		2
P3		12	yes
S3		6	yes
T3		12	yes
U3		12	yes
Y3		2
Z3		6	yes

Tetratrigs

There are 60 free tetratrigs (order-4 polytrigs) and 104 one-sided tetratrigs:

Name	Image	Aspects	One-Sided
B04		12	yes
B14		12	yes
C04		6
D04		12	yes
E04		12	yes
E14		6
E24		12	yes
E34		12	yes
F04		12	yes
F14		12	yes
F24		12	yes
F34		12	yes
H04		12	yes
H14		12	yes
H24		12	yes
H34		12	yes
I04		3
J04		12	yes
J14		12	yes
J24		12	yes
J34		12	yes
K04		6
L04		12	yes
M04		6
N04		12	yes
N14		12	yes
O04		3
P04		12	yes
P14		12	yes
P24		12	yes
P34		12	yes
Q04		12	yes
Q14		12	yes
R04		12	yes
R14		12	yes
R24		12	yes
R34		12	yes
S04		6	yes
S14		12	yes
S24		12	yes
S34		12	yes
S44		12	yes
T04		12	yes
T14		6
T24		12	yes
U04		12	yes
U14		6
U24		6
V04		6
V14		6
V24		6
W04		6
W14		6
W24		12	yes
X04		3
Y04		6
Y14		12	yes
Y24		12	yes
Y34		12	yes
Z04		6	yes

Quasi-Ditrigs

There are 9 free quasi-ditrigs (order-2 quasi-polytrigs) and 13 one-sided quasi-ditrigs:

Name	Image	Aspects	One-Sided
C12		6
I02		3
I12		3
L02		6
L12		12	yes
P12		12	yes
S12		6	yes
V02		6
Z12		6	yes

Intersections

As there is the possibility for polytrigs to cross each other at any (X,Y) intersection, the solution algorithm needs to prevent such crossings. Unlike with polysticks, the intersections are not simple (either used or available); multiple polyforms can use an intersection simultaneously.

In the puzzle matrix, we represent contstraints on intersections via up to 6 additional columns per intersection [†], in the form i(X,Y,Z) (or "X,Y,Zi"). This means that the segment in direction Z cannot go through the intersection, (X,Y). These are the Z directions:

  2    1
   \  /
3___\/___0
    /\
   /  \
  4    5

These intersection constraints are secondary columns, meaning that at most one polyform may use or fill a column. Unlike primary columns, secondary columns may remain unused/unfilled.

For each polyform, we check the angle between each pair of line segments. Both ends of each segment must be checked, but only in one direction (counter-clockwise) to avoid duplication. For any two line segments, there are six possibilities:

  B  / A
____/___     D ____    E ____    F ____
              /          \
    C        /  D'        \

• A: 60° (adjacent) -- no constraints are added.
• B: 120° (one-gapper) -- 3 constraints are added: the 2 line segments themselves (e.g. Z={1,3}), plus the gap in-between (e.g. Z=2).
• C: 180° (two-gapper) -- 4 constraints are added: the 2 line segments (e.g. Z={3,0}), plus the two gaps (e.g. Z={4,5}). Note that the gaps on the opposite side will be added when the other line segment is checked.
• D: 240° (three-gapper) -- no constraints are added. However, D' is a case of a 120° one-gapper (case B).
• E: 300° (four-gapper) -- no constraints are added.
• F: 360° (five-gapper or stub; only one segment involved) -- no constraints are added.

Only cases B & C require constraints.

If an intersection constraint is already used (or otherwise unavailable), no other polyform with the same contstraint may be placed in the puzzle solution.