Sliding Block Puzzles, Part 3

This article may as well be part of a series: 1 2(read this first)

Additional notes: ‘Simple simple simple’ is referred to as this post as simple^3,

Warning: This article contains original research! (It’s also more papery than most of the other articles on this site)

In the previous post I mentioned several methods that could be used to speed up the finding and exhaustive searching of sliding block puzzles, as well as a candidate for the ‘hardest’ one-piece-goal diagonal-traverse 4×4 sliding block puzzle. I am pleased to say that the various bugs have been worked out of the sliding block puzzle searcher, and that 132 has been confirmed to be the maximum number of moves for a simple simple simple 4×4 sliding block puzzle with no internal walls!

(that’s not a lot of qualifiers at all)

As the reader may expect, this blog post will report the main results from the 4×4 search. Additionally, I’ll go over precisely how the algorithms very briefly mentioned in the previous post work, and some estimated running times for various methods. Following that, various metrics for determining the difficulty of a SBP will be discussed, and a new metric will be introduced which, while it is slow and tricky to implement, is expected to give results actually corresponding to the difficulty as measured by a human.

Search Results

Running SBPSearcher on all the 4x4s takes about 3 hours (processing 12295564 puzzles), which was quite useful for fixing hidden bugs in the search algorithm. Here are the best simple^3 4×4 n-piece SBPs, where n goes from 1 to 15:

For those of you with a text-only web browser, your lucky numbers are: 1,4,9,19,36,51,62,89,132,81,64,73,61,25,21
Click to view in full size

And for comparison, the move counts vs. the previously reported move counts:

   1   4   9  19  36  51  62  89 132  81  64  73  61  25  21
   1   4   9  24  36  52  68  90 132  81  64  73  61  25  21

    Notice that all the entries in the top row of the table are either less than or equal to their respective entry in the bottom row of the table, some (such as in the case of p=7 or p=4) being much less This is because the previous search (run, in fact, as a subfeature in the sliding block puzzle evolver) started with all possible positions and defined the goal piece to be the first piece encountered going left to right, top to bottom, across the board. As such, the search included both all the 4×4 simple^3 sliding block puzzles as well as a peculiar subclass of sliding block puzzles where the upper-left square is empty but the goal piece is often a single square away! This accounts for the 6-piece case and the 8-piece case (in which the first move is to move the goal piece to the upper-left), but what about  the other two cases?

    For the 4-piece case, the originally reported puzzle (see here for the whole list) wasn’t simple^3, and it isn’t possible to convert it into a simple^3 SBP by shifting blocks in less than 5 moves. Interestingly, the new ‘best’ puzzle for 4 pieces is just James Stephens’ Simplicity with a few blocks shifted, a different goal piece, and a different goal position! (There could be copyright issues, so unless stated, the puzzles in this article are public domain except for the one in the upper-right corner of this image) Additionally, the 7-piece 68-move puzzle in the previous article is impossible to solve! The upper-left triomino should be flipped vertically in place. I expect this to have been a typing error, but the question still stands: Why is there a 6-move difference?

    As mentioned before, the actual stating of what constitutes a simple simple simple puzzle is as such: “A sliding block puzzle where the piece to be moved to the goal is in the upper-left corner, and the goal is to move the goal piece to the lower-right corner of the board”. Unfortunately, there’s some ambiguity as to when a piece is in the lower-right corner of the board – is it when the lower-right cell is taken up by a cell in the goal piece, or is it when the goal piece is as far to the lower-right as it can be? If we take the latter to be the definition, then additional ambiguities pop up when faced with certain problems, such as the following one often encountered by SBPSearcher:

0000000001110102
Which piece has just moved into the lower-right?

Because of problems like these, SBPSearcher uses the former definition, which means that puzzles where the goal piece takes the shape of an R aren’t processed. (In actuality, it’s SBPFinder that does this checking, when it checks if a puzzle is in the ‘justsolved’ state). If we say that the first definition is stricter than the second, then it could be said that SBPSearcher searched only through the “Strict simple simple simple 4×4 Sliding Block Puzzles”. While I don’t think that any of the results would change other than the p=7 case, it would probably be worth it to modify a version of SBPSearcher so that it works with non-strict simple simple simple sliding block puzzles.

A few last interesting things: The 13-piece case appears to be almost exactly the same as the Time puzzle, listed in Hordern’s book as D50-59! (See also its entry in Rob Stegmann’s collection) Additionally, the same split-a-piece-and-rearrange-the-pieces-gives-you-extra-moves effect is still present, if only because of the chosen metric.

The Algorithm, In Slightly More Detail Than Last Time

There are only two ‘neat’ algorithms contained in the entire SBP collection of programs, these two in SBPFinder and SBPSearcher respectively. The first of them is used to find all possible sliding block puzzle ‘justsolved’ positions that fit in an NxM grid, and runs in approximately O(2*3^(N+M-2)*4^((N-1)*(M-1))) time. (Empirical guess; Due to the nature of the algorithm, the calculation of the running time is probably very hairy).

First of all, the grid is numbered like this:

 0  1  3  6 10
 2  4  7 11 15
 5  8 12 16 19
 9 13 17 20 22
14 18 21 23 24

where the numbers increase going from top-right to lower-left, and moving to the next column over every time the path hits the left or bottom edges. (Technical note: For square grids, the formula x+y<N?TriangleNumber(x + y + 1) – x- 1:N*M – TriangleNumber(N + M- x – y – 1) + N – x – 1 should generate this array)

Then, the algorithm starts at cell #0, and does the following:

Given a partially filled board: (at cell 0 this board is all holes)

  1. Take all the values of the cells from (cell_number-1) to the number of the cell to the left of me, and put that in list A.
  2. Remove all duplicates from A.
  3. If the following values do not exist in A, add them:  0 (aka a hole) and the smallest value between 1 and 4 inclusive that does not exist in A (if there is no smallest value between 1 and 4, don’t add anything except the 0)
  4. Run fillboard (that is, the current function), giving it cell_number+1 and the board given to this level of the function with the value of cell_number changed to n, for each value n in A.

However, if the board is all filled (i.e, cell_number=25) , check to see that the board has holes and that it is justsolved, and if so, standardize the piece numbering and make sure that you haven’t encountered it before, and if so, sort the board into the appropriate piece number “box”.

Once the fillboard algorithm finishes, you should have N*M-1 boxes with all the possible justsolved positions that can be made on an N*M grid! There are a number of other possible methods that do the same thing- all it basically needs to do is generate all possible ways that pieces fitting in an NxM grid can be placed in a grid of the same size.

For example, you could potentially go through all possible 5-colorings of the grid (4-colors and holes), and remove duplicates, but that would take O(5^(N*M)) time, which isn’t the most feasible option for even a 4×4 grid.  You could also proceed in a way that would generate the results for the next number of pieces based on the results of the current number of pieces and all possible rotations and positions of a single piece in an NxM grid by seeing which pieces can be added to the results of the current stage, but that would take O(single_piece_results*all_justsolved_results). While that number may seem small, taking into account the actual numbers for a 4×4 grid (single_piece_results=11505 and all_justsolved_results=12295564) reveals the expected running time to be about the same as the slow 5-coloring method. However, it may be possible to speed up this method using various tricks of reducing which pieces need to be checked as to if they can be added. Lastly, one could go through all possibilities of edges separating pieces, and then figuring out which shapes are holes. The time for this would be somewhere between O(2^(3NM-N-M)) and O(2^(2NM-N-M)), the first being clearly infeasible and the second being much too plausible for a 4×4 grid.

In practice, the fillboard algorithm needs to check about 1.5 times the estimated number of boards to make sure it hasn’t found them before, resulting in about half a billion hash table lookups for a 4×4 grid.

The second algorithm, which SBPSearcher is almost completely composed of, is much simpler! Starting from a list of all justsolved puzzles (which can be generated by the fillboard algorithm), the following is run for each board in the list:

  1. Run a diameter search from the current puzzle to find which other positions in the current puzzle’s graph have the goal piece in the same position;
  2. Remove the results from step 1 from the list;
  3. Run another diameter search from all the positions from step 1 (i.e consider all positions from step 1 to be 0 moves away from the start and work from there), and return the last position found where the goal piece is in the upper-left.

Step 2 is really where the speedup happens- Because each puzzle has a graph of positions that can be reached from it, and some of these positions are also in the big list of puzzles to be processed, you can find the puzzle furthest away from any of the goal positions by just searching away from them. Then, because the entire group has been solved, you don’t need to solve the group again for each of the other goal positions in it and those can be removed from the list. For a 4×4 board, the search can be done in 3 hours, 27 minutes on one thread on a computer with a Core I7-2600 @3.4 Ghz and a reasonable amount of memory. In total, the entire thing, finding puzzles and searching through all of the results, can be done in about 4 hours.

Of course, where there are algorithms, there are also problems that mess up the algorithms- for example, how would it be possible to modify SBPSearcher’s algorithm to do, say, simple simple puzzles? Or, is it possible to have the fillboard algorithm work with boards with internal walls or boards in weird shapes, or does it need to choose where the walls are? An interesting thing that would seem to point that the answer to the first question might be yes is that to find the pair of points furthest apart in a graph (which would be equivalent to finding the hardest compound SBP in a graph) requires only 2 diameter searches! Basically, you start with any point in the graph, then find the point furthest away from that, and let it be your new point. Then, find the point furthest away from your new point, and the two points, the one you’ve just found and the one before that, are the two points farthest away from each other. (See “Wennmacker’s Gadget”, page 98-99 and 7 in Ivan Moscovich’s “The Monty Hall Problem and Other Puzzles”)

Metrics

a.k.a. redefining the problem

Through the last 3 posts on sliding block puzzles, I have usually used the “Moves” metric for defining how hard a puzzle is. Just to be clear, an action in the Moves metric is defined as sliding a single piece to another location by a sequence of steps to the left, right, up and down, making sure not to pass through any other pieces or invoke any other quantum phenomena along the way. (The jury is out as to if sliding at the speed of light is allowed). While the majority of solvers use the Moves metric (my SBPSolver, Jimslide,KlotskiSolver, etc.), there are many other metrics for giving an approximation to the difficulty of a sliding block puzzle, such as the Steps metric, and the not-widely used sliding-line metric. The Steps metric is defined as just that- an action (or ‘step’) is sliding a single piece a single unit up, down, left, or right. The sliding-line metric is similar: an action is sliding a single piece any distance in a straight line up, down, left or right. So far as I know, only Analogbit’s online solver and the earliest version of my SBPSolver used the steps metric, and only Donald Knuth’s “SLIDING” program has support for the sliding-line metric. (It also has support for all the kinds of metric presented in this post except for the BB metrics!)

Demonstration of various metrics

Additionally, each of the 3 metrics described above has another version which has the same constraints but can move multiple pieces at a time in the same direction(s). For example, a ‘supermove’ version of the Steps metric would allow you to slide any set of pieces one square in any one direction. (As far as I know, only Donald Knuth’s SLIDING program and Soft Qui Peut’s SBPSolver have support for any of the supermove metrics) In total, combining the supermove metrics with the normal metrics, there are 6 different metrics and thus 6 different ways to express the difficulty of a puzzle as a number. Note however, that a difficulty in one metric can’t be converted into another, which means that for completeness when presenting results you need to solve each sliding block puzzle 6 different ways! Even worse, the solving paths in different metrics need not be the same!

For example, in the left part of the image above, where the goal is to get the red piece to the lower-right corner, the Moves metric would report 1, and the red piece would go around the left side of the large block in the center. However, the Steps metric would report 5, by moving the yellow block left and then the red block down 4 times. Also, in the right picture both the Moves and Steps metrics would report ∞, because the green block can’t be moved without intersecting with the blue, and the blue block can’t be moved without intersecting with the green, but any of the Supermove metrics would report a finite number by moving both blocks at once!

Various other metrics can be proposed, some with other restrictions (You may not move a 1×1 next to a triomino, etc.), some which, like the Supermove metrics and the second puzzle above, actually change the way the pieces move, and you can eventually get to the point where it’s hard to call the puzzle a sliding block puzzle anymore. (For example, Dries de Clerq’s “Flying Block Puzzles” can be written as a metric: “An action is defined as a move or rotation of one piece to another location. Pieces may pass through each other while moving, but only one piece may be moved at a time”.

Suppose, however, that for now we’re purist and only allow metrics which generate numbers based on the step, sliding-line, moves, super-step, super-sliding-line, and super-moves metrics. It can be seen , quite obviously in fact, that these metrics don’t in all cases show the actual difficulty of the puzzle being considered. For example, take a very large (say 128×128) grid, and add a 126×126 wall in the center. Fill the moat that forms with 507 1×1 cells, all different pieces, and make the problem be to bring the block in the upper-left down to the lower-right. If my calculations are correct, the resulting problem should take 254*507+254=129,032 steps, sliding-line actions, and moves to solve, which would seem to indicate that this is a very hard puzzle indeed! However, any person who knows the first thing about sliding block puzzles should be able to solve it -assuming they can stay awake the full 17 hours it would take!

Because of this discouraging fact- that is, 6 competing standards, none of which are quite right, I would like to introduce a 7th, this one based on a theoretical simulation of a robot that knows the first thing about sliding block puzzles, but nothing else.

The BB Metric

a.k.a. attempting not to invoke the xkcd reference

Nick Baxter and I have been working on a metric which should better approximate the difficulty of getting from one point to another in a position graph. The basic idea is that the difficulty of getting from node A to node B in a graph is about the same as the average difficulty of getting from node A to node B in all spanning trees of the graph. However, finding the difficulty of getting to node A to node B in a tree is nontrivial, or at least so it would seem at first glance.

Suppose you’re at the entrance of a maze, and the maze goes on for far enough and is tall enough such that you can only see the paths immediately leading off from where you are. If you know that the maze is a tree (i.e, it has no loops), then a reasonable method might be to choose a random pathway, and traverse that part of the maze. If you return from that part to the original node, then that part doesn’t contain the goal node and you can choose another random pathway to traverse, making sure of course not to go down the same paths you’ve gone down before. (Note that to be sure that the goal node isn’t in a part of the maze, you need to go down all the paths twice, to walk down a path and then back up the path). For now, we take the difficulty of the maze to be the average number of paths you’ll need to walk on to get to the goal node or decide that the maze has no goal(counting paths you walk down and up on as +2 to the difficulty). Because of the fact that if the node you’re in has no descendant nodes which are the goal node you’ll need to go down all of the paths leading from that node twice, the difficulty of the part of the maze tree branching off from a node A can be calculated as

sum(a_i+2,i=1 to n)     (eq. 1)

where n is the number of subnodes, and a_i is the difficulty of the ith subnode. Also, if the node A is on the solution path between the start and end nodes, then the difficulty of A can be calculated as

a_n+1+1/2 sum(a_i+2,i=1 to n-1)    (eq. 2)

where a_n is assumed to be the subnode which leads to the goal. This basically states that on average that you’ll have to go down half of the subpaths and the path leading to the goal to get to the goal. Because root nodes are assumed to have 0 difficulty, you can work up from the bottom of the maze, filling in difficulties of nodes as you go up the tree. After the difficulty of the root node has been calculated, the length of the path between start and end nodes should be subtracted to give labyrinths (mazes with only a single path) a BB difficulty of 0.

Perhaps surprisingly, it turns out that using this scheme, the difficulty of a tree with one goal node is always measured as V-1-m, where V is the number of nodes in the tree (and V-1 is the number of edges, but this is not true for graphs) and m is the number of steps needed to get from the start node to the end node in the tree! Because of this, the difficulty of getting from one point to another in a graph under the BB metric is just the number of vertices, minus one, minus the average path length between the start and end nodes in the graph.

A few things to note (and a disclaimer): First of all, the actual graph of which positions can be reached in 1 action from each of the other positions actually depends on the type of move chosen, so the BB metric doesn’t really remedy the problem of the 6 competing standards! Secondly, the problem of computing the average path length between two points in a graph is really really hard to do quickly, especially because an algorithm which would also give you the maximum path length between two points in polynomial time would allow you to test if a graph has a Hamiltonian Path in polynomial time, and since the Hamiltonian Path problem is NP-Complete, you could also do the Traveling Salesman Problem, Knapsack Problem, Graph Coloring Problem, etc. in polynomial time! Lastly, I haven’t tested this metric on any actual puzzles yet, and I’m also not certain that nobody else has come up with the same difficulty metric. If anybody knows, please tell me!

One last note: Humans don’t actually walk down mazes by choosing random paths- usually it’s possible to see if a path dead-ends, and often people choose the path leading closest to the finish first, as well as a whole host of other techniques that people use when trying to escape from a maze. Walter D. Pullen, author of the excellent maze-making program Daedalus, has a big long list of things that make a maze difficult here. (Many of these factors could be implemented by just adding weights to eqns. 1 and 2 above)

Open Problems

a.k.a. things for an idling programmer to do

  • What are the hardest simple simple simple 3×4 sliding block puzzles in different metrics? 2×8? 4×5? (Many, many popular sliding block puzzles fit in a 4×5 grid)
  • How much of a difference do the hardest strict simple^3 puzzles have with the hardest simple^3 SBPs?
  • How hard is it to search through all simple simple 4×4 SBPs? What about simple SBPs?
  • (Robert Smith) Is there any importance to the dual of the graph induced by an SBP?
  • Why hasn’t anybody found the hardest 15 puzzle position yet? (According to Karlemo and Östergård, only 1.3 TB would be required, which many large external hard drives today can hold! Unfortunately, there would be a lot of reading and writing to the hard disk, which would slow down the computation a bit.) (Or have they?)
  • Why 132?
  • What’s the hardest 2-piece simple sliding block puzzle in a square grid? Ziegler & Ziegler have shown a lower bound of 4n-16 for an nxn grid, n>6. How to do so is fairly easy, and is left as an exercise for the reader.
  • Is there a better metric for difficulty than the BB metric?
  • Is there a better way to find different sliding block puzzle positions? (i.e, improve the fillboard algorithm?)
  • Is it possible to tell if a SBP is solvable without searching through all possible positions? (This question was proposed in Martin Gardner’s article on Sliding Block Puzzles in the February 1964 issue of Scientific American)
  • (Robert Smith) How do solutions of SBPs vary when we make an atomic change to the puzzle?
  • Are 3-dimensional sliding block puzzles interesting?
  • Would it be worthwhile to create an online database of sliding block puzzles based on the OEIS and as a sort of spiritual successor to Edward Hordern’s Sliding Piece Puzzles?

Sources

Ed Pegg, “Math Games: sliding-block Puzzles”, http://www.maa.org/editorial/mathgames/mathgames_12_13_04.html

James Stephens, “Sliding Block Puzzles”, http://puzzlebeast.com/slidingblock/index.html (see also the entire website)

Rob Stegmann, “Rob’s Puzzle Page: Sliding Puzzles”, http://www.robspuzzlepage.com/sliding.htm

Dries De Clerq, “Sliding Block Puzzles” http://puzzles.net23.net/

Neil Bickford, “SbpUtilities”, http://github.com/Nbickford/SbpUtilities (meh)

Jim Leonard, “JimSlide”, http://xuth.net/jimslide/

The Mysterious Tim of Analogbit, “Sliding Block Puzzle Solver”, http://analogbit.com/software/puzzletools

Walter D. Pullen, “Think Labyrinth!”, http://www.astrolog.org/labyrnth.htm

Donald Knuth, “SLIDING”, http://www-cs-staff.stanford.edu/~uno/programs/sliding.w

Martin Gardner, “The hypnotic fascination of sliding-block puzzles”, Scientific American, 210:122-130, 1964.

L.E. Hordern, “Sliding Piece Puzzles”, published 1986 Oxford University Press

Ivan Moscovich, “The Monty Hall Problem and Other Puzzles”

R.W. Karlemo, R. J. Östergård, “On Sliding Block Puzzles”, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7558

Robert Hearn, “Games, Puzzles, and Computation”, http://groups.csail.mit.edu/mac/users/bob/hearn-thesis-final.pdf

Ruben Grønning Spaans, “Improving sliding-block puzzle solvingusing meta-level reasoning”, http://daim.idi.ntnu.no/masteroppgave?id=5516

John Tromp and Rudi Cilibrasi, “”Limits on Rush Hour Logic Complexity”, arxiv.org/pdf/cs/0502068

David Singmaster et al.,  “Sliding Block Circular”, www.g4g4.com/pMyCD5/PUZZLES/SLIDING/SLIDE1.DOC

Thinkfun & Mark Engelberg, “The Inside Story of How We Created 2500 Great Rush Hour Challenges”, http://www.thinkfun.com/microsite/rushhour/creating2500challenges

Ghaith Tarawneh, “Rush Hour [Game AI]”, http://black-extruder.net/blog/rush-hour-game-ai.htm

Any answers to questions or rebukes of the data? Post a comment or email the author at (rot13) grpuvr314@tznvy.pbz

What I’ve Been Working on Lately

Readers of this blog may notice that I haven’t been updating for the last 4 months. The purpose of this “filler” post is for me to say why.

First of all, I could easily blame the season. Summer, as is well known, is a time to “kick back and relax” as well as forgetting about important things you should be doing and reading webcomics instead.

I could also blame the wonderful 3D printer I’ve bought, which has quickly filled up my desk and emptied my wallet with tens of tiny plastic models and puzzles.

However plausible that may seem, I would more truthfully blame the projects I’ve been working on, especially my “work” in the field of sliding block puzzles.

As you may know from a post I made about a year ago, I’m quite interested in really hard sliding block puzzles such as the Panex Puzzle (30,000? moves) or Sunshine (729? moves). James Stephens, of puzzlebeast.com, is certainly a pioneer in making really hard sliding block puzzles by computer. Using his “Puzzlebeast” software, he’s made at least 23 progressively harder sliding block puzzles, ranging from 18 to 148 moves! What’s more, he restricts many of these puzzles to only having a few pieces, and in at least 11 of them the goals are “Simple Simple”, that is, move a single piece to a single corner! Even the puzzle which fits on a 4×4 grid and uses only 4 pieces and is only 18 moves to a solution, “Simplicity”, is really quite hard for a human to solve! Oskar van Deventer, maker of many mechanical monstrosities, has designed a 3d-printable version of the Simplicity puzzle, calling it the “Hardest sliding piece puzzle on a 4×4 grid”.

Gauging from Stephens’ description of Puzzlebeast, Puzzlebeast uses a genetic algorithm to create its puzzles. So far as I can tell, it starts with a random set of puzzles. It picks the hardest out of that set, then for the next generation it creates random “mutations” of the best puzzles of the last generation. For example, it may add a piece, move a piece, modify a piece, or remove a piece. Repeat this process over and over again, and eventually you’ll have a hard sliding block puzzle. I think because it seemed to work very well for him, I eventually tried to make a sliding block puzzle evolver for myself.

And so the SBP project began: The earliest version of my SBP evolver were coded in Mathematica, and was very manual.  I would start with 5 randomly generated 4×5 rectangular puzzles, without any restrictions on the number of pieces, and then for each puzzle I interpreted it as a “Simple simple simple sliding block puzzle”(see footnote 1) and then fed it into Analogbit’s online sliding block puzzle solver, which counts moves in steps, meaning that each “step” is sliding one piece one grid space in the puzzle. Once that was finished, I took the best two puzzles, converted them to 1-d arrays, “interleaved” them, and then influenced random mutations in their cells (That is, each cell had about a 1/5 chance of being added 1 to or being subtracted 1 from). Since that probably isn’t too clear, here’s an example:

Suppose the best two puzzles from the last generation were

 0,19, 1, 2      0,19, 0, 3
 2, 1, 1, 1      2,19, 1, 1
 0, 2, 0, 2 and  1, 3, 2, 0
 1, 1, 0, 0      0, 1, 1, 0
 1, 1, 0, 1      0, 1,19, 2

Then the “interleaving” of the two would be

0,19,1,2,2,1,1,1,0,2,0,2,1,1,0,0,1,1,0,1 +

0,19,0,3,2,19,1,1,1,3,2,0,0,1,1,0,0,1,19,2=

0, 19, 1, 3, 2, 19, 1, 1, 0, 3, 0, 0, 1, 1, 0, 0, 1, 1, 0, 2

and the “mutants” would be generated from there, and the process would repeat.

Notes: 1. “Simple simple simple sliding block puzzle” is my own term, based off of Nick Baxter’s definitions at the Sliding Block Puzzle Page . For me, it means that each piece is different from another only by its shape, and that the goal is to get the top-left-most piece down to the lower-right. The original definition was somewhat ambiguous, it actually means that if there is no piece with a square occupying the upper-left corner, it is not a valid simple simple simple sliding block puzzle. Additionally, many of the puzzles in this first section are copied straight from the Mathematica notebook, and so there is a distinct lack of proper number parsing. Parsing manually is simple: If two numbered pieces have the same number and are orthogonally adjacent, they both belong to one piece. Otherwise, they belong to different pieces. (Eventually I got a parser working to make these puzzles conform to standards, so the reading should get easier). Lastly, steps and moves are different, as one involves moving one piece one space and the other involves moving one piece any number of spaces. Edward Hordern’s book, Sliding Piece Puzzles, does a good job to clear this up.

Anyways, the very first incarnation of the SBP Evolver produced quite fantastic results! In about 10 generations, with populations varying from 4 to 10, the puzzles had progressed from 4 impossible puzzles and 1 8-stepper to  3 impossible puzzles and 7 possible, one a 58-stepper! Now of course this is no big result, as such puzzles as Bob Henderson and Gil Dogon’s “Quzzle-Killer” take 121 steps to solve, and so this early experiment was really just a proof of concept.

Eventually, I got tired of feeding all these puzzles through Analogbit, so I decided to write a C# program to do it for me, except instead of using Analogbit, it would use Jim Leonard’s very speedy Jimslide software. Furthermore, it would have much larger populations (perhaps 100 or so) and do many more generations. Some time later, after writing many, many lines of code to process the puzzles for Jimslide’s use, and then processing the output, I finally got it working! Almost immediately, I set it going on a huge number of 4×5 puzzles (10 million) and let it run overnight. It actually took around 4 days, but the best it found was a 176-move puzzle!

1203-4253-4673-8879-ABCC
The 176-mover (by no means the best simple simple)

The SBP Evolver also displayed some behavior which I conjecture is common to most poorly-written genetic evolution programs: Once the program found a really good optimization, if there weren’t any tiny optimizations which would improve the puzzle, it would tend to stay with that puzzle for a while unless, by pure chance, the next generation happened not to contain that puzzle. As such, the 4 days might actually not have been long enough to find the best puzzle. Additionally, Bob Henderson’s Gauntlet #2, another simple simple sliding block puzzle, trumps the 176-mover with 235 moves!

As far as I can tell from his description on Andrea Gilbert’s clickmazes site, Bob Henderson uses a very different method of generating sliding block puzzles. He inputs a collection of shapes, and then his packing program generates all possible ways that those blocks could be placed in a sliding puzzle. He then feeds those through his sliding block puzzle solving program, which returns the best results. I expect it produces results much faster, albeit only with the blocks the designer chooses.

Having been thus discouraged, I set out to go through the much easier 4×4 puzzles instead. This time, after about a day, it generated a 125-move simple simple puzzle! However, it turned out that the puzzle could be backtracked to make a 132-move puzzle, presented below. Interestingly, when I ran the same computation again, it generated another descendant of the 132! Now, of course, the question was: Is this the best 4×4 simple simple simple SBP?

1123-4522-4678-0690
Red to lower-right.

The problem could be easily solved by just generating all possible 4×4 positions, interpreting a simple simple simple SBP out of them, and then solving each and every single one. But how would you do the former? After all, there can be 16 possible block types in a 4×4 (including holes) and each space could be one of the 16, so you’d have 16^16=18,446,744,073,709,551,616 possible combinations! My answer to this was to invoke the 4-color theorem, using 0 for the holes, and 1,2,and 3 for colors for the other pieces. After the 4-coloring of the board, a parser would assign each block a unique number, and then remove any duplicates (This was in fact WRONG; The holes could be separate, and so the 4-color theorem applied only to the blocks. I in fact had to eventually use 5-colors for the whole thing). After around a day or so, the puzzle-finder would process 4294967296 boards, and it returned only 52,825,604 different boards!

Two other methods which might have worked as well or better might be to either generate all 1-piece boards, then generate all 2-piece boards from all nonoverlapping combinations of the 1-piece boards, and so forth. There’s also a method based on dynamic programming which I currently use, which (while it is too long to write out here) is included in the SBPFinder source code, available at the bottom of the post.

After the 52,825,604 different boards were separated into files depending on the number of pieces, the host software would load up each file into a hash table, then solve the first puzzle. After the puzzle was solved, the software would process the output and remove the puzzles mentioned in the solution from the hash table. It would then solve the new first puzzle, and so on. While it isn’t very fast at all to use this algorithm (it took 48 days), it at least had an advantage: By separating the puzzles into files labeled with the number of pieces, it was possible to return the “hardest” puzzle for an arbitrary number of pieces in a 4×4 grid! Below is a table of the hardest simple simple simple SBPs in a 4×4 grid, from 2 to 15 pieces. Keep note, though, that since the computation missed out on a few million puzzles, all the below are unverified and the ones which are very dubious are removed. Also, because SBP determined which piece was the goal piece by going line by line, some of the puzzles below are simply simple simple SBPs and the ones which are just simple SBPs are removed. (Confused? Check http://www.johnrausch.com/SlidingBlockPuzzles/4×5.htm)

Note that these results are not to be trusted; for one, bugs have been found in both the problem finder and the puzzle-to-Jimslide converter itself, and so the results certainly aren’t rigorous. Also, the SBP Evolver (which also runs the puzzle-to-Jimslide converter and searcher) was originally designed to treat any puzzle as a simple simple simple, by choosing the goal piece as the first piece encountered going line by line through the board. Lastly, there’s a curious phenomenon around 12 pieces: Breaking a 1×2 into 2 1×1 pieces and shuffling the remainder about creates 9 more moves!

Since then, I’ve been trying to do a verification of the 4×4 computation, specifically by creating another program to rerun the entire search process, return the best results, and then check to see if the results are the same. The catch: I need it to be a few times faster. The optimizations I’m working on including are:

•Using one of the alternative methods to find potential SBPs faster,

•Only storing the “justsolved” puzzles, that is, puzzles in which the goal piece is already in the lower-right and can move out of it’s current position. (Based on an idea from “Rush Hour Complexity” , by John Tromp and Rudi Cilibrasi. It turns out that about 1/4 of 4×4 SBP positions are justsolved, a rather large value, mostly because in most positions there is a piece in the lower-right corner, and the only real limitation is that it must be able to move), and

•Using a custom-written sliding block puzzle solver to find the hardest puzzle in the entire group of positions the justsolved puzzle is linked to. (This can be done in 2 diameter searches, one to find the other justsolved puzzles in the group, and the other to find the starting position the furthest away from all the justsolved positions. My custom solver is about 3x as slow as Jimslide, but it makes up for it by that it’s solving the entire group of puzzles and removing the other justsolved puzzles from the list. There can be a stunning amount of other justsolved positions reachable from a puzzle- some have been found with over 14,000 !)

However, I’ve hit upon a gypsy moth in my solver causing it not to search the puzzle completely! Preliminary tests of the program though, have revealed the expected running time to be about a day, so stay posted!

Anyways, that’s my explanation as to what’s been going on, and I apologize for my relative silence.

G4G9, Day 5: Balancing Laptops, Mobius Music, and Egg Cartons

This is the 6th and final post in a series of posts about Gathering For Gardner: 1 2 3 4 5

I started the last day of Gathering For Gardner 9 by waking up late.

As a result, I completely missed the first talk and entered the conference room in the middle of the second talk, by Karl Schaffer, about “Dancing Tessellations”. It consisted mainly of a few videos in which a normal dance would be reflected along certain axes so that it effectively makes a video tessellation. The next one was a short talk on extending the Side-Angle-Side (SAS) similarity theorem to three-dimensional shapes using the least possible number of measurements. One of the especially interesting talks in the first session was by Linda Zayas-Palmer, on why the infinite number, 0.999999… , is actually not just equivalent to, but greater than, 1. The talk directly after that was about some of Salvador Dali’s puzzles in some of his paintings, in which you have to find a certain phrase. Turns out his puzzles are rather easy.  My favorite talk in the session, though, was by Burkard Polster on how to balance your laptop on a bedside table such that it occupies the minimum amount of space on the table and doesn’t fall off. It starts out by a simple dissection of a square by Martin Gardner, and then exteds it to show how to balance the laptop just right so that it’ll balance, thus leaving room for puzzles or whatever you would put on a bedside table.

During the break, Mom and I went up to the exhibit room, where the exhibitors were packing up their exhibits. Most of the exhibits were already gone, but a few were there that weren’t the first time. For one of these, involving curious polyhedral sculptures made with egg cartons, Mom actually got to talk with Jeannie Mosely, the person who made them. In fact, she actually got a model of the octahedron which had fairly novel methods of holding together as an example to make more.

After the break, the talks continued with a talk on 3-dimensional packing puzzles made out of various spheres glued together to make polyomino-like shapes. Due to the spherical nature of the pieces, some of the puzzles need the polyspheres to “snap” together, something which doesn’t normally happen. A rather good talk in this session was by Ed Pegg, about the Wolfram Demonstrations Project, and some of the best demonstrations that had been posted, such as a program to find the smallest box that squares of size 1/n can fit in:

Or even how to solve the Orchard-Planting Problem, involving finding a certain number of lines that pass through a certain number of points, given the required points:

The talk after Ed Pegg’s talk was one of the most anticipated talks of the entire conference: Finding a single shape that covers the entire plane aperiodically, which was an unsolved problem. Joshua Socolar managed to find a single hexagonal tile (with matching rules, though) which creates a Sierpinski Gasket-like shape when made. He also made a 3-dimensional tile which acts the same.

The 2-d tile

Afterwards, Vi Hart did a great talk on making music with music boxes with the music scores in Mobius strips, or the music boxes arranged in such a way so that the music played by one music box is played by another music box seconds later.

After Vi Hart’s talk the lunch break started, but instead of going to lunch  I went immediately up to the Gift Exchange area, where I would wait in line to get a bag full of exchange gifts from nearly everybody, repeated for everyone, who would get one also.

Apparently everybody else had the same idea of waiting in line early. I ended up behind Bram Cohen, inventor of BitTorrent as well as a whole bunch of super-duper-hard twisty puzzles which have some rather ingenious ideas behind them. He happened to have a few non-twisty, but still hard, puzzles while waiting in line, and I managed to almost solve one of them (the Cast Rattle), which involved getting the right pieces in the right place (That isn’t a spoiler, is it?). The other one, Cast Marble, I couldn’t get immediately, but I might have been getting close. Soon, I got to the front of the line to get my bag of exchange gifts and got the huge bag (I could barely carry it) as well as a few other miscellaneous items from people at a few nearby tables, such as a perplexing wooden object which looked like a gear, or a few pictures from Caspar Schwabe (I presume) of large inflatable solids, including the huge 59th stellation of the icosahedron seen on day 3.

I brought the huge bag of gifts up to the hotel room to open, and even though the bag’s heaviness was an indicator of the number of things inside, it still felt like Christmas when I opened it. There were mathematical dice with the sides only using the number nine and a set of plastic rings with interchangeable art based on the Traveling Salesman problem; there was a CD containing rather high-quality pictures as well as a digital copy of the exchange book from G4G8; A set of pieces for an unsolved puzzle and a key to open doors with using a hammer; A book about formulae that changed the world and a second copy of  A New Kind of Science(Ah, so that’s where the heaviness came from);Even a mysterious back-scratcher and tapper. These are just a few of the things in the bag, and to list them all out would certainly lengthen this blog post by quite a lot.

By the time I had gotten to the bottom of the bag, the third session was about to start so I had to rush down to see the talk by Gordon Hamilton (of the Magical Mathematics Museum) about having problems in K-12 classrooms involving unsolved problems such as the circle-packing problem (In how small a square can you pack n circles?), the 3n+1 conjecture (Do all Collatz sequences end in 4,2,1?), and others. Also in the same session was Solomon Golomb’s talk about the Pentomino Game on nxn boards. The “Pentomino Game”, is a rather interesting two-player game in which players alternate turns placing pentominoes onto an 8×8 board. The first player who can not place another piece loses. One of the most interesting talks of the session was “Fun with Egg Cartons” by Jeannie Mosely. In the talk,  she described how she made most of the Platonic Solids – out of egg cartons! The process of making these is pretty easy- just interleave strips of egg cartons at the vertices to make the edges- but the results are still interesting.

Immediately following was a talk not relating to mathematics at all (but still cool), about restoring various ancient text adventures. The talk was by Adam Atkinson, and it was about cross-compiling old text adventures (running on mainframes) so that you could play them on newer computers. Many of them are stored at ifarchive.org (the Archive for Interactive Fiction), including Acheton, probably the third text adventure ever made. Just don’t get eaten by a grue.

After the last short break, the last session of G4G9 began. Kate Jones started of with a philosophical talk involving pentomino puzzles,followed by Bill Mullins, who talked about Martin Gardner’s search for the person who wrote “The Expert at the Card Table”, probably the most important book ever on sleight of hand with cards, who wrote his name as “S.W.Erdnase”. It can be reversed to make E.S.Andrews , but from there it’s much harder. So far, they’ve found 5 suspects as to who S.W.Erdnase might be, 2 by Gardner and 3 by others, but the writer remains hidden. Hirokazu Iwasawa (also known as Iwahiro) then followed that with a talk about the subclass of “Hat-Team Puzzles” , how to solve them, as well as other variations on the problem. A bit later, Colin Wright did a double talk about “How far is the Moon?” and about notations for juggling. The former was left out (the pdf is available here) , but the talk about juggling was amazing. Not only did he juggle normally with up to 5 balls, but he also showed how to use a notation for juggling to make up your own tricks, some insanely complex and others trivial. Following that, George Hart talked about his new sculpture, “Comet!” which involves multiple smaller versions of the main model (a puzzle-like polyhedral-ish form) with different colors. It’s so big that it has to be hung on the ceiling of an atrium. After that, Mike Keith did the second-to-last talk about his book, Not A Wake, in which every word of the text- including the subtitle and the title- has the same number of  letters as the nth digit of pi does. The book goes on for 10,000 digits, with 10 stories followed by the digits of pi in that story, each story being a different style than the others.

After the last talk and closing notes, G4G9 was over. However, the fun(at least for me) continued. I was invited to dinner (along with Bill Gosper, Mom, Julian and Corey Hunts) by Dick Esterle to the Varsity Jr., an old-style fast food diner that had been operating for 45 years. Bill and Julian declined, but the rest of us went.

The diner had good food (especially the burgers) , and talking with Esterle was quite interesting. I brought a box puzzle (the same from the prelude) , and he managed to solve it in record time just by shaking it hard. He also, using the materials that were available, gave me 2 versions of the same puzzle. First, arrange 3 cups in an equilateral triangle such that a knife can reach from any cup to any other cup. Then, use the knives to balance a salt shaker in the middle of the triangle above the table. (This can be done using 2 knives) Then, set the cups so that they are just a bit too far for the knives to reach, and once again balance the salt shaker using 3 knives. Corey and I eventually solved it and put a few straw decorations on (from my solution to the problem using straws to extend the knives and only using 2 knives). To prevent spoilers, it’s at http://daftmusings.stattenfield.org/wp-content/uploads/2010/04/Neil-and-Corey-at-the-Varsity-copy.jpg .

After dinner, Dick Esterle drove us back to the Ritz-Carlton, where we went back up to our hotel rooms and played with puzzles until bedtime.

The day after that, I was waken up very early to get packed up for the airplane trip back to San Jose. We met Bill Gosper in the hotel lobby, and took a cab to the airport, at which point we waited until dawn-ish. On the airplane trip back (with an exchange in Chicago), I looked at all of the exchange gifts in the bag and Bill Gosper programmed on his laptop. Eventually, after having 2 breakfasts due to time zones, we landed in San Jose, drove over to my house, whereupon Bill drove back to his house. And because of time zones, I still had the rest of the day to play with puzzles.

Thus the epic of Gathering for Gardner 9 ended.

It was an absolutely great experience from before it even started to it’s end, and I met a lot of new people and saw a lot of puzzles and magic tricks and optical illusions. I would certainly go the next time it happens, and the time after that. Certainly, it was one of the best events that I attended ever, if not the best.

As an afterword, on May 22, Martin Gardner died. Hearing the news of this was incredibly saddening to me, as well as sudden. He was one of the most important people that ever lived, for mathematics and as well as for many other subjects. He helped popularize M.C. Escher and Godel,Escher,Bach , and introduced mathematics in a fun way to at least everybody at any of the G4Gs. He was truly amazing.

G4G9, Day 4: Lasers, Sculptures, and Balloon Polyhedra

This is the 5th post in a series of posts about Gathering For Gardner: 1 2 3 4

We woke up the next day, and soon realized that the first talk had already started, but only by around a minute. Luckily, the conference was in the hotel I was staying in, so I only arrived a few minutes late. The first talk was by Jean Pedersen, about the extended face planes of various polyhedra. The next few talks were rather interesting:  Zdravko Zivkovic introduced a puzzle called “MemorIQ” where you have to make various shapes out of octagonal pieces which are colored on the sides. The sides of the pieces touching must also be the same, so it is a bit of a challenge to make a square with the pieces. Al Seckel then did a talk on “The Nature of Belief”, talking about various ambiguous optical illusions which change completely when you add a simple line to them, as well as a music track reversed which originally sounds like gibberish, but when words are added, comes out very clear. Greg Federickson did a talk on “Symmetry vs. Economy in Dissections of Squares and Cubes”.  In it, he showed many demonstrations of  dissecting squares and cubes into many smaller squares and cubes, in very symmetrical ways and also in the minimum number of pieces. He also showed examples for hinged dissections, some of which were very ingenious, especially for the cubes.  Lastly, Robert Crease talked about his new book about some of the most important equations in mathematics and science.

After a short break, the 2nd session began. Pablos Holman stated out with a great talk about “Hackers and Invention” in which he demonstrated how to kill mosquitoes by shooting lasers, changed the voicemail sound on Al Seckel’s phone by spoofing his caller ID, displayed a robot that wheels up to people and shows them their passwords, and showed how to pick a lock very quickly using a filed-down key and a hammer. After this talk, I went out with Bill Gosper, who was going to show John Conway the Universal Game Of Life Computer which Calcyman had made computing Pi. Bill also showed Conway some other Game of Life patterns, such as the same universal computer computing the digits of the Golden Ratio, and a Python script for going to a particular step in a Life simulation faster than the normal algorithm, which he demonstrated by simulating a pattern to a googol-1 steps. Because of this, I was a bit late for the last talk of the day, the overview of the math sculptures that were to be made later that day at Tom Rodger’s house, which ranged from a button knot to a huge zonohedral pavilion.

I had a quick lunch (i.e, none) and boarded the bus that would be going to Tom’s house. On the way there, I tried to figure out some particularly hard puzzles which had little or no instructions, and also talked with some of the other attendees. When we arrived, they had a lot of Japanese-style lunches set out on a table for us to eat before building the various sculptures and seeing some of the things that were already set up. Some of the most interesting things there were a metal polyhedral-ish sculpture that George Hart was making, an impossible box that you could stand in, and a huge black hyperbola that towered over everything else.

After eating my lunch, I helped build the base for the zonohedral pavilion by soaping the pieces and then placing them into place on the supports. When that was done, they started on the roof of the pavillion, and I showed a few puzzles to other attendees, inlcuding a version of the Enigma puzzle as well as a “chopstick” puzzle using some of the left-over chopsticks from lunch.

Afterwards , I helped out on another sculpture, this time a metal sculpture of a three-dimensional Peano curve, which had to be put together using  near-identical pieces and screws. The pieces were very rusty, so my hands got very dirty. Eventually it was almost done and I wandered off somewhere else. Back near the house, Vi Hart had been showing people how to make various polyhedra out of  balloons, such as simple octahedra and cubes.

I went with Gareth Conway and Max to explore a section of the landscape which Max said was an entrance to a gold or a silver mine, and which was almost completely covered with leaves from the surrounding trees. At some point, Max said that we’ll get famous for discovering this gold mine, to which Gareth responded that he was already famous for that he knew 130 digits of pi. I promptly responded with all of the digits of Pi I knew (only 30), and Gareth corrected me when I added on a few extra digits. It’s good that Michael Keith, the author of a book entirely written in Pilish wasn’t there at that point, because then I’d have to listen to quite a lot of digits of Pi. Eventually, however, it turned out that the “gold mine” was actually just a well.

Meanwhile, the polyhedral balloon-making had gotten completely out of control:

I went back to the main area, where I saw that a lot of the sculptures had been finished, such as the Chinese Button Knot and George Hart’s sculpture. I got to talk with Clifford Pickover about various things, such as the non-paradox that 100% of all integers have a 9 in them, and about some of the artwork in The Math Book, Pickover’s new book. Nearby was Ivan Moscovich, whom I talked with as well about various puzzles, such as his Mirrorkal series of sliding block puzzles in which you have to make a certain image with the pieces, which have mirrors on them so that the first puzzle is figuring out what configuration the blocks should be in afterwards. Soon, nearly all of the sculptures had been finished except for the pavilion which was almost finished and it was getting dark.

We had quite a nice dinner, although the tables were full so I had to sit nearby, where Gosper was.  We talked for some time, and I mentioned a formula that can calculate Pi to 42 billion digits but then soon diverges. After the dinner, I went into Tom’s house which, as I have said before, is absolutely filled with puzzles. I played with a few puzzles, including  a 3-piece burr and a few Japanese puzzle boxes but then encountered a puzzle that fell apart and then was impossible to put back together. By that time, it was time to go back to the hotel. I boarded the bus in the back- right next to George Hart and a few other people who had made the sculptures at Tom’s house that day, who I talked with for the ride back.

It had been a great day, and there was only 1 day of the conference left.

G4G9, Day 3: Random(Blog), Crazy Detectives, and the Rubik’s Cube

This is the fourth post in a series of blog posts about Gathering For Gardner 9: 1 2 3

We started out the 3rd day by changing the hotel where we were from the Peachtrees to the Ritz-Carlton, where I missed the first talk, which was apparently about “The Odd One Out and Unrevealing Coin Weighings”

The very first talk that I saw, then, was by John Edmark about “Geometric Patterns of Change”. It was mostly about the sculptures that he has made, some based on the Fibonacci sequence and the Golden Angle, while others were on various spirals which could change direction by simply changing the angle at the top. Adrian Fisher also did a talk on that he was making Custom Designed Mazes, specifically hedge mazes for any people who had a castle somewhere and liked mazes. Last in the first session was a 15-minute talk by Ed Pegg, called “Meet the Attendees”, which was where he would bring up various attendees who weren’t doing talks and have them describe themselves in 20 seconds, as he would show a slide that he had made for them.  I thought that he would only bring up the attendees who wanted a slide in the presentation.

Turns out, I was wrong. He really had made 70 individual slides, one for each attendee who wasn’t giving a talk, including me.

I was around 5th, but because many of the attendees had decided not to come up, I was instead in 2nd place for a 20-second talk. Of course, I hadn’t expected this, and so I had around 30 seconds to figure out what I was going to say.  When my time came, I went up and gave a very short description of my website, this blog, and my Scratch Projects, somehow in less than the 20 second I had. Many other people came up and gave short descriptions of what they did, some seeming to go over 1 minute, but Ed’s talk still came in before the 15 minutes he had.

The next session started out with two Dr. Matrix (one of Martin Gardner’s characters, a numerologist) impersonators, Scot Morris and Bruce Oberg, talk about the number 9. Scot’s talk was about “Cosmic 9” which detailed how 9 lay at the center of the universe: He pointed out the methods of counting out nines, that 9 was a square number, and so on. Bruce Oberg’s talk was about “Nein to Nine”, in which he pointed out how bad 9 was. My favorite line in his talk: “First, I will show that 9 is lazy. What happened in 9 A.D.? (pause) ABSOLUTELY NOTHING!” After a few more talks, Stephen Wolfram did a talk on all the work he has been doing, such as Mathematica, Wolfram|Alpha, and A New Kind of Science, a rather large book weighing in at 1,200 pages.

We had a short lunch break, in which I skipped eating in order to buy a few puzzles, which included a combinatorial puzzle in which you have to rotate 3 controls in order to get 10 disks to line up, as well as an interesting packing set of polyhedra. After this, I went back downstairs for the 3rd session.

Steve Macknik and Susana Martinez-Conde started out with a talk on why we are fooled by magic. They pointed out that this was because of the magician’s skillful use of misdirection, and showed us a few videos on this effect, starting out with a card trick:

And then following up with a case of “Whodunit”, where there are 21 changes in the scene:

David Kaye also did a talk on how to perform magic for groups of  children, using a video as an example where he is dressed up as a clown and proceeds to do a trick with scarves, except that many things go wrong while he is doing the trick. Adam Rubin then did a talk on “Gravity Unmatched” which was a magic trick where a knife, attached to a string which goes over a pole and is tied to a pen, is falling towards him, yet it stops just before stabbing him. Kenichi Mura then did a talk on using Reulaux triangles for buckets in a chaos experiment.

There was a short break, in which I went to the Thinkfun exhibit showing nearly all of the games and puzzles that Thinkfun has made, from its first puzzles based on the Chinese Rings to the classic Pentominoes to the new Tipover. I talked with some of the creators, such as Bill Ritchie and Tanya Tompson, and said that many of their old puzzles were really neat, and that perhaps they should do sort of a “2nd edition” of some of them.

The last session of the day was themed around the Rubik’s Cube, and started out with Jerry Slocum doing a talk on the history of the Rubik’s Cube which was very interesting especially in the part where he talked about various Rubik’s Cube variants, such as the Void Cube or some of Bram Cohen and Oskar Van Deventer’s twisty puzzles. Lucas Garron followed up by talking about speedcubing and other types of Rubik’s cube. My favorite talk of the session, though, was Bram Cohen’s demonstration of the twisty puzzles that he has been making, in which the cubes can have very strange forms once twisted in certain ways (They no longer in any way resemble cubes) and also where the cube is distorted and so will not permit certain moves once twisted. Many of the cubes he and Oskar have invented can be seen at Oskar’s Youtube page:

Rik Van Grol, editor of Cubism For Fun, did a talk on “The Quest for God’s Algorithm”  which is the algorithm which solves the Rubik’s Cube in the minimum number of moves. He detailed on how the number has gone down from a high 60 to a lower bound of 20 and an upper bound of 22. (News Flash! Tomas Rokicki has found an algorithm which solves the Cube in 21 steps. Could this be God’s Algorithm?) Roice Nelson, creator of many wonderful programs, then did a talk on his program for displaying 3-d Rubik’s Cubes as 2-dimensional stereographic projections which you can rotate.  Julian and Corey then went up and gave a talk entitles “Fun with the Minsky Circle Algorithm”. It summarized nearly all of their research with the Minsky Circle Algorithm, which is supposed to make circles, but they managed to tweak the variables so that it makes crazy fractal-like structures. For some reason, the plots of the periods often have symmetry, often based around a central point:

Click to view full size

After the last session, we waited while the room in which the talks were held was being converted into a dinner/magic room. While we were waiting in line to get food, a person managed to find me and said “Stephen Wolfram wants to see you.” I was absolutely amazed by this, so I followed her to where, in fact, Stephen Wolfram was. I talked with him for a bit about various cellular automata and his book, and then went back in line to get food.

The magic show was amazing. It started out with Mark Mitton bringing Gareth Conway (he must be getting awfully tired of these magic shows) up to demonstrate an optical illusion with a rotating spiral. Then a dancer came up and performed an act in which she would produce seemingly endless flowers and cards from a single flower. Mark went back up for an act in which he would get a (very confused) audience member to perform a magic trick, without him speaking any words. A few other magicians came up for acts, and Gary Foshee presented a gift to Tom Rodgers. Lennart Green did an amazing card trick where he would blindfold himself, duct-tape his entire face,  cover it with aluminum foil, and then perform a magic trick, sometimes spilling cards, but performing the trick flawlessly. I was actually called up for a trick by Derek Hughes, in which he would perform a card trick in which supposedly, whatever answers I gave to his questions, he would show that I did not have free will by showing that I chose one particular card.

Apparently I do have free will, because I managed to somehow mess him up by not cutting the cards.

There were many other acts, and the show in general was great. In the above video, there’s a multicolored blob to the left, which was because the first act was of Caspar Schwabe blowing up a giant inflatable model of the 59th stellation of the icosahedron.

After the magic show, we went back upstairs and went to bed.

Gathering For Gardner, Day 2: Fractals, Puzzles, and Magic

Continued from a previous post… and the one before that

The next day was Thursday, marking the start of the talks, where various mathematicians, optical illusionists, computer programmers and magicians would give short 10-30 minute talks about various subjects. The talks started at 8:30, but we got there a bit early, so my mom dropped off my exchange gift (a puzzle where you have to put together 9 nonahedral shapes together to make a nonahedron), while I watched the start of the talks. The very first talk was by Erez Lieberman-Aiden, who talked about how the human genome might fold itself into spacefilling curves, rather than in a big tangle. The talk was supposed to be 30 minutes long, but he finished 3 minutes early, so (due to a rule/tradition that any speaker who finished before his time limit was given 1 dollar for each minute that he was under time) he received 3 dollars. Vladmir Bulatov did a talk on models of hyperbolic geometry, starting with Escher’s Circle Limits and moving on to computer models and animations. Jason Rosenhouse also did a talk on “The Monty Hall Problem, Revisited” in which he described various variations on the Monty Hall problem, such as a Monty who completely chooses random doors, and sometimes shows the car before he allows you to make a decision. Gary Foshee did a 1-minute talk on the Tuseday Birthday Problem, based on the original birthday problem, except that one of the children is born on a Tuesday.

Then there was a 20-minute break, in which I went up to the exhibit room to help and watch the exhibitors set up.  Hans Schepker was setting up a large staircase which appeared to defy gravity, even though wires were attached to each of the cubes that made it up. He also made a type of flexagon based on seven tetrahedra taped along their edges in which the shape folded out progressively around the circle instead of all at once. John Edmark was also there, with many sculptures based on the Fibonacci sequence, the Golden Ratio, and the Golden Angle, such as a whirligig which, when spun one way, made a smooth spiral, and when spun the other way, made a shape that looked like a pine cone.

The next session started out with John Conway doing a talk on the Lexicode Theorem Non-Theorem Puzzle, which led to the system of Nimbers, in which 8+8=0, and where 8*11=9. Uri Levi was next, with a demonstration of a new puzzle he had found called the “Magnetic Tower of Hanoi”  which normally needs 3^n moves to solve, but variations on it can have rather complicated formulas for the minimum moves required. Neil Sloane also announced that the OEIS was going into a wiki format, and Benjamin Chaffin did a talk on computing the curling number conjecture and the Recaman Sequence.

By then it was time for lunch, and I skipped lunch to have a look at the sales rooms, where various puzzle creators were selling their puzzles for various prices. The first booth that I recognized when I first came in was that of Pavel Curtis, creator of  insanely hard puzzles, who was selling nearly all of the puzzles he had on his website. I also noticed that the people who made ZomeTool had set up a booth selling the product. Inside the other room was even more puzzles, including various combinatoric puzzles, mathematical books, puzzle boxes and suitcases, and much more. Sandro Del-Prete, who I had met before before the Bar Bets session, was there and my mom bought one of his books for me, provided that he would sign the book in German, and that I would have to read what he had written.  Nearby was Clifford Pickover, one of my favorite writers of math and computer science books, who I talked with shortly and then – something that would only ever happen in Gathering For Gardner- Ivan Moscovich, another one of my favorite authors of math and puzzle books, turned out to be right beside us. Of course, I talked with him for a while, and then went back to the other room, where I noticed that Kadon Enterprises, makers of tons of polyomino-based puzzles, were there, and quickly solved one of their easier puzzles, a set of pentominoes which could be stacked to make 3D shapes. By that time I went back down for the next set of talks, as an hour had already passed.

The next set of talks started out with a set of puzzle fonts by Erik Demaine, where you have to solve a puzzle to even figure out what the letter was, and then repeat that for each letter in the text. Kenneth Brecher did a talk on ambiguous figures, in 2D and also in 3D, and proposed a problem about 4 or more perspectives of an ambiguous object that I quickly solved by placing the Rubin Vase on a type of striped disk which produces either 4 or 6 perspectives, depending on what you consider it to be. Clifford Pickover did a talk on the making of his newest book, called The Math Book, and Glen Whitney finished off the session with a talk on The Museum of Mathematics, which is to be built very soon. Another short break, and then the last session for the day began.

First, there was a 30-minute talk on “The Art of Throwing Up” which is not what you may think it is. It was actually about juggling, and by the end of the talk I could actually juggle three scarves without grabbing everywhere. Tomas Rokicki, one of the programmers of Golly and a searcher for God’s Number on the Rubik’s Cube, then did a talk on ‘Modern Life” which was about recent developments in Conway’s Game of Life patterns. David Spies introduced GamesCrafters, a service where you can play around  70 games against a perfect opponent, and Robert Bosch talked about using the Traveling Salesman Problem to generate artworks. Sandro Del-Prete also did a talk about some of his illusions, a few of which were animated. Alex Bellos, author of a new book, Here’s Looking at Euclid ( Alex’s Adventures in Numberland in Britain) talked about why they still use abacuses in Japan (those kids are scary fast), and Eve Torrence, lastly, gave an improvement to Lewis Carroll’s Condensation Method.

Afterwards, we went to the 50th floor of a nearby tower for a large dinner with other attendees of G4G9. After the dinner, we were led into one of a few rooms where we were shown a number of short magic shows. I was in the room with Gareth Conway and John Conway, who I talked with about the Game of Life (it was originally simulated on Go boards), the talk about Nimbers he gave, and the Century Sliding Block Puzzle, which he apparently found by modifying the L’Ane Rouge puzzle. The magic shows were great, and I noticed that for some reason, Gareth, my mom, and I were chosen very frequently. Some of my favorite acts were a trick by Victoria Skye, who had 3 cards which would correspond to any answer to one of the questions she asked you; A trick by Mark Mitton in which he would place a card on the table, stand on top of a chair in a corner, and the card would turn out to be whatever the person named; and nearly all of Lennart Green’s card tricks. I was especially amazed by a trick by John Railing in which he turned a pack of cards into a sheet of plexiglass. This was especially amazing to me because I was holding the pack of cards at the time, and my hand was small enough that I could see in from the outside, and I still couldn’t tell when the switch happened.

Afterwards, we went back to our hotel and went to sleep, amazed by what had happened today.

G4G9, Day 1: Pencils, Optical Illusions, and Bar Bets

Continued from the previous post

The next day, Wednesday, was the first official day of Gathering For Gardner. The only session that day was the Bar Bets section, which was where the magicians and some mathematicians would show various tricks and trick bets which were mathematically related or interesting. However, the session was in the afternoon, so in the morning we had some time to do whatever we wanted to.

Julian Ziegler Hunts and his family had arrived overnight, so we got to have breakfast with them, in which he showed me some interesting Minsky Circle maps based on varying ξpsilon and zeta in the Minsky circle algorithm and plotting the period. After this, my mom and I, as well as the Zieglers and Gosper slept in until 11:00,at which point we decided to head back over to Tom Rodger’s house to play with puzzles while we waited for the session to begin.

As I have mentioned before, Tom has a huge collection of puzzles and sculptures. Since Julian had never been here before, and Tom was on a quick errand, I quickly gave him a tour of the house. Inside the puzzle rooms, Bill noticed that there were many impossible objects made by Gary Foshee, who makes sculptures where the puzzle is to determine how the object got into the current state, not to get it out. A classic example is of the “arrow through the coke bottle”:

Of course, Tom had many others, such as multiple coke bottles, strung together in impossible ways:

Later, Tom Rodgers came back from his errand and showed us some secret closets filled with puzzles. He placed out a few of his favorites on the table for us, and we attempted to solve all of them:

Many of the puzzles I knew the solution to, such as the nails puzzle and the ring puzzle, others I was able to solve, but the majority of them completely stumped me and everyone else. Akio Hizume showed us two interesting programs he wrote, called Real Number Music and Real Kekak System. They were both based on using the coefficients of the continued fraction of the number to generate music, and often made music which I think I’ve heard in some songs. At around 2:00 P.M., we went to the Ritz-Carlton for the before-conference meet.

There at the meet were lots of people who were going to G4G9, such as Lucas Garron, a speedcuber who has some very interesting modded cubes, such as one which transforms the edges to the corners and the corners to the edges, and is equivalent to a Shepard’s cube. There were many puzzles there, including Oskar’s Gears and a set of 9 3×3 paper-folding puzzles which varied from easy to AAUUGGHH! I also got to meet Sandro Del-Prete, one of my favorite optical illusion artists and talk to him about his optical illusions and what he was inspired by to make some of his drawings. He didn’t have perfect English, and my German is terrible, so my mom had to act as a translator at some parts. I was still able to understand what he was saying, even in German, though.

by Sandro Del-Prete

At around 6:30, we were led into an adjoining room for the Bar Bets session, in which various people demonstrated interesting and amazing magic tricks and bar bets. One person attempted unsucessfuly to drop a cork so that it would balance on its edge, another was successful at the same thing with matchboxes. The Great Jordini showed how to solve a certain puzzle by blowing on it, and I even got to solve a simple matchstick puzzle, shown below:

Get the dime out of the glass by moving only two matchsticks

Many of the tricks originated from Martin Gardner, such as a trick where a person moves a ring from a lower upperhand knot to a higher one. This went on until around 11:30, at which point we went back to our hotel and slept.

Naturally, I was excited for tomorrow.