Archive for the ‘Zapped Puzzles’ category

The Devil’s in the Angles

July 27th, 2017

Recently, while I was considering possible designs for a puzzle for my exchange gift for the next Gathering for Gardner, I thought about doing something with multiple layers of clear plastic, where interactions of markings on the layers define the puzzle. When you’re going to lasercut a large quantity of puzzles, keeping down the cost, and therefore the cut length, is paramount. So I wanted to be able to use the simplest possible markings on the pieces.

A straight line segment looked like a pretty good candidate, and it leads to an obvious puzzle goal: make the segments on two layers perpendicular. I still needed to choose pieces for these markings, but after a little trial and error, I landed on dominoes, with a segment centered in each square. For these, given some reasonable restriction on the allowable angles of the segments, the number of different pieces possible would land somewhere in the range of what would make for a good puzzle.

I ended up using segments that were turned either 15° or 45° off from the edges of the pieces. These admit exactly 12 different pieces, which can tile two layers of a 3×4 rectangle:


What makes this set particularly nice is that you can get two more puzzle challenges by changing the goal angle for the crossing segments. In addition to making them all perpendicular, you can make them all cross at 30° or 60°. These challenges should be easier, as there are two ways for an angle to differ from another one by 30° or 60°, but only one way to be perpendicular.

I also found a related puzzle that uses 10 dihexes. There are 13 pieces possible in this scheme, but I’ve omitted the ones with a lengthwise axis of symmetry from the puzzle:

In the end, I decided not to make either of these my exchange gift. I had a couple of prototypes made of the first puzzle, and it was clear to me that it needed to be larger than I could afford to make it and give away a few hundred copies. It also works best with a frame to hold the pieces and keep them neatly aligned, which adds considerably to the time and expense per copy. But even though I won’t be able to give this away at G4G13, I hope to be able to be able to sell a few copies at my vendor table there!

Edgematching with Catalan number patterns

March 11th, 2017

Edgematching puzzles are a genre that I haven’t previously explored very deeply. A classic example is the MacMahon squares puzzle. If you subdivide a square diagonally into four triangles, there are 24 ways to color the triangles using three colors. Using a set of 24 squares with all of the possible colorings, it is possible to make a 6×4 rectangle where all of the edges match.

As I was pondering the possibility of designing my own edgematching puzzle, I considered that pieces with multiple colors are a bit of a pain to make with a laser cutter. However, engraving lines is relatively easy. And I found a promising set of line patterns related to the Catalan numbers. The Catalan number sequence (1, 2, 5, 14, 42, 132…) is one that comes up in a surprising variety of contexts. For example, Catalan(n) is the number of distinct ways that n pairs of matched parentheses can occur in a string. For n = 3, we have ()()(), (()()), ((())), ()(()), and (())().

Replacing the parentheses with diagonal lines, and stretching them until they connect, we can make the following figures:

We can place these figures around the edges of a square, and use them to do edgematching— but with a new twist as to what counts as a match. Looking at the patterns that are made when two of these figures meet at an edge, we see that one thing that distinguishes them is the number of loops they make. One, two, or three loops can be made. This gives us three different puzzle objectives: place the pieces of the puzzle so that all internal edges have the same number of loops, where that number can be one, two, or three. The fact that there are three loop numbers is promising because it means that, on average, the probability of an edge in these three puzzles being a match will be one-third, the same as in the MacMahon Squares puzzle. This table shows the possible edge patterns, colored according to the number of loops:

From the perspective of puzzle design, it’s convenient that the proportion of pattern matches of each type is different; this seems likely to result in puzzles that are correspondingly different in difficulty, which is desirable. The table also reveals symmetries in how the edge figures form the different types of patterns. If you swap both the rows and the columns of the mirror pair of figures, you get a table with the same loop numbers in the same places, as we would expect. Perhaps more surprisingly, this also works with the first and second rows and columns. Thus those two edge figures form a sort of hidden symmetric pair. If you swap all instances of one in a puzzle solution with instances of the other, you will get a second solution.

There’s still one task remaining before we have a puzzle design: choosing the pieces. The MacMahon squares puzzle used every possible piece. Since we have five edge types here, instead of three, that would give us more pieces than we’d really want for a good manual puzzle. There are probably several reasonable options here, but in the interest of prototyping, I wanted to start with a small piece set, so I decided to explore a set of nine pieces with bilateral symmetry. Here’s a solution with single loops:

And here’s a double loop solution for comparison:

I’ve already had prototypes made of this puzzle, and it feels promising. I hope to have at least one more post about variations on this design, but for now I’ll stop here.

Magic figures from crossed stick configurations

July 1st, 2015

When I was working on finding configurations to use in crossed stick puzzles, it occurred to me that the same configurations would make good bases for magic figures. Since each piece is a line segment with the same number of intersections, you could put numbers at intersection sites, trying to arrange them so that the numbers on each segment add up to the same magic sum. Since I had already figured out how to use Numberjack to solve magic figure problems in the context of magic dice, it was simple enough to adapt the code to solve other magic figures.

The puzzle that I’m selling as Grand Hex can form two different figures. Since they each have 24 intersection points, it seemed reasonable that one could use the numbers from 1 to 24 on the intersections, and get a magic figure with a magic sum of 50. And here’s one for each configuration:

magic-grand-hex-1

magic-grand-hex-2

The gold lines aren’t part of the original puzzle configurations, but they were the obvious places to add a few constraints, since the solver otherwise finds a very large number of solutions for the figures with just the black lines.

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.

A Ten Piece Triangular Grid Puzzle Configuration

June 24th, 2013

Here’s a configuration that I found while doodling a few weeks ago:

hex-10

At the time, I was thinking of the 12 piece puzzles I found using the triangular grid; this configuration could be an easier challenge for that puzzle set that wouldn’t use all of the pieces.

But it could also make a good puzzle in its own right. We can use exactly the same slot scheme here as in the decagram puzzle. That puzzle used deep/shallow slots, (pointing the same direction) at the inner slot positions, and up/down slots at the outer positions. There are ten such pieces, which can be flipped horizontally but not vertically. Outer slots always connect with outers, and inners with inners, and the inner connections are bipartite, so it ought to work.

Ups and Downs (and Deeps and Shallows) revisited

June 21st, 2013

hexcross

I would like to be able to report that I have produced a successful prototype of the crossed stick puzzle I described in a previous post. But I cannot. This photo is a lie. There are two configurations for this puzzle, for which I intended to use two copies of each of the six possible pieces with up/down binary slots:

hexcross-both

I say “intended to” because the puzzle appears to not be possible to solve. Specifically, the 0110 piece is rather intransigent for the configuration on the left, and it doesn’t seem possible to fit two of them in without changing the piece set. Which is indeed what I did to put together the solution shown at top. For the configuration on the right, 0101 is the problem piece.

Problem #41: Are there sets of pieces that can be assembled into both of the above figures? It would be ideal if all 6 possible pieces are present in at least one copy. (I’d have explored this manually, but for the other reason this prototype was a failure: the material was too thick for the width of holes I used, and a number of pieces snapped in the process of trying to assemble the above. So I am not able to test out whether I can make two different configurations with any piece set without running out of intact pieces.)

In crossed stick puzzles, we like for solutions to be “assemblable,” meaning that there is no cycle of pieces where each has a downward facing slot connected to the next piece and an upward facing slot connected to the previous piece. (If there were, there would be no piece you could place last.) The assemblability condition implies the existence of a partial ordering among the pieces, where the pieces are ordered according to which ones are “on top” of other pieces. It follows that that there must be at least one piece with all slots pointing up and one piece with all slots pointing down.

It turns out that the Star of David puzzle using a single set of these pieces, which I proved was unsolvable due to a clever parity argument, is also unsolvable because it has only one 0000 piece. (Likewise, the dual Star of David puzzle using two sets of pieces, which I proposed in order to get around the parity problem, is also unsolvable, because that would require four 0000 pieces.)

An alternative to the up and down slot scheme is the deep and shallow slot scheme, where all slots point the same direction on each piece. This scheme bypasses assemblability issues entirely, but it has another problem: because upward and downward pointing pieces may only connect to each other, the configuration they form must be bipartite. It turns out that a lot of interesting configurations aren’t! Here are the configurations possible on a triangular grid with 12 pieces with three equally spaced slots:

(Did I miss any?

(Did I miss any?)

Only two of these configurations are bipartite. They can be made with a double set of 6 pieces with a deep/shallow slot scheme. Here are a couple of prototype lasercut puzzles in these configurations:

minihexcross

But what about the rest? Is there some way we can change our piece set to be able to make them? If we allow the middle slot to take all four possible combinations of up/down and deep/shallow, while the outer slots are deep/shallow and, as before, point the same direction, the resulting set should be more flexible in the configurations that can solve. (Conveniently, there are twelve such pieces.) Any subconfiguration with a cycle formed by an odd number of pieces that is connected only by outer slots is still impossible to solve. Therefore the configuration with the triangle shown in brown is still impossible. But the others should still be solvable.

(As I was finishing off this post, another set of pieces to use with these configurations occurred to me. We can make a set of pieces where each piece has exactly one deep, one middle, and one shallow shot, and the slots can occur in either direction and any order. As before, there are twelve such pieces. Can they be assembled into all of the above configurations?)

Three More Crossed Stick Puzzles

March 28th, 2013

Since I last posted about crossed stick puzzles, I’ve come up with three new ones. Here’s one of them:

This one nicely fills one of the spots in the binary word table. There are eight pieces with three slots apiece; if we use binary shallow/deep slots, there are exactly eight possible pieces, because the pieces won’t be flippable vertically or horizontally within the puzzle.

The principle behind this piece configuration can be used to make other configurations. You can take any line segment, together with a center point, reflect the segment across an axis passing through the center, and create images of the original and reflected segments over successive rotations around the center to make configurations with rotational (indeed, dihedral) symmetry. However, because the pieces wouldn’t generally be horizontally flippable, (are there exceptions?) this only produces puzzles with combinatorially complete piece sets when the number of pieces is a power of two, and only 8 and 16 make reasonable numbers of puzzle pieces. In fact, I’d argue that the ideal range of numbers of pieces for a puzzle of this type is between 8 and 12, with a penumbra extending to about 6 and 16 in which puzzles will still be interesting to some solvers, but not as many. This necessarily constrains the quantity of viable puzzle configurations to a number that is finite, and may indeed be quite small.

But if the math keeps the number of possible puzzles down, inventing new ways to skirt the constraints we’ve set for ourselves can create new possibilities. Witness the following configuration:

Here the slots are ternary: intersection points can have slots that are ⅔ of the width of the piece (pointing up or down) or they can have two slots ⅓ of the width of the piece, pointing both up and down. Where three pieces intersect, one of each of these three slot types must be present. Three piece intersections are harder to work with than regular intersections. I’m pretty sure there is no finite configuration on the triangular grid containing all pieces of the same size with all intersections being three piece intersections.

So we have to fudge. This configuration looks like it has two kinds of three slot pieces, because three of the three slot pieces intersect at a two piece intersection. The trick is that the slot on the two slot pieces at the two slot intersection has a special, single ⅓ width slot, so that it can match the regular slots on the three slot pieces. Nicely, there are exactly three possible two slot pieces with one slot of this type and one regular slot.

In this scheme there are ten three slot ternary pieces, when both horizontal and vertical flipping is allowed. Since there are only nine three slot pieces in the configuration, one piece must be excluded. In fact, our hand is forced: the excluded piece must be the one that has all three slots of the double ⅓ width type. This is because the total number of double ⅓ width slots must equal the number of three piece intersections, which is nine. Before excluding that piece, there is one double ⅓ width slot in the two slot pieces, and 11 such slots in the three slot pieces. Well, if we can’t have a combinatiorially complete set of pieces, the next best thing is a combinatorially complete set minus the most exceptional member, which we could argue that this piece is, on account of it being the only piece with both horizontal and vertical reflection symmetry.

Finally, two configurations for the same piece set:

The configuration on the left was one that I implied in this post. If we use shallow/deep binary slots, we have pieces that can be flipped horizontally but not vertically. There are six of these and twelve pieces in the configuration, so we can use a double set of these as our piece set. As an extra bit of good fortune, there is a second configuration that uses these pieces.

I’m currently getting prototypes of the last two of these lasercut, so I hope to be able to show off the results soon. (I came up with the first one after I put in the order, so it will be a while before I get around to making a prototype of it.)

Crossed Stick Variations

December 6th, 2012

In a (somewhat) recent post, I discussed my decagram puzzle that I used for the gift exchange at Gathering for Gardner 10. Of course, I wondered what other puzzles of this type are out there waiting to be found. I’m particularly interested in mathematically elegant puzzles, which for me means ones that use combinatorially complete sets of pieces, that is, sets of pieces where every possible piece for a given scheme is actually present. Rob Stegmann has a page with a listing of similar puzzles, which he calls crossed stick puzzles.

In a crossed stick puzzle like my decagram puzzle, each piece has a number of slots, which are at the same position on every piece, and each slot can be one of a number (typically two) of types. This means that you can assign a code to every piece, which will be a binary string if there are two slot types.

Stegmann’s page also notes the possibility of different slot compatibility schemes: instead of 1 and 0 being compatible with each other and not with themselves, the opposite is possible, although it seems harder to realize physically. (Perhaps magnets might lend themselves to such a scheme.) With three or more slot types, more compatibility schemes become possible.

Thus there are essentially four attributes that describe a puzzle of this type. These are the configuration of pieces in the completed puzzle, the allowable actions that can be performed upon a piece in a given position, (rotation, flipping) the compatibility scheme, and the piece codes that are present.

What viable piece configurations exist? For our purposes, a legal puzzle configuration consists of a number of congruent pieces, which can be represented as line segments marked at their intersection points. Exactly two pieces must meet at each intersection point. (Relaxing that requirement may bear fruit, but it also complicates the physical design of slots in a puzzle.) If there are two intersection points per piece, the situation is not terribly interesting: the pieces must topologically form a loop, and there are an infinite number of ways they can do this. So I’ll restrict myself to configurations where the number of intersections per piece is three or greater.

As my decagram puzzle might suggest, one class of puzzle configurations consists of star polygons. Oskar van Deventer designed a heptagram puzzle, which uses flexible foam pieces to get around the assemblability problem I mentioned in the previous post. It not have a combinatorially complete set of pieces; making up for this, the flexible material does allow the pieces to form a number of different patterns.

Another class of crossed stick puzzle configuration consists of square grid patterns; most of the examples on Stegmann’s page are of this type. Few of them use complete sets of pieces, although “The Fence”, designed by Jean Claude Constantin, has a complete set from which the 1111 and 0000 piece have been removed.

In addition to grids and stars, we can make “broken stars”, where small segments are excised from the center of each of the pieces in a star configuration. Are other puzzle configurations possible?

As you can see, at least one is. In this configuration there are eight pieces. Taking a note from “The Fence”, I used all of the possible pieces except the two where all of the slots are of the same type. (As in the decagram puzzle, the pieces can be flipped horizontally, which means that there are ten different piece types possible before we exclude those two.)

A complicating aspect of this configuration is that intersections may occur at different angles depending on whether the piece is part of the outer square or the inner square. The slot shape I used allows the same slot position to work for both 45° and 90° angles. An unintended consequence of the design of this puzzle is that the pieces can also form an octagram.

I’d certainly be interested in hearing about other piece configurations that could be used in a crossed stick puzzle, if you can come up with any.

A Polyformist’s Toolkit: Symmetry Variations

May 25th, 2012

It lately occurred to me that there are concepts that I use (and see used by others) in creating variations on polyform puzzles that I haven’t seen explained very thoroughly, and it might be helpful if I used this space for just that purpose.

Some polyomino puzzles using symmetry variations

The first of these is the use of different kinds of symmetry in defining the set of pieces used in a puzzle. (I touched on this in my post on rectangular-cell pentominoes.) Normally, all combinations of rotations, translations, and reflections of a polyomino in a grid are considered to be equivalent. Leaving aside translations for the moment, the possible rotations and reflections of a polyomino are equivalent to the group of symmetries of a square. We can find variations on polyominoes by restricting the allowed symmetries to subgroups of that group. For example, the one-sided polyominoes are the result of allowing only rotations, not reflections. Rhombic cell pentominoes (which Kadon sells) allow 180° rotations, plus diagonal reflections. My Agincourt puzzle allows only reflections over vertical axes, assuming that the arrows are pointing vertically. Notice that it doesn’t matter which direction the arrows point as long as they point in the same direction; this suggests that what we are interested in isn’t symmetry subgroups per se, but classes of subgroups where two subgroups that are related to each other by symmetries of the square are equivalent.

What are all of the possible variations with different allowed transformations? We can generate a representative subgroup of every class by using some combination of reflection over a particular axis parallel to the grid, a particular diagonal axis, and 90° and 180° rotations. Here’s a chart of the symmetry variations this produces.

  Polyomino Type Reflection Rotation # of Symmetries
Free Either 90° 8
Parallel (a.k.a. Rectangular) y axis 180° 4
Diagonal (a.k.a. Rhombic) x=y 180° 4
One-sided None 90° 4
Oriented Parallel y axis None 2
Oriented Diagonal x=y None 2
Polar One-sided None 180° 2
Fixed None None 1

I chose the above terminology for the types (after keeping “free”, “one-sided”, and “fixed” as established terms) in order to build in some helpful mnemonics. The types with four symmetries have short names. The types with two symmetries have longer names based on the names of the types whose symmetry groups their symmetries are subgroups of. The odd duck here is “polar one-sided”, which is a subgroup of all of the larger symmetry groups, but putting “one-sided” in its name makes the types with two symmetries nicely echo the names of those with four.

Here’s a chart of the number of polyominoes of each type for a given size:

Polyomino Type 1 2 3 4 5 6 7 OEIS #
Free 1 1 2 5 12 35 108 A000105
Parallel 1 2 3 9 21 68 208 A056780
Diagonal 1 1 3 7 20 62 204 A056783
One-sided 1 1 2 7 18 60 196 A000988
Oriented Parallel 1 2 4 12 35 116 392 A151525
Oriented Diagonal 1 1 4 10 34 110 388 A182645
Polar One-sided 1 2 4 13 35 120 392 A151522
Fixed 1 2 6 19 63 216 760 A001168

(The odd entries for the polar one-sided polyominoes track those for the oriented parallel polyominoes exactly for several terms, before eventually diverging. There are 4998 9-ominoes for both, and 67792 polar one-sided, and 67791 oriented parallel 11-ominoes. It seems unlikely that this is a coincidence. Does anyone know why this occurs?)

These types can be realized geometrically by replacing square cells in a planar tiling with cells with the appropriate symmetry. Another way they can be realized is by keeping the cells square and marking them with a figure with the appropriate symmetry. This is essentially what I did by cutting arrow shaped holes in the Agincourt pieces. The latter method allows the possibility of mixing different symmetry types in the same tiling. I don’t believe I’ve seen such a problem before, so let me be the first to fill what may be a much needed gap:

Problem #28: Tile a 6×6 square with the oriented parallel, oriented diagonal, and polar one-sided trominoes. No tromino should touch another of the same type.

With these symmetry subgroup based polyform variations in mind, any type of polyform on a square grid can be transformed into an entire family of polyforms. In particular, polysticks would reward exploration in this light, which does not seem to have occurred yet. A similar analysis to the one above can be made for symmetry based variations of polyiamonds and polyhexes. Bringing translation symmetry subgroups into the picture leads to things like checkered polyominoes. I may get to these in later posts; this one was getting long enough that I needed to wrap it up.

I should note that Peter Esser’s pages on polyforms cover these variations, and that his polyomino solver program can work with any of the 8 symmetry types (but not with mixed types.) (It is, sadly, a Windows binary, but I’ve been able to make it work under Wine on Linux.)

Binary System, Decimal Star

April 19th, 2012

If you participated in the gift exchange at the 10th Gathering for Gardner, which was held recently in Atlanta, you would have received one of these in your bag of exchange gifts:


It is common, (but by no means required) for participants to use the number of the conference as a theme in their exchange gift in some way. I considered a ten pointed star with pieces that slot together as a promising shape for a puzzle, and I recalled that there were ten distinct reversible binary sequences of length four. (In this scheme 0011 and 1100, for example, are considered equivalent because they reverse to each other.) This meant that with four slots at intersection points, if there were two possible positions for each slot, (like up and down) there would be exactly ten possible pieces, which would make an elegant puzzle set if I used one of each. Conveniently, the pieces could be flipped horizontally to physically realize the reversal of the string. Inconveniently, the pieces could also be flipped vertically, which would invert the 1’s and 0’s, and lower the number of distinct piece shapes to six. Another problem is that some configurations of pieces could not be physically assembled. If there was a triangle of pieces where each had an up slot followed by a down going around the triangle, there would be no way to fit the third piece in, because it would simultaneously need to be slotted in from above and below.

I solved both of these problems at once by changing the inner slots to all face the same direction, and to have shallow vs. deep as their two possible states instead of up and down. Now the ten pieces can be divided into two pentagonal configurations that are connected by their outer slots, and connect to each other by the inner slots. Because every triangle in the star contains the two inner slots of a piece, the triangles are all assemblable. The pentagons must also be assemblable, because there are only four pieces with up and down outer slots, so one side of the pentagon must have two slots pointing the same direction, and that side may be placed last. And because the direction of the inner slots is forced, only horizontal flipping is allowable. Here’s a photo of an assembled puzzle, along with an unassembled set of pieces:

Mathematical niftiness aside, is this a good puzzle? I think so. It has a fair number of solutions, but neither so many that you can easily stumble upon one without applying any strategy to solving the puzzle, nor so few that you have to spend a lot of time engaged in trial and error. Let me know if you have one of these and need hints for solving it.

In an upcoming post, I’ll discuss some variations on this type of puzzle.

Why L-topia Is Awesome

December 7th, 2010

It’s the holiday shopping season, so I figured it couldn’t hurt to write a post or two on the puzzles I am selling.

Every mathematical puzzle designer worth his or her salt has an argument for their puzzle’s awesomeness using impressive sounding mathematical justifications. This, for L-topia, is mine.

There are 12 pieces in the set. Empirically, 12 is a good number of pieces for a mathematical puzzle. There are 12 pentominoes, and 12 hexiamonds.

The shape of the pieces, an l-tetromino, has some desirable properties. It is very highly tileable. Two factors that affect the tilability of a polyomino are its size and its symmetries. Smaller and less symmetrical polyominoes are the most tilable. The l-tetromino is the smallest asymmetrical polyomino, and the only asymmetrical tetromino, so it should be the most tilable of all.

A set of 12 l-tetrominoes tiles a 6×8 rectangle in 1114 ways. That’s probably the most for any set of 12 copies of a single polyomino tiling any rectangle, but it’s not that impressive compared to other sets containing multiple shapes. For example, the 12 pentominoes can tile a 6×10 rectangle 2339 ways. 

But because the shapes are all the same, if you mark all of them in some way to distinguish them from each other, (as the holes on the L-topia pieces do) every permutation of placements of the 12 l-tetrominoes can create a distinct tiling. Now the total number of tilings is roughly 1114 · 12!. (Actually, it’s slightly less because some of the tilings of the rectangle are symmetrical: about 55 of the 1114 solutions are symmetrical by reflection or 180° rotation, so the total is about 1059 · 12! + 55 · 12! / 2, or about 520 billion.)

Well, that’s a pretty impressive number, but having an impressively large space of possibilities does not, by itself, make for a great puzzle. In this case, however, I do think it is helpful, and I’ll explain why presently.

Suppose I think of a proposition that can apply to any of the holes in the set. For example, that the hole appears in an odd numbered row. Because there are two different kinds of holes, it may be elegant to use either the opposite of that proposition, or some proposition that is complementary in some way, to apply to the second kind of hole; in the problem illustrated by the solution above, we have the round holes in odd rows, and the square holes in odd columns. Suppose the probability of the proposition being true is ½, and suppose that the probability for each hole is independent from the others. (One must take care that the placement of holes on the pieces doesn’t fatally interfere with independence; if, for example, we had asked for circles on odd rows and squares on even rows, there would have been pieces that could not have been placed legally anywhere.) Then the probability that the proposition is true for all of the holes is 1/224. Given this piece of information, we can get an expected number of tilings where the proposition is true by multiplying that probability by the total number of tilings.

The result is about 31,000. That number is tiny compared to the size of the total space of tilings, but I can say from experience that it makes for puzzles that are challenging but solvable. And it gives us wiggle room to use propositions with probabilities that are a little smaller than ½, or for which the probabilities are not entirely independent. The result is that we can come up with a wide variety of propositions to use in designing puzzles with the expectation that they will provide a good puzzle solving experience. L-topia isn’t just a puzzle, it’s a natural puzzle creation kit!

Why L-Topia isn’t awesome, and Agincourt is

Unfortunately, to be perfectly honest, being a “puzzle creation kit” interferes with L-topia’s accessability as a puzzle. Because the circular and square holes have no inherent meaning, but have to have their meanings imposed by a puzzle’s directions, you can’t simply take the pieces out of the box and start solving.

Agincourt, on the other hand, with its 64 squares with an arrow in each, practically begs to be turned into four 4×4 layers with the arrows aligned. Of course, there are other challenges to be found, but the one that literally comes out of the box is both elegant, and has a reasonable level of difficulty. (Some of the L-topia puzzles are better for hardcore puzzle solvers.)

Once again, I have both puzzles available for sale. Order soon for delivery by Christmas!

Rectangular Pentominoes

October 29th, 2010

When I had Agincourt made, I purchased a bulk order of 4″ × 4″ × 1″ white cardboard jewelry boxes. They look quite nice, and they fit both Agincourt and L-Topia, but I have enough of them that I’m on the lookout for ideas for polyform puzzles that fit nicely into a few square layers. And now I’ve found one:

I stumbled upon this by noticing that there are 21 pentominoes of this symmetry type, which could make three 5 × 7 layers. I wanted square layers; usefully, squashing the cells into rectangles with a 5 : 7 ratio of width to length simultaneously gave me the square layers and gave the cells the right type of symmetry.

It’s been observed that any of the subgroups of the symmetries of the square can be used as the basis for a type of polyomino puzzle. (See Peter Esser on pentomino variations, and particularly the page on parallel polarized pentominoes, which are equivalent to rectangular pentominoes.) For Agincourt, I physically realized one of these types by laser-cutting symmetrical, arrow-shaped holes in every square cell. Other types have been made by changing the shape of the cells themselves. Rhombic pentomino sets have been produced by Kadon as Rhombiominoes. Sets of rectangular polyominoes, shaped like Meiji chocolate bars, have been produced by Hanayama. (These may not be equivalent to the rectangular polyominoes above, if the top is distinct from the bottom, which isn’t clear from the pictures there.) I’m not aware of anyone who is producing complete sets of rectangular pentominoes, so there’s a gap I’m willing to step into.

If you take out the pentominoes with a diagonal line of symmetry in their non-squashed form, (the green ones above) the remaining 18 pentominoes come in 9 pairs, where each pair contains two different squashed versions of the same pentomino. With these pieces it is interesting to try to tile a pair of shapes with the same orientation such that one piece from each piece pair is in each shape. (Note that if the two shapes had different orientations, you could always make the second shape with corresponding pieces in the same position as the first, but squashed in the other direction.)

Since the set has area 90, the obvious thing to try is two 9×5 rectangles. The next most obvious thing to try is two 7×7 squares with corners removed. Neither of these seem to work, although I have no proof.

One thing that does work is a 7×7 square with a 4×4 square cut out of one corner. But this is again just the case where you can trivially get the solution to the second piece by squashing the pieces differently, because this shape has diagonal “mirror symmetry”.

Another problem is finding three congruent shapes, each of which has the following property: three of its pieces have their twin in one of the other two shapes, and three have their twin in the remaining shape:

I’m looking into having some sets of the rectangular polyominoes made, and if I can do so economically, I’ll sell them through the store. (Sadly, TechShop Portland, the facility where I made Agincourt, has gone away, so I will need to look at other options.)

Introducing Agincourt (to the Blog)

February 25th, 2010

Agincourt is one of the lasercut acrylic puzzles which I’m selling through the store. It’s the set of all of the ways to make 2-, 3-, and 4-ominoes with arrow shaped holes in each square pointing in the same direction. The symmetry of the arrows means that you can flip over pieces without changing the arrow directions, but you can’t rotate them. Most of the puzzles I have designed for the set ask for the solver to make all pieces point the same way, but the arrows naturally suggest a scoring system to handicap the puzzle for different levels of solvers — just count the number of pieces you had to put in the wrong direction, and try to improve on your score.

Here’s a solution to the puzzle that literally comes out of the box. (The puzzle comes in the box with 4 layers of pieces in 4 × 4 squares.)

Expect more Agincourt puzzles later.