Category: Zapped Puzzles

Polysticks and Polyominoes, Together at Last

~ munizao ~ Leave a comment

Back in my 11th post on this blog, I posed a problem involving tiling a figure with tetrominoes, and then tiling the edges of the tetrominoes with tetrasticks. Now I’m on my — well, look at that. This is my 100th post here! Anyway, recently I was playing around with Jaap Scherphuis’ PolySolver program, looking to see if there were any of my old problems that it could solve, and that one looked like a good fit. It turned out to have a unique solution, according to the solver.

As it happened, this problem was already at the front of my mind, after meeting William Waite of puzzlemist.com at Gathering 4 Gardner 15 this February. He gave me a copy of a combined polyomino/polystick puzzle he designed after a previous conversation at a G4G where I mentioned the problem above.

I think it’s worth examining how this puzzle differs from my take on the type, and why. I used a complete set of tetrasticks, and the closest thing I could get to a complete set of polyominoes, doubling up on tetrominoes and throwing in a monomino hole only because one of the tetrasticks required it. It’s just my aesthetic as a polyomino problemist to want to use complete sets when I can. Waite has a different objective; this was a puzzle produced for sale, with the object of the customer feeling that they got good value for the purchase price. Thus, where I didn’t care if the puzzle required computer assistance to solve, Waite wants a human puzzler to have a good chance of getting there on their own.

Because of this, both the polyomino set and the polystick set consist of easier pieces to tile. The polyominoes are the full set of 2–4-ominoes, which is at least as nice of a set as what I chose. The polysticks, however, are a mix of 3-sticks and 4-sticks, and neither set is complete. The polystick pieces seem to have been chosen for ease of tiling. The qualities that would make a more tilable piece are having little symmetry, having a smaller bounding box, and having a shape that fits nicely on the edges of the board. These pieces all have at least one of these features. The puzzle claims to have 4326 solutions, so finding one of them should be tractable.

Having a single unique solution doesn’t make a problem better than any other, but it does seem like a remarkable occurrence. Doubly so when lightning strikes again near another instance. Here I adjusted the shape from the first problem to one that had biaxial symmetry rather than quarter-turn rotation symmetry. This too has a unique solution!

Three paths to pick from, part 2: Distant connections

~ munizao ~ Leave a comment

I promised two more path puzzles in part 1, and their time has come. When I posted recently about “starmaps” as a variation on edgematching puzzles, my variation there was actually the second puzzle inspired by them that I had found recently. The first was this set of 2×2 square tiles with one cell being marked with 2 orthogonal or diagonal arrows. (The tiles can be flipped.)

Part of the inspiration to use arrows may have come from the game of Trippples, [siccc] which uses a complete set of fixed square pieces with arrows in three directions. I recently read about Trippples in issue 7 of Abstract Games magazine. Once I had these squares with arrows, a puzzle challenge seemed natural: connect the arrows into a single path, which may not enter any cell with arrows in any direction that does not correspond to an arrow.

Problem 61: Find a closed circuit using these pieces. I spent enough time finding the path above; I suspect that a closed circuit may be solvable if you have the patience of a Lewis Patterson, which I do not.

One element I like to consider in puzzle design is non-locality. A puzzle exhibits non-locality if, when you are placing a piece, you must consider pieces that are not immediately adjacent. Most polyform and edgematching puzzles are generally local. If half of a puzzle frame is filled, pieces in the interior of the filled region do not directly affect how new pieces can connect to the edge of that region. (Of course, I am eliding the fact that they reduce the set of remaining pieces that are available to place.) In the above puzzle, the empty space allows long distance connections, turning path-making into a non-local problem.

My Color Tubes puzzle from my Edge Collection Connection set of edgematching card puzzles was also a path puzzle with non-local considerations. I neglected to introduce it on the blog back when I produced the set, so let’s remedy that now.

The configuration shown is a solution to the challenge of placing the pieces so that each tube has three segments of three different colors. Segments can break in the middle of a card, or at a connection across a card boundary with non-matching colors. (Here, the cards cannot be flipped over; the back sides of the cards contain a second, related puzzle.) Other challenges for the cards are placing them so there are two differently colored segments, or four. This was definitely more of a “designed” puzzle than a “discovered” puzzle, which was a bit of a departure for me. I’ll have another excuse to muse about the distinction in a future post, but at this point I’ve hinted at more than one future post, so they can’t all be the next one.

With a couple of instances of non-locality under our belts, can we say anything useful about it as a puzzle design tool? In the case of Color Tubes, I think it gives it a little more depth than a typical 3×3 edgematching puzzle, which would seem to be welcome. In the arrow path puzzle, it adds difficulty and complexity, but the result is a little too much difficulty and complexity, at least for my tastes. It is a spice that should be judiciously applied. But then, so is hinting at coming posts, and that won’t stop me from teasing more material about non-local puzzles in the near future!

Three paths to pick from, part 1: A compact gem

~ munizao ~ Leave a comment

I’m going to be sharing a few different puzzles I’ve discovered that share the theme of path building. The first is a pretty polyiamond puzzle I recently prototyped; the other two have been split into a second post.

Path puzzles are a natural extension of edge matching. Instead of just marking edges in some way so that we can match like markings, we can choose and connect any pair of edges. Then we can make challenges involving the paths spanning multiple tiles that are formed. I’ve examined cell markings on polyforms a fair amount here, but I’ve left edge markings understudied. One reason is that the combinatorial explosion of possibilities can become overwhelming. The L-tetromino (to pick a simple asymmetric example) has 16 different cell markings if each cell can either be marked or not. Kadon sells this set in an 8×8 square frame as L-Sixteen. Since the L-tetromino has 10 edge segments, there are 2^10 = 1024 different markings if we do the same with the edges. If someone made this, it’d need a 64×64 square frame!

Cell markings also work for path puzzles! (Adapted from here.) Not shown: 4096 square unit monstrosity.

It’s probably little surprise then that most puzzles involving edge markings use simple squares or hexagons. But recently, when I was looking for something to do with diamonds and triamonds, I found a nice set for a path puzzle.

But first, an aside on why I was looking at diamonds and triamonds. My recent puzzles with row and column pip sum challenges used multiple copies of small polyominoes with different markings. The ability to exchange copies of the same shape usefully inflates the size of the search spaces for those puzzles. But tile placement remains an important aspect, even if the finding a tiling is easy, so it still has the feel of a polyform puzzle. In a sense, these puzzles “punch above their weight” in terms of the amount of puzzle you get for the size. I wanted to find other puzzles like this, and started to look at polyiamonds. For small polyiamonds, a hexagon of side length 2 seemed like the ideal frame.

There are a number of ways to divide up the 24 cells of that hexagon, but 3 diamonds and 6 triamonds was a top candidate. I tried magic pip sum puzzles first with mixed results, but then I checked the ways to connect edge segments and found that I got exactly 3 diamonds and 6 triamonds. And making paths with them is indeed a nice manual puzzle.

After I came up with this I was curious about which exits from the hexagon it is possible to get to from a given starting point. The darker triangles overlaid on that diagram give a clue: the number of transitions between dark and light squares must always be the same, however the pieces are placed. This means that the path must always enter and leave the hexagon at triangles of the same color, so only the positions marked 1, 4, 5, and 8 are possible exits if you start at the ★. Solutions do exist for each. (Positions marked with the same number give equivalent paths by symmetry.)

I later produced a lasercut acrylic prototype of the puzzle. Here it is:

One change I’d like to make for a production version would be to cut a circle in the frame around the hexagon so that the whole puzzle can be easily rotated, allowing the ends to match the symbols. As it is, you might find a solution that connects “wrong” edges, and it’s a pain to take the pieces out and put them back in the right orientation.

In future posts, I can promise not only more path puzzles, but also another “compact gem” of small polyform sets with big puzzling possibilities.

Cell Numbering Sums

~ munizao ~ Leave a comment

Before I started this blog, I explored polyominoes with cells individually labeled with numbers. I called these sumominoes, as I was looking at sets of all polyominoes with a given sum. Erich Friedman discovered them independently, and called them weightominoes in his July 2009 Math Magic Problem of the Month. I prefer his term for the general concept, as there is no reason they need to be grouped by sum. Both Friedman and I looked at problems where the goal was to overlap these polyominoes in a rectangle so that every cell had the same sum of labels. While I looked at a particular complete set, Friedman looked at pilings of multiple copies of the same cell numbered polyomino. (Aside: “pilings” isn’t a standard term, but it’s a concept we need a term for. We have “packings” for deficient tilings that don’t fill a space, so “pilings” for abundant tilings that fill it with overlap. Then a “tacking” is when there is both empty space and overlap, of course.)

All polyominoes with positive integer labels that sum to 4.

In this kind of problem we looked at sums of cells in the “z” direction. But we could instead look in the x and y directions. There is a common type of figure where we do this already: magic squares!

For this type of problem, excluding 0 as a potential cell label isn’t necessary. Standard numbered dominoes include 0 (blank) as a label, so we might want to do the same for physical puzzles using pips. (Pip patterns are preferable to numerals for physical puzzle pieces since they don’t have a preferred orientation.)

In fact, in the context of standard dominoes, examples have existed for some time. Here is a domino magic rectangle using a full set of double-six dominoes. The row sums are all 24, and the column sums are 21.

Solution from “The Existence of Domino Magic Squares and Rectangles”, by Michael Springfield and Wayne Goddard, graphic mine.

Of course, the fact that it can be done doesn’t make it a good puzzle, and working with a full set of dominoes might get tedious. Since I’ve been looking for simple puzzles with small piece sets, I tried to find one in this format. There are two cell numbered dominoes and four L-trominoes with a cell sum of 2. Their total area is 16, good for a 4×4 square,. and their total label sum is 12, giving a row and column sum of 3. One nice thing about a magic square type puzzle is you get an extra challenge for free. Finding a configuration with just row and column magic sums is a fairly light challenge, but getting the main diagonals to also match the magic sum is much harder. I had a small number of these made to give away at the 2022 MOVES conference:

Show Solution

Looking upward in size, there are 12 trominoes with a cell sum of 3, good for a 6×6 square with line sums of 6. I made a prototype:

But this isn’t quite as great as a puzzle, which is why I didn’t bother to conceal the solution as a spoiler. The reason is that it’s easy to make subunits where pip sums are preserved on applying a symmetry action. For example, in the solution above the three I trominoes in the upper left can be permuted in any order without changing row or column sums. Likewise, the two 2×3 rectangles formed from two L trominoes on the bottom can be flipped over one axis. This makes it much easier to turn a semimagic (row and column only) solution into one where the diagonals also work. (Subunits like these can appear in the smaller puzzles here, but there isn’t really enough room for them to dominate a solution.)

What I really want from going one step up from a 4×4 puzzle is a 5×5 one. Well, if we exclude the pieces with 3’s, we have an area of 24, which is almost right. We can make a 5×5, but it would have an unfortunate hole:

Or a fortunate one! Since my pips were lasered out holes to begin with, the big hole should clearly just count as one hole for the purpose of line sums. Now we have 25 holes, and 5 will work as the line sum. (While I normally like rounded corners for pieces since they have a softer tactile feel, if I made more of these, I’d use sharp corners and square pip holes, to visually unify the two different hole sizes.)

Show Solution

Is there anything else we can do with cell numbering? Polyhexes seem promising since there is an extra direction for sums to happen on. And perhaps we can use the numbers for something other than sums. I’m sure there are more creative discoveries waiting to be made!

The Pentominoes My Destination

~ munizao ~ Leave a comment

Usually, the pentominoes are the raw material of a problem, not its end point. Here are a couple of puzzles that turn the usual order on its head.

I.

With Gathering for Gardner 12 approaching in 2016, I was looking for things to do with the pentomino theme. (I’ve posted previously about my pentomino coloring talk and what led from it.) I had come up with a puzzle with 12 separate frames, each with space for a pentomino, and two sets of 12 puzzle pieces. Each set was in a different color, and the object of the puzzle was to fill all of the frames with two pieces of the same color. I made a copy out of lasercut wood, and brought it to the Gathering.

At the Gathering’s offsite “garden party” I commandeered a table a little bit away from the main crowd. (I have auditory sensitivity issues that become a problem in loud, crowded spaces.) I set out the pieces and frames, and hoped I would get some takers. I was incredibly lucky that one of them was none other than Richard K. Guy! I tended to be shy at these conferences about approaching the “old guard” who knew Martin Gardner as a peer. We have lost many of them, including Guy, John Horton Conway, Raymond Smullyan, and Solomon Golomb, in the years since this picture was taken. This was my only substantial interaction with Guy, and I’m very thankful to have the memory.

I discovered that a puzzle with multiple frames had very interesting effects on the collaborative dynamics of group solving. Everyone could pick a frame to work on separately, so there was no confusion as to which parts were “owned” by whom. Unused frames and pieces could be picked up by anyone without fear of stepping on anyone’s toes. Sometimes a player would require a piece that was already used in a different frame, and they would ask its owner for it. Everyone was working toward the same final goal, so they would always be willing to share. I saw the same patterns when three different groups worked on the puzzle that day, and I believe that the delineation of responsibilities that emerged from the multiple frames helped all of the players feel ownership of an important role in solving the puzzle.

Here is the set of pieces. The size of each piece is 2½ unit squares. I wanted to have two copies of six different pieces, but that didn’t work, so there are two singletons per set.

Although the puzzle as designed requires two pieces from the same set in each frame, an obvious alternate puzzle would be to have each frame use one piece of each set. I haven’t tried it though, so I don’t know if that challenge is a good puzzle, or even solvable.

II.

I’ve recently been looking for light puzzles with small piece sets that might make good exchange gifts for Gathering for Gardner. Taking the 1½- and 2½-ominoes and giving them every possible choice for marking any of the (full) cells with a square yields 6 pieces, with 5 squares, and an area of 13. Well, 5 squares means I’m going to have to do something with pentominoes. And an area of 13… well, that’s just awkward. But I was inspired by Tick Wang’s Tans Dance, along with other puzzles I saw on the Nothing Yet Designs site where the goal is not to make a particular shape, but to make any symmetrical shape.

And that’s the puzzle. Take these pieces and make a symmetrical shape (either rotation or reflection symmetry is fine) where the blue squares form a pentomino. Now do it again for the other 11 pentominoes. All of them are solvable! Most of them, individually, are not too hard, but with 12 challenges, it should keep someone busy for a few minutes.

What I like about this puzzle is that the symmetry goal makes the squareless pieces relevant, and including the squareless pieces makes the pieces a more complete and elegant set. Will it be my exchange gift for the next G4G? I think it’s too early to say yet. I try to pick an idea at about six months prior to the conference. This tends to give me a timeline where I have plenty of time for design, prototyping, ordering materials, and assembly, with some cushion if my first idea doesn’t pan out. I’ll still be on the lookout for more good light puzzles. After all, having lots of ideas to choose from for one’s exchange gift is the best way to ensure you find a really good one!

(A final aside: you might notice that there are two ways to make a half-omino. You can cut parallel to the grid, as I did for both of these puzzles, or you can cut a square diagonally. For the first puzzle, diagonal cuts were out, because the T pentomino cannot then be split into two 2½-ominoes. For the second puzzle, I considered diagonal cuts first. That version of the puzzle does actually also work, but often, you get to a point where you have the puzzle basically solved, but you have to do some fiddly piece flipping so that the right triangle ends give a symmetric figure.)

The Rune Where It Happens

~ munizao ~ 4 Comments

A while back, I was finalizing my drawing files for laser-cut frames for my Cross Products puzzles, which I was intending to sell at Gathering for Gardner 13. I wasn’t happy with just wasting the material in the center of the frames, so I looked for a simple idea that would make use of it. The shape that was being cut out was a rectangle with a 3:4 aspect ratio. I could cut that into 12 squares, and then engrave something on each of them. Now what might there be 12 of?

It will probably not surprise anyone here that my mind went straight to the pentominoes. Tiles with pentominoes could be useful for choosing one at random. (Sure, I already owned a 12-sided die with the pentominoes on it, which I bought from Eric Harshbarger, but with tiles one could select without replacement, or even effectively shuffle an ordering of the entire set.)

The tiles I made for my G4G13 exchange gift didn’t have these fancy swirled colors.

The tiles reminded me of rune stones, with the pentominoes forming a cryptic alphabet. I thought it would be amusing to make sets of them my exchange gift for G4G13, along with a slip that instructed the user on how to use the arcane power of the pentominoes to divine the future. It would be the kind of playful deadpan jab at ungrounded mysticism that Gardner’s alter ego, Dr. Matrix, might have enjoyed making. But to really justify the effort, it couldn’t be just that. I’d need to include some activity using the pieces that would have genuine recreational math interest. Perhaps a puzzle.

What I found was a variation on the common superform framework that incorporated squares with pentomino runes. The basic common superform problem is to find a figure into which any of the polyforms in a set can be placed. Usually, the object is to minimize the area of such a figure, but in this case, the area will be set by each particular challenge using the pieces. We add a couple of restrictions:

  • Each set of five tiles that forms a pentomino must contain the corresponding rune.
  • Each rune must be contained in at least one set of tiles that forms that pentomino.

The above figure was included as an example on the instruction sheet. The challenges provided were to find a valid tile arrangement using nine of the tiles, to do so with all of the tiles but one, and to do so with the complete set. Remarkably, this is possible!

Show Solution

I’ve since looked for other sets of polyforms that are able to make valid rune configurations with a complete set. Here are the tri-diamonds:

And here are the tetrahexes:

Can you find others?

Incidentally, at G4G13, I gave a few pentomino readings to fellow conference goers, one of whom reacted with cheerful amusement, and another with stony skepticism. Honestly, I could not have hoped for anything better.

The Devil’s in the Angles

~ munizao ~ Leave a comment

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

~ munizao ~ 2 Comments

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.

Isolating small pieces: submitted solutions

~ munizao ~ 1 Comment

A couple of submitted solutions on the theme of isolating small pieces in tilings of polyominoes of mixed sizes:

George Sicherman solved problem #44. (Tile a certain torus with the 1–5-ominoes such that the 1–4-ominoes do not touch each other. Finding a solution where none of the smaller pieces even meet at corners was optional, but well appreciated!) This solution contains four “crossroads”, or points where four polyominoes meet. These are sometimes considered an aesthetic flaw in a polyomino tiling, and whether or not you agree with that, finding solutions without them tends to be good for an extra challenge.

Problem #44a: find a solution for problem #44 without crossroads.

Jaap Scherphuis analyzed this challenge that was included with my Agincourt puzzle: find a tiling of an 8×8 square where none of the dominoes and trominoes touch each other or the outer edge. He found that there were 32 solutions. In just one of these, none of the smaller pieces meet at a corner:

I don’t feel that I acknowledge other puzzle creators enough in this space, so I want to give a shout out to Kadon for their Mini-Iamond Ring puzzle, which contains all of the 2–5-iamonds, and includes as a challenge isolating all of the different sizes of pieces:

Magic figures from crossed stick configurations

~ munizao ~ Leave a comment

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: Compatibility Variations

~ munizao ~ Leave a comment

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

~ munizao ~ Leave a comment

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

~ munizao ~ 1 Comment

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

~ munizao ~ Leave a comment

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

~ munizao ~ Leave a comment

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.