Archive for December, 2012

Symmetry Variations on Binary Words

December 18th, 2012

In exploring the space of crossed stick puzzles, I’ve gone on a tangent into the world of binary words and their symmetries. A binary word is just a string where the “letters” can be one of two symbols; for convenience we’ll use 0 and 1. (The distinction between a “word” and a number in binary is that a word can have any number of leading 0’s, and these are significant.)

The usefulness of binary words in crossed stick puzzle design comes from our ability to encode them in the types of slots used in a piece of a puzzle. For example, my decagram puzzle uses pieces with outer slots that could point down or up, and inner slots that always point up, but could be deep or shallow. We can assign 0 to down and 1 to up for the outer slots, and 0 to deep and 1 to shallow for the outer slots. Then, reading across the slots, we get a binary word corresponding to a given piece. For example, down-shallow-deep-up is 0101.

One benefit of using binary words is that we can enumerate the possible pieces in a puzzle by counting the binary words of a given length, (in this case four). But there is a snag: The piece we called 0101 can be flipped horizontally, after which it would read as 1010. It seems that rather than plain binary words, what we want are the equivalence classes of binary words formed by some symmetry action, in this case, reversing the word. Examining these gives us four symmetrical words that map to themselves upon flipping, and six pairs of words that flip to each other, for a total of ten classes of length four.

Instead of horizontal flipping, we could, if our slots are only using an up vs. down slot scheme, flip them vertically. In terms of the effect on the pieces, this will invert all of the 0’s to 1 and vice versa. This gives us eight pairs of words that flip to each other. We could also allow both horizontal and vertical flipping. In this case there are six classes of words of length four.

At this point, you might want a table with the number of binary words of each type. That way, when you come up with a crossed stick puzzle idea you can look at the table on the row with the number of slots in the pieces, and see if there’s an entry that gives you the number of pieces you’d like. Or you could go the other direction, and look at an entry in the table and try to come up with a good puzzle for that entry. (This is how I designed my Decagram puzzle.)

Length Fixed Invertible Reversible Inv. & Rev.
1 2 1 2 1
2 4 2 3 2
3 8 4 6 3
4 16 8 10 6
5 32 16 20 10
6 64 32 36 20
7 128 64 72 36

Let’s give it a try using the piece configuration from my last post:



Applying the table to this, there are 12 pieces with 4 intersections (and thus, slots) in that configuration. There are no entries of 12 in that row, so we’re going to have to get creative. There’s a 6 in the Inv. & Rev. column; we can make our (well, my) puzzle have two copies of each piece corresponding to one of those. The intersection points are conveniently symmetrical, which gives us reversibility, and if we use up/down slots, we get invertibility. So now we have a puzzle design.

Of course, there’s one step left, which is making sure that the puzzle can be solved. (Ideally, by a human being of reasonable intelligence devoting no more than a reasonable amount of time.) It is quite possible to develop a design for a puzzle of this type that can’t be solved.

For example, this star of David puzzle, using one set of the invertible & reversible 4 slot pieces, is unsolvable. To see why, look at the relevant binary words, and consider the first and last digits, corresponding to the slots at the six points of the star.

0000
0001
0010
0011
0101
0110

There are three 1’s in the external slots. Inverting a word may change that number by two, or keep it the same. Reversing a word will not change the number of 1’s. Therefore, the number of 1’s must always be odd. But since each intersection in a solved puzzle must have one up and one down slot, there must be exactly six 1’s in external slots in a solved puzzle. Thus, the puzzle is unsolvable. (However, if we had two copies of each piece, we could possibly make two stars of David by swapping pieces between the sets. This gives us a second challenge for the set above. It’s starting to look like a keeper!)

Stepping away from crossed stick puzzles, it turns out that all of the fun things that you can do with binary words can be done with these symmetry variants. And when I think of fun things you can do with binary words, I think of de Bruijn sequences and Gray Codes! But this post has gotten long enough already; that will have to wait for another post.

Crossed Stick Addendum

December 9th, 2012

Here’s another configuration of segments that could work in a crossed stick puzzle:

Conveniently, all of the pieces meet at 60° angles, so if I make a puzzle using this, I won’t need to use a slot design that admits multiple angles as in the one in the previous post.

A related configuration with three intersections per piece can be formed by clipping the outer points of this configuration. Are there any more crossed stick configurations that I’ve missed?

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.