Archive for August, 2013

Hinged Polyforms

August 30th, 2013

Here’s a tiling of the nine hinged tetriamonds:

hinge-iamond-2

Hinged polyforms meet at corners rather than edges as in regular polyforms. The corner connections, like hinges, are flexible: two hinged polyforms are equivalent if it is possible to turn one into the other by swinging the hinges at the vertices, in addition to rotating and reflecting the whole pieces. Hinge angles that cause two cells to lie flat against each other are disallowed, as it isn’t possible to visually distinguish which side of the edge has the hinge. In some cases, hinges may be “locked”, with angles that are completely determined by the geometry of the piece. (For instance, when three cells meet around an equilateral triangle.)

With the above piece set, it is possible to realize all of the pieces using a small set of angles for the individual triangles. Other sets may be trickier to work with.

Here are the hinged tetrominoes:

hinge-4-ominoes

Can a symmetrical tiling be found for these? Problem #43: Find one.

Constellations

August 22nd, 2013

I made a presentation on flexible polyforms at the last Gathering for Gardner, but there were some polyform types that I didn’t get to, since I hadn’t yet come up with any good problems for them. One odd sort of polyform, which I am fancifully calling a constellation, can be obtained from configurations of points on the plane. We can consider two sets of points on the plane to be distinct if the pattern of collinearity among the points is different. Because every pair of points defines a line, the lines with only two points are, in a sense, not interesting; only the lines with three or more points need to be considered when determining whether two constellations differ. It seems reasonable to consider the order of points on a line to be significant; this gives us three different 5-point constellations with a pair of three point lines that meet at a point. There are 7 5-point constellations in all. Here’s the first tiling puzzle solution I found for them:

constellation-5-5

One rule for constellation tiling puzzles that I like is to disallow any point from one constellation from falling directly between two points in another constellation. This keeps the constellations more compact, and adds a little challenge to the puzzle. I like to get as much symmetry as possible in one of these flexible polyform tilings, so I decided to try for one with 7-fold symmetry. This was a little harder, but eventually I found the following tiling:

constellation-5-7

Where can we go from here? If I’ve counted right, there are 21 6-constellations. Of these, 7 can be formed by adding one independent point (a point on no line of 3) to each of the 5-constellations. The full set seems a little too big to solve by hand, but if we exclude the ones with independent points, a puzzle with the remaining 14 seems more manageable. (We may also want to exclude the 6-constellation with two separate lines of three points. With that one excluded, the remaining 13 6-constellations all can be formed from connected groups of lines with 3 or more points.)
constellation-6-set

The 14 6-constellations with no independent points.

Problem #42: Find a tiling of 6-constellations with 6-fold dihedral symmetry. Either the set of 13 or the set of 14 will do. Even more symmetry is even better.

Crossed Sticks: Compatability Variations

August 19th, 2013

So far, the crossed stick puzzles I’ve designed have been limited by the two-dimensional nature of designing for lasercut materials. But 3D printing presents another option for puzzles that can’t be formed from flat pieces.

One new area to explore is connector compatibility variations. In most of the puzzles we’ve looked at thus far, there are two types of connectors or slots, ups and downs, or deeps and shallows, and each type matches the opposite. Suppose instead we wanted two types of connectors where each matches itself rather than the other type. It can’t be done (as far as I can tell) with lasercut slots, but it can be done! My first 3D printed puzzle prototypes are shown below:

3d-protos

Consider connectors made of pairs of studs and holes as in the the puzzle on the left side of the image above. When we flip and rotate a piece with this type of connector in order to join it at right angles with another such piece, the studs on each piece match the holes on the other. But this only works when the two connectors have the same orientation. When a connector with a vertical stud pair is matched with a connector with a horizontal stud pair, both pairs of studs end up at the same position, so the connectors can’t join. We can call this connection scheme the same-match scheme, as opposed to the other-match scheme.

With diagonal pairs of studs and holes, (as on the right side above) flipping the piece swaps the positions of the studs and holes instead of keeping them in place. This means that the resulting puzzle will use the standard compatibility matrix. Initially, this may seem disappointing: after all, this is just the puzzle we could get without using stud and hole blocks. But in fact this setup allows us to use both compatibility schemes! If we place both layers of pieces so that the studs face the same direction, we have a puzzle using the same-match scheme.

It should be pretty clear that these two schemes are the only viable connection schemes for two connection types. When we move to three connection types, things get a little more complicated. It will help to represent a connection scheme as a graph, where the vertices represent connection types, and compatible types are connected by an edge. Since self-compatibility is possible, the graphs may contain loops from one vertex to itself. Here are the graphs for the two binary connection schemes:

2-compats

One example of a ternary connection scheme can realized with lasercut slots. Let the three slot types be deep, middle, and shallow, where middle depth slots match themselves, and deep and shallow match each other. Here’s the graph for that scheme:

3-compats-1

The advantage of working from graph representations of connection schemes is that we can come up with the graphs first, and then worry about how we will physically realize a puzzle using that scheme later. So let’s just doodle some promising three-vertex graphs:

3-compats-all

Some constraints become apparent at this point. First, there can’t be a vertex with no edges, because that would represent a connection type that can’t connect to anything, and its presence would immediately render a puzzle unsolvable. Vertices that connect to everything (including themselves) are also problematic. Such a connection type doesn’t add to the challenge of a puzzle, and if all vertices had this property, the puzzle wouldn’t be a puzzle at all. I’m inclined to remove graphs with this kind of vertex from consideration for the time being, allowing that I may be wrong, and interesting puzzles using this kind of vertex may indeed be possible.

Another problem that can occur is that vertices may be indistinguishable. For example, consider this graph:

3-compats-indist

Both the rightmost and the leftmost vertex in this graph are connected only to the center point. What this means in practice is that it doesn’t matter whether a connector has the leftmost vertex type or the rightmost vertex type; the connectors will behave exactly the same. But if this is so, there is effectively no difference between this connection scheme and the other-match binary scheme. For the connector types in a scheme to be distinguishable, each must have a different neighbor set.

A quality of a connection scheme that may be desirable is balance. Consider the following graph:

3-compats-unbalanced

The rightmost vertex only connects to one vertex, while the others both connect to two. Now imagine a puzzle that uses equal numbers of all three connector types, as we have typically done so far. Since we need all rightmost type connectors to match something, we have to use up all of the middle type connectors for this purpose. This means that the leftmost type connectors must all match themselves. Since no leftmost type connectors can match middle connectors, we find ourselves effectively using the three-height slot scheme. This doesn’t mean that this scheme is entirely unviable, but our piece sets are going to have to look a little weird to make it work. For the moment we will mainly concern ourselves with balanced schemes, where each vertex has the same degree. (That is, they are connected to the same numbers of vertices.)

Another consideration that will be important is the density of the graphs. This quantity is the ratio of the degree of the vertices (or the average if the scheme is unbalanced) to the total number of vertices. The density will have an effect on the difficulty of the puzzle and the number of solutions, since a high density means that if we randomly distribute connections, each connection has a high likelihood of being valid.

The following are the “good” ternary connection schemes under the above constraints.

3-compats-viable

The schemes in the top row have density ⅓, and those in the bottom row have density ⅔.

I could keep going about how we could realize some of these schemes in 3D printed puzzles, and I could get into quaternary schemes, but longpost is already long, so I’ll save this for later.