The problem: given a broken snake cube puzzle, find out the order in which to re-string the pieces which will result in a repaired, solvable puzzle.
Briefly, the puzzle is a bunch of wooden cubes strung together on an elastic cord. You can't change the order, but you can fold it different ways; the goal is to fold them into a 3x3 cube. The individual cubes are either straights — the cord goes through without turning — or corners — which give you the solver the choice of which way to fold at that piece. (And there are the two ends.)
I wrote a solver, for which the code is on github. It is not especially fast (recursive backtracking; exhaustive search for these pieces took almost two hours on a 2.4GHz i5 MBP). It does allow for arbitrary target shapes — which I have only minimally used, but what if the puzzle was to fold a fish? — and possibly arbitrary puzzle pieces too (a Y?).
Above, verifying one solution by hand. Below: tested in meatspace!
The original elastic cord had broken. I spliced in some fishing line (whatever was on hand), and Geoff engineered a new attachment plug out of pencil wood. (Only minor injuries were sustained.)
2011-11-11 / Python
In: Code
Created by and © 2011 Mark Fickett except where noted. I try for valid XHTML 1.0 Strict and CSS.