Archive for March, 2011

Hamiltonian and Eulerian Snakes

March 7th, 2011

George Sicherman recently sent in a solution to problem #17, tiling a Hamiltonian circuit of a 6×8 grid of vertices using the linear 3- and 4-sticks. In fact, he found all 51 solutions. Two of them have the property that all of the joints between polysticks occur at 90° angles. Here’s one, in the form of snakes:

(The other is a variation on this one where the order of two of the polysticks in the center of the top of the figure is swapped.)

Later, I saw that the same set of polysticks would fit into a 3×4 array of diamonds. All of the vertices in this figure have even degree, which means that it is possible to make Eulerian circuits on it. Sicherman sent in a solution to this one too:

Sorry, I was too lazy to turn it into snakes. For this problem, solutions like the above with no point where four polysticks meet are preferable, otherwise there would be more than one direction for a path to take. Although it would be nice if it could be done without any points where two polysticks cross, this is impossible. (The pieces contain 14 straight joints; if there are no crossings, each straight joint must also be the locus of two end points. Since each piece has two end points, and there are 13 pieces, there aren’t enough end points to go around.)

A Semimagic Magic 45-omino

March 1st, 2011

Bryce Herdt has found a solution to problem #21:

The shape of the darker region is “magic” because the number of cells in each 3×3 block corresponds to a number in a magic square, while the number of cells in each row, column, and main diagonal is 5. The sum of the numbers in each row and column is 115.

There’s still room for improvement here: note that the diagonals do not add up to the magic sum. (A mostly magic square with this property is called semimagic.)

Problem #21.1 Find a magic magic 45-omino, as above, but with diagonals adding to the magic sum.

It’s interesting that this solution was found by manually tweaking the output of a program that I wrote to solve the problem. I was never able to get the program to find an actual solution, so I had it give up after a certain number of trials and output the best near solution. There may well be a large number of solutions, but the search space is enormous.

It’s pretty simple to get fairly close by picking a random permutation of numbers and repeatedly swapping them around to get sums closer to the magic sum. But getting from this local minimum to a real solution is the hard part. The problem would seem to call for something like simulated annealing, and indeed I found a reference to a magic square finder algorithm using something similar. (It should be noted that if all you want is a magic square of a given size, there are deterministic methods that will get you one very quickly.) I added a hack to my code to make it do a crude version of this, but it doesn’t seem to have helped much. (The near solution that Herdt fixed up was made with the old version of the code.)

Feel free to look at my solver code (in Python). I do wonder if there is some way it can be fixed up to be better at getting from near solutions to real solutions.