# Posts Tagged ‘hamiltonian circuits’

## 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.)