Wanderings on a Six-Sided Die

August 27th, 2010 by munizao 1 comment »

Here’s a little doodle on a grid based on a standard six-sided die:

I started by deciding that the pip positions should all connect North to south and East to West. It followed logically that I could have a puzzle where the solver could choose one of two possibilities for each empty cell: connecting North to West and South to East, or North to East and South to West. Because there are 33 non-pip squares, there would therefore be 233=8,589,934,592 ways to fill the grid. The lines on the outside of the grid show how the squares would connect when folded into a cube.

As an exercise, I found a way to make a single circuit, which is shown above. While that turned out to be about the difficulty of puzzle I can handle in something I am solving by hand, I’m sure there are more interesting specimens to be found.

Unfortunately, because the number of pips is odd, it’s impossible to have two circuits where each go through all of the pips. The circuits would have to cross each other an even number of times. But we could have one of the circuits cross itself once, and then have both circuits go through the remaining 20 pips. (Let’s call that problem number, oh what are we on, #12. By the way, the problem numbers are so that I can keep track of solvers of numbered problems and give them the fame they deserve. Nobody has solved any yet. You can be the first!)

Another possibility would be to use three circuits, each crossing itself once, and each visiting 12 pips in addition to the self-crossing. That’s #13.

I like big, wide ranging circuits here, so a constraint I like is to have circuits that visit all 6 sides. So bonus points on the preceding problem for having all three circuits do that. And that suggests #14: Maximize the number of circuits in a solution where all circuits present visit all 6 sides.

I thought early on that I could take this in the direction of a knot theoretical puzzle, but then one would have to keep track of which thread went under which in the crossings, which seemed like an unnecessary complication. I also think it would be interesting to make a multi-state maze (See Robert Abbott’s site for some good examples) using this template, but I haven’t yet had any good ideas for how that would work. If you have a good idea for a variation on this puzzle, I’d love to hear it. (This is of course true for all of my puzzles.)

For your solving convenience, I have an empty grid image here, and the Inkscape SVG file I used to produce it and the image above is here.

Make All Sad at TWIFcomp

April 26th, 2010 by munizao No comments »

TWIFcomp is a competition for works of interactive fiction with source code not exceeding the length of a tweet. (Unlike on Twitter, whitespace characters do not count toward the total.) There were 61 entries, of which the largest proportion were in Inform 7. My entry, Make All Sad was written in perl. If you really insist on playing it unspoiled, and you have perl installed, you should go there before reading any further.

Aaron A. Reed at >TILT AT WINDMILLS has a good post highlighting a selection of the games. The space of 140 characters really only suffices for one gag, but a pretty wide variety of gags were tried. Adam Thornton gets a special, “if they ever do this again there will have to be a new rule” award for encoding a full length game that’s been years in the making as several hundred megabytes of whitespace characters, with a short perl script to decode it. (Assuming that gets a normal release soon, I’m looking forward to playing it.)

Choosing to use perl instead of a dedicated IF language meant I didn’t get a parser, world model, built in verbs, or even a prompt for free. (I spent 9 characters on the “>” prompt, which was extravagant, but I felt it necessary to give my game the feel of IF.) I do however get text mangling for cheap, and a good set of general programming operators.

My first important design decision was that I was not going to attempt to parse input, but would instead map the length of the input to the effect. This way, you could type any normal IF command, (“TAKE ROCK”, “GO NORTH”, etc.) and it would have an effect on the game, giving the illusion that there is a parser doing something there. (For the sake of having a better way to leave the game than CTRL-C, I did catch just one command: QUIT.)

The other piece of the puzzle was creating something not utterly trivial to do with this piece of information. I settled on having a set of three “objects” and a set of three possible adjectives, with a goal of getting all of the adjectives into a particular state. The game would print “The x is y.” for each object and its current adjective. (In the end, I could find no other way to excise the last character I needed to get down to 140 but to change “The” into “My”. I’m actually happy with that; this way feels more flavorful and implies an NPC behind the words.) Saving characters by having the nouns and adjectives share their final letters was an idea I had before I started coding, and gives the output a bit of visual poetry.

Finally, I needed a function to map the input length to the effect. I wanted different lengths to do different things to the three adjectives, sometimes changing all three, sometimes keeping some of them the same. And I needed something extremely terse. The shift operator “>>” saved me here. The function has period 12, so “MAKE ALL SAD” (12 characters) has no game effect. As a fortuitous coincidence, none of the 12 possibilities can win the game in a single turn.

The rest was perl golf, as the pastime of writing perl programs in as few (key)strokes as possible is called. There is a primer here that gave me some helpful ideas. In standard perl golf, whitespace counts; since it didn’t here, initializing the noun/adjective array by splitting on the space character was a win.

If I had a few more characters, I would have liked to end the game with a victory message in the event of all being sad. But I’m reasonably happy with how it turned out.

The source:
@o = split ' ', 'ma cu to sa re od';
@s = 0..2;
do
{
    map
    {
        $a = $s[$_] += $x >> $_;
        printf "My %sp is %sd.
", $o[$_], $o[$a % 3 + 3]
    } 0..2;
    print ">";
    $_ = <>;
    $x = y///c - 1
}
until /quit/i

Edit: Naturally, after the competition deadline and after I wrote up this post, I found a couple good ways to squeeze out a bunch of characters, and a feature I could add that could fit into the extra space. The new feature is that “G”, the standard abbreviation for AGAIN in IF, repeats the last command. This only took 11 characters to achieve.

The code for the new (and hopefully final) version follows:

@o = split ' ', 'ma cu to sa re od';
@s = 0..2;
do
{
    print "My $o[$_]p is $o[($s[$_] += $x >> $_)  % 3 + 3]d.
" for 0..2;
    print ">";
    $_ = <>;
    ! /^g$/i && ($x = y///c - 1)
}
until /^quit$/i

Gordon Hamilton’s Polyanimal Zoo

April 6th, 2010 by munizao No comments »

Here’s a problem that I heard from Gordon Hamilton at Gathering for Gardner 9, and tracked down to an article of his in issue #10 of Pi in the Sky, a western Canadian math magazine for high school students and teachers.

A polyomino animal can eat another polyomino animal (his perhaps overly cute term is “polyanimal”) if the second one can be placed inside the first. Find animals of sizes 4, 5, 6, 7, 8, 9, and 10 that can live together peacefully (none can eat any of the others) within a 7×7 square pen.

This is really a satisfying puzzle to solve. Usually in polyform tiling puzzles, you spend a fair amount of time feeling out the territory, learning which pieces like to go in certain places, and which you want to deal with first and which you want to save for the end. But then, the larger part of the solving time is spent in trial and error with various configurations attempted at random until at last you run into a solution.

Here, the whole solving process is learning about the territory of the puzzle, and none of it feels like random crunching. I highly recommend giving it a try, but if you just want to see a solution, mine is here.

Of course, the matter of polyominoes fitting inside other polyominoes is an area that I’ve dealt with in my Polyomino Cover material, which I summarized in my presentation for G4G9. And one of the problems in Hamilton’s Polyanimal problem set is the same as what I’ve called the minimal pentomino cover problem. But most of them are completely different, which only reinforces my belief that this is an area with a lot more waiting to be discovered. (His last problem is “Design a Polyanimal Game.” Now that’s open-ended and provocative!)

Pentomino Cover Cycles

March 17th, 2010 by munizao No comments »

What’s the smallest shape into which any of the 12 pentominoes can be placed? I call this old chestnut the “minimal pentomino cover” problem, and I’ve spent a lot of time working on a number of variations on it. For the purpose of introducing and illustrating the basic problem to my dear readers, I wanted to use an animated GIF file showing all of the pentominoes in turn being placed on a minimal cover.

An aesthetically pleasing way to cycle through the pentominoes would be to move one square at a time. This is in fact possible:

A couple of variations on the problem of finding such a cycle suggest themselves:

#9: Minimize the total distance the squares move per cycle. The taxicab metric seems to be more sensible and simpler than Euclidean distances here. I made no attempt to do any minimization in the above solution, so I’m sure there is room for improvement.

#10: If you gave every square in the pentominoes a distinct color, and kept the color the same when a square moved, you could keep track of where the squares end up at the end of a cycle. During the cycle illustrated above, two pairs of squares switch places. Is there a cycle of single-square moves through the pentominoes that ends with each square in the same place it began?

Notice that the central square can never move, because the only pentomino placement without the central square is one of the P pentomino, for which the only valid square movements turn it into a U pentomino. It would need movements to two different pentominoes to be part of a cycle.

For both of the above problems, the other 9 square pentomino cover would also be a valid substrate:

Since this one has no immobile squares, another problem using it may be solvable:

#11: Find a cycle where the permutation of the squares from one cycle to the next is cyclic (in the second sense in the linked article.) That is, successive iterations of the cycle will eventually take each square in a pentomino to all of the other positions in that pentomino.


Some very good news: I’ve been invited to the 9th Gathering for Gardner conference in Atlanta later this month. The Gathering for Gardner is an invitation-only conference  held in honor of Martin Gardner, who brought recreational mathematics to a generation through his columns in Scientific American. That generation was not my generation, but it was impossible to miss his imprint on later writers, and I’ve picked up used copies of several of the collections of his columns. A large proportion of the names on the spines on my recreational mathematics bookshelf are represented among the invitees, so this will be really special for me.

Pentomino Layer Cake

February 27th, 2010 by munizao 3 comments »

On the Polyforms list, Erich Friedman posed a very interesting new pentomino tiling problem:

Tile a rectangle of minimal area with pentominoes so that for each pentomino there is exactly one stratum, or cluster of one or more copies of that pentomino that reaches from one side of the rectangle to the opposite side. Pentominoes in a stratum must form a single group, connected by edges, not just corners.

Michael Reid found this 3×30 solution:

It’s not hard to prove that it is minimal. A natural extension of the problem is to find minimal solutions for 4×n and 5×n rectangles. Michael Reid found the first 5×n solution, but I improved on it with this 5×32 solution:

The 4×n problem seems to be the hardest, and initially it was not clear that it would be possible. The X pentomino has only one possible stratum, which only can only be bordered by Y, I or N, and it is also difficult to find matches for a Z stratum. Additionally, only Y, L, and P can form straight line stratum boundaries usable for the top and bottom of the rectangle. (See wikipedia’s pentomino page if you don’t know the correspondence between letters and shapes.) I did eventually find this 4×50 solution:

This solution seems rather prolifigate with its pentominoes, but finding any solution at all was a bit of a surprise.

Introducing Agincourt (to the Blog)

February 25th, 2010 by munizao No comments »

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.

Holy Hyperbolic Heptagons!

February 19th, 2010 by munizao No comments »

Recently, MathPuzzle highlighted a program called MagicTile for playing with Rubik’s Cube variants on various tessellations in spherical, Euclidean, and hyperbolic geometries. One interesting hyperbolic tessellation is the {7, 3} tessellation, composed of heptagons, with three meeting at every corner. Twenty-four of these heptagons can be wrapped up into a genus-3 (that is, topologically like a torus but with three loops instead of one) “Platonic solid” called Klein’s Quartic, which John Baez has a fascinating page about.

Polyforms based on hyperbolic tessellations appear to be a relatively unexplored area. I’ve come across a couple of references on counting the n-cell polyforms for a given tessellation, but I haven’t found evidence that anyone has actually used them for puzzles. So I set myself this one. There are ten tetrahepts on the {7, 3} tessellation. Could they tile two copies of the same shape?

An implicit constraint in my solution of this problem was that the shapes could extend no farther than the second ring around a central heptagon. I searched for a solution using plastic game counters that would not have fit on any heptagons farther out on the diagrams I used as solving boards. I also knew that I was going to make images to show on my blog, and they would be clearer if there were no relatively tiny heptagons in the solution. In fact, the decision to find a puzzle in two pieces was affected by the observation that using an extra Poincaré disk would remove the need to use the tiny outer heptagons.

This was a pretty difficult puzzle to solve by hand, so I feel like I’m being a little mean using an even harder, (and perhaps impossible) variant as the numbered puzzle for this post:

#8: Find a symmetrical shape for which two copies can be tiled by the ten {7, 3}-tetrahepts. In addition to mirror symmetry, 180° rotational symmetry around the midpoint of an edge could work. (The other modes of rotational symmetry of the tessellation won’t work for a 20 cell shape.)

I would also love to see what other puzzles people can come up with on this or any other hyperbolic tessellation.

Hexiamonds on an Octahedron

January 26th, 2010 by munizao No comments »

Here’s an interesting problem that seems not to have gotten as much attention as I think it deserves. The twelve hexiamonds contain a total of 72 triangular units. A regular octahedron with edges 3 units long can fit 9 triangles on each of its 8 faces, exactly enough to tile with the hexiamonds. Some individual solutions to this problem have been found. A solution at Livio Zucca’s site bears the label “Adrian Struyk 1963?” so we may assume the problem has been around at least since then. Another solution by Michael Dowle is here.

Notice that you can unfold an octahedron to produce a net in the form of an octiamond. This provides another source for solutions. The octahedron has 11 different octiamond nets. Pieter Torbijn found that 24 enlarged octiamonds could be tiled with the hexiamonds; of these, 5 are nets of an octahedron.

As far as I know, nobody has made an exhaustive computerized search for solutions to this problem. You can be the first!

#4: How many distinct ways can the hexiamonds tile an octahedron?

The octahedron has a large amount of symmetry compared to any planar figure that these pieces can tile. It has 48 automorphisms, or ways to map the solid onto itself. This would indicate a relatively small number of different solutions, since many solutions will be mappings of each other over the various ways of rotating and reflecting the octahedron. On the other hand, the shape lacks external borders, which ought to greatly increase the number of possibilities.

Some solutions have a piece that wraps around and caps a vertex. This could be considered an aesthetic flaw, because it would be impossible to tell which hexiamond the capping piece is just from knowing what triangles it occupies; you must also know its edges.

There are 7 different pieces that can cap a vertex, one of which, the pistol, can cap it in two distinct ways. Notice that due to the symmetry of the shape it makes when it caps a vertex, only the orientation of the sphinx is a riddle; its identity is never in question.


#5: How many solutions have a capped vertex?

#6: What is the largest number of vertices that can be capped in a solution? The ideal would be for all six vertices to be capped with all of the above hexiamonds except the sphinx.

The octahedron has twelve edges, the same as the number of hexiamonds. This suggests another problem:

#7: Is it possible to tile the octahedron so that each of the twelve hexiamonds is folded across exactly one of the edges of the octahedron?

2-coloring Pentomino Packings

January 24th, 2010 by munizao 1 comment »

I like to collect pentomino coloring problems.

So it should come as little surprise that I was intrigued by the cover of Puzzle Fun 16. Puzzle Fun was a ‘zine produced by Rodolfo Marcelo Kurchan in the ’90s covering a variety of polyomino problems. I missed out on subscribing to it myself, and the Puzzle Fun website languished for a decade after new issues stopped appearing.

A few months ago, Kurchan put the content of all of the back issues of Puzzle Fun online.

Puzzle Fun 16 focused on pentomino packing problems. Packing problems differ from tiling problems in that empty space is allowed, and the goal is to minimize the amount of empty space required. Packing, usefully, makes some kinds of problems possible to solve that would not be solvable as tiling problems.

One such puzzle type is packing polyforms that are 2-colorable, (that is, one can use two colors to color every piece such that no piece touches another of the same color.) This is the puzzle type I saw on the cover of Puzzle Fun 16.

The problem itself was this: Place two sets of pentominoes in the smallest possible rectangle such that no pentomino touches another in the same set. [PF problem #549]

A solution was printed in Puzzle Fun 18:

(Solution by Hector San Segundo.)

I should note that this problem implies strict coloring: pieces are not allowed to touch even at corners. I am more interested in non-strict coloring, which is generally the default in coloring problems, and I am interested in colorings of a single set of pentominoes. (Which all of the problems on my pentomino coloring page are.)

#1: Place a 2-colorable (non-strict coloring) set of pentominoes in the smallest possible rectangle. My best attempt has 65 squares:

Filling out the matrix of variations gives two more problems:

#2: As #1, but with a strict coloring.

#3: As in PF #549, but with a non-strict coloring.

(The following problem in PF 16 (#550) was a variation on #549 minimizing perimeter rather than area, but this is less interesting to me.)

http://www.puzzlefun.com.ar/

Welcome!

January 20th, 2010 by munizao No comments »

I’ve been playing with polyominoes and other recreational math topics for quite a while, and sharing my results on an email list, and on my own website. It has occurred to me that this is the 21st century, and I should get a public blog for this material. Also, since I am now selling puzzles that I’ve designed and made, having a blog may, I hope, be a way of generating interest in them so that I can make and sell more.

Other subjects that I judge may be interesting to the same sorts of people who are into recreational math, (like interactive fiction writing, which I’ve been meaning to get back into) may come up here too. We’ll just have to see where this leads.