19
$\begingroup$

I have a wooden snake puzzle in my collection that has been unsolved for years. I wondered if any of you might be interested. I have fiddled with it, but think it might need dynamic programming or something to solve. But maybe some of you have an approach that would work.

The puzzle is pictured below. It consists of 64 wooden cubes each of which (except the ends) has a hole in the center of two of the faces. An elastic is threaded through the whole thing so that the pieces can swivel in place. The objective is to arrange it into a 4x4x4 cube.

Snake Puzzle

So, for example, starting at the bottom end (in the picture), there are 3 in a row. The last of these three has the fourth cube coming off at right angles. The direction it comes off can be swivelled, and that entire next segment (also 3 in a row: blocks 4-6) can swivel around so that it doubles back on itself, or sticks out at right angle or continues straight with a kink.

The last of these is impossible, of course, because the length would be 5 and therefore it would not fit into a 4x4x4 cube.

Here is a description of the entire snake:

3 - 2 - 3 - 2 - 2 - 4 - 2 - 3 - 2 - 3 - 2 - 3 - 2 - 2 - 2 - 2 - 2 - 2 - 2 - 2 - 3 - 3 - 2 - 2 - 2 - 2 - 2 - 3 - 4 - 2 - 2 - 2 - 4 - 2 - 3 - 2 - 2 - 2 - 2 - 2 - 2 - 2 - 2 - 2 - 4 - 2

In the above sequence, each corner is counted twice. There are 46 segments, so 45 corners, which is why the above numbers sum to 109 rather than 64. Hopefully that makes sense.

Would love to hear your thoughts. Even partial insights would be helpful.

Enjoy!

Thanks to @Jaap Scherphuis, it is now neatly solved! Me: >10 years without success. The internet: <1h. Gotta love it.

Snake puzzle - solved

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I bought that a couple of months ago. Now here I am, on Puzzling; reading through this very post; looking at this very particular puzzle. Sometimes, I feel like I might have cosmic powers... (though I, as well, could not turn the wooden snake into a cube). $\endgroup$
    – Mr Pie
    Commented Jul 20, 2018 at 5:52

2 Answers 2

Reset to default
23
$\begingroup$

I have the same snake cube puzzle, except that its cubes don't alternate in colour. On mine they are coloured so that the finished cube consists of 2x2x2 blocks.

Drawing of the solution is under the spoiler:

enter image description here

The 3x3x3 version of this puzzle is very common, though almost all versions use the same configuration of straight and bent cubes. You can find out more about these smaller versions on my snake cube page.

Improve this answer
$\endgroup$
3
  • $\begingroup$ That's amazing! How did you solve it in the first place? Or did you somehow maintain the solution? $\endgroup$
    – Dr Xorile
    Commented Oct 19, 2017 at 19:07
  • 5
    $\begingroup$ I solved mine by hand, but it is easier than yours because of the colouring. I also have a javascript program to solve the 3x3x3 version on the page I linked to. A few years ago I adapted that script to work for the 4x4x4 to create the picture above. If I remember correctly, the script also showed that the solution is unique (up to rotation/reflection). $\endgroup$
    – Jaap Scherphuis
    Commented Oct 19, 2017 at 19:13
  • $\begingroup$ Excellent answer and website. Thanks! Do you happen to still have the code for solving 4x4x4? It would be interesting to see. Since bruteforcing the 45**4 possibilities might not be the fastest solution. $\endgroup$
    – Eric Duminil
    Commented Jul 17, 2020 at 22:25
1
$\begingroup$

Late this July, have written a computer program which solves these, in a language called TXR Lisp. This is not packaged into anything nice with a GUI; it's just a function we can call from the interactive listener.

The code isn't graph-based; it isn't using graph representations to solve a Hamiltonian circuit. Rather it models the actual rotation and positioning of the pieces to form different foldings of the snake, and performs bounding box and shape checks to detect the solution or non-solutions.

Run the interpreter from the system prompt, loading the snake-cube.tl file which is hosted in a git repository here:

$ txr -i snake-cube.tl

Then use the solve function. Let's try an example in which we have a trivial snake: four straight pieces, solving for a 1x1x4 box:

1> (solve '(s s s s) 1 1 4)
(((s 0 0 0) (s 0 0 1) (s 0 0 2) (s 0 0 3)))

The input symbol s is a shorthand denoting a straight piece: a cube whose next face is attached to the face opposite to the incoming face. The other type of piece is e: elbow: the 90 degree bend.

The first and last cube of a snake don't attach to anything, and so it doesn't matter whether we specify them as s or e:

1> (solve '(s s s s) 1 1 4)
(((s 0 0 0) (s 0 0 1) (s 0 0 2) (s 0 0 3)))

Here, the program is telling us that starting with the straight piece at location <0, 0, 0>, facing upward (along the Z axis), there is exactly one solution for this trivial snake, which can only express a straight tetromino and nothing else. The numbers give the coordinates of the pieces in 3D space. The next piece is at <0, 0, 1>, and so we are stacking the cubes up the Z axis.

The output is a list of lists of (s ...) and (e ...) items. If there are multiple solutions, there are multiple lists.

Multiple solutions include symmetric solutions: rotations and reflections. If we have eight pieces, six of which are elbows, we can fold them into a 2x2x2 cube, and 24 ways are found of doing this:

3> (solve '(s e e e e e e e) 2 2 2)
(((s 0 0 0) (e 0 0 1) (e 0 1 1) (e 0 1 0) (e 1 1 0) (e 1 1 1) (e 1 0 1)
  (e 1 0 0))
 ((s 0 0 0) (e 0 0 1) (e 0 1 1) (e 0 1 0) (e 1 1 0) (e 1 0 0) (e 1 0 1)
  (e 1 1 1))
 ((s 0 0 0) (e 0 0 1) (e 0 1 1) (e 0 1 0) (e -1 1 0) (e -1 1 1)
  (e -1 0 1) (e -1 0 0))
 ((s 0 0 0) (e 0 0 1) (e 0 1 1) (e 0 1 0) (e -1 1 0) (e -1 0 0)
  (e -1 0 1) (e -1 1 1))
 ((s 0 0 0) (e 0 0 1) (e 0 1 1) (e 1 1 1) (e 1 0 1) (e 1 0 0) (e 1 1 0)
  (e 0 1 0))
 ((s 0 0 0) (e 0 0 1) (e 0 1 1) (e -1 1 1) (e -1 0 1) (e -1 0 0)
  (e -1 1 0) (e 0 1 0))
 ((s 0 0 0) (e 0 0 1) (e 0 -1 1) (e 0 -1 0) (e 1 -1 0) (e 1 -1 1)
  (e 1 0 1) (e 1 0 0))
 ((s 0 0 0) (e 0 0 1) (e 0 -1 1) (e 0 -1 0) (e 1 -1 0) (e 1 0 0)
  (e 1 0 1) (e 1 -1 1))
 ((s 0 0 0) (e 0 0 1) (e 0 -1 1) (e 0 -1 0) (e -1 -1 0) (e -1 -1 1)
  (e -1 0 1) (e -1 0 0))
 ((s 0 0 0) (e 0 0 1) (e 0 -1 1) (e 0 -1 0) (e -1 -1 0) (e -1 0 0)
  (e -1 0 1) (e -1 -1 1))
 ((s 0 0 0) (e 0 0 1) (e 0 -1 1) (e 1 -1 1) (e 1 0 1) (e 1 0 0)
  (e 1 -1 0) (e 0 -1 0))
 ((s 0 0 0) (e 0 0 1) (e 0 -1 1) (e -1 -1 1) (e -1 0 1) (e -1 0 0)
  (e -1 -1 0) (e 0 -1 0))
 ((s 0 0 0) (e 0 0 1) (e 1 0 1) (e 1 0 0) (e 1 1 0) (e 1 1 1) (e 0 1 1)
  (e 0 1 0))
 ((s 0 0 0) (e 0 0 1) (e 1 0 1) (e 1 0 0) (e 1 1 0) (e 0 1 0) (e 0 1 1)
  (e 1 1 1))
 ((s 0 0 0) (e 0 0 1) (e 1 0 1) (e 1 0 0) (e 1 -1 0) (e 1 -1 1)
  (e 0 -1 1) (e 0 -1 0))
 ((s 0 0 0) (e 0 0 1) (e 1 0 1) (e 1 0 0) (e 1 -1 0) (e 0 -1 0)
  (e 0 -1 1) (e 1 -1 1))
 ((s 0 0 0) (e 0 0 1) (e 1 0 1) (e 1 1 1) (e 0 1 1) (e 0 1 0) (e 1 1 0)
  (e 1 0 0))
 ((s 0 0 0) (e 0 0 1) (e 1 0 1) (e 1 -1 1) (e 0 -1 1) (e 0 -1 0)
  (e 1 -1 0) (e 1 0 0))
 ((s 0 0 0) (e 0 0 1) (e -1 0 1) (e -1 0 0) (e -1 1 0) (e -1 1 1)
  (e 0 1 1) (e 0 1 0))
 ((s 0 0 0) (e 0 0 1) (e -1 0 1) (e -1 0 0) (e -1 1 0) (e 0 1 0)
  (e 0 1 1) (e -1 1 1))
 ((s 0 0 0) (e 0 0 1) (e -1 0 1) (e -1 0 0) (e -1 -1 0) (e -1 -1 1)
  (e 0 -1 1) (e 0 -1 0))
 ((s 0 0 0) (e 0 0 1) (e -1 0 1) (e -1 0 0) (e -1 -1 0) (e 0 -1 0)
  (e 0 -1 1) (e -1 -1 1))
 ((s 0 0 0) (e 0 0 1) (e -1 0 1) (e -1 1 1) (e 0 1 1) (e 0 1 0)
  (e -1 1 0) (e -1 0 0))
 ((s 0 0 0) (e 0 0 1) (e -1 0 1) (e -1 -1 1) (e 0 -1 1) (e 0 -1 0)
  (e -1 -1 0) (e -1 0 0)))

And so here is the first of eight solutions for one 3x3 snake that I have:

5> (first (solve '(s s e s e s e s e e e e s e s e e e s e e s e e e s s) 3 3 3))
((s 0 0 0) (s 0 0 1) (e 0 0 2) (s 0 1 2) (e 0 2 2) (s 0 2 1) (e 0 2 0)
 (s 1 2 0) (e 2 2 0) (e 2 2 1) (e 1 2 1) (e 1 2 2) (s 1 1 2) (e 1 0 2)
 (s 1 0 1) (e 1 0 0) (e 2 0 0) (e 2 1 0) (s 1 1 0) (e 0 1 0) (e 0 1 1)
 (s 1 1 1) (e 2 1 1) (e 2 0 1) (e 2 0 2) (s 2 1 2) (s 2 2 2))

Finally, let's try yours. From the image, I will try to transcribe the 64 pieces, starting with the bottom and going clockwise. Because this is slow, let us compile the code:

1> (compile-file "snake-cube")
t

The pprof macro wrapped around the calculation will give us the execution time and memory allocation stats:

4> (pprof (solve '(s s e e s e e e s s e e s e e s e e s e e e e e e e e e s e s e e e e e e s e s s e e e e s s e e s e e e e e e e e e e s s e s) 4 4 4))
malloc bytes:  5303878935384
gc heap bytes: 7484828731840
total:         12788707667224
milliseconds:      49936965
(((s 0 0 0) (s 0 0 1) (e 0 0 2) (e 0 1 2) (s 0 1 1) (e 0 1 0) (e 0 2 0)
  (e 0 2 1) (s 1 2 1) (s 2 2 1) (e 3 2 1) (e 3 2 0) (s 2 2 0) (e 1 2 0)
  (e 1 1 0) (s 2 1 0) (e 3 1 0) (e 3 1 1) (s 2 1 1) (e 1 1 1) (e 1 1 2)
  (e 1 2 2) (e 0 2 2) (e 0 2 3) (e 1 2 3) (e 1 1 3) (e 0 1 3) (e 0 0 3)
  (s 1 0 3) (e 2 0 3) (s 2 1 3) (e 2 2 3) (e 2 2 2) (e 2 1 2) (e 3 1 2)
  (e 3 2 2) (e 3 2 3) (s 3 1 3) (e 3 0 3) (s 3 0 2) (s 3 0 1) (e 3 0 0)
  (e 2 0 0) (e 2 -1 0) (e 3 -1 0) (s 3 -1 1) (s 3 -1 2) (e 3 -1 3)
  (e 2 -1 3) (s 2 -1 2) (e 2 -1 1) (e 2 0 1) (e 2 0 2) (e 1 0 2)
  (e 1 -1 2) (e 1 -1 1) (e 1 0 1) (e 1 0 0) (e 1 -1 0) (e 0 -1 0)
  (s 0 -1 1) (s 0 -1 2) (e 0 -1 3) (s 1 -1 3))
 [ ... snip 31 more solutions ])

It took almost 14 hours, and burned through over 11 Tb of garbage-collected memory allocations. The VM footprint stayed below 29 Mb the entire time.

Here is that one of the other solutions which contains only non-negative XYZ coordinates:

 ((s 0 0 0) (s 0 0 1) (e 0 0 2) (e 1 0 2) (s 1 0 1) (e 1 0 0) (e 1 1 0)
  (e 0 1 0) (s 0 1 1) (s 0 1 2) (e 0 1 3) (e 0 0 3) (s 1 0 3) (e 2 0 3)
  (e 2 0 2) (s 2 1 2) (e 2 2 2) (e 2 2 1) (s 2 1 1) (e 2 0 1) (e 2 0 0)
  (e 3 0 0) (e 3 0 1) (e 3 1 1) (e 3 1 2) (e 3 0 2) (e 3 0 3) (e 3 1 3)
  (s 2 1 3) (e 1 1 3) (s 1 1 2) (e 1 1 1) (e 1 2 1) (e 1 2 0) (e 2 2 0)
  (e 2 1 0) (e 3 1 0) (s 3 2 0) (e 3 3 0) (s 2 3 0) (s 1 3 0) (e 0 3 0)
  (e 0 2 0) (e 0 2 1) (e 0 3 1) (s 1 3 1) (s 2 3 1) (e 3 3 1) (e 3 2 1)
  (s 3 2 2) (e 3 2 3) (e 2 2 3) (e 2 3 3) (e 1 3 3) (e 1 2 3) (e 1 2 2)
  (e 0 2 2) (e 0 2 3) (e 0 3 3) (e 0 3 2) (s 1 3 2) (s 2 3 2) (e 3 3 2)
  (s 3 3 3))

Following these coordinates while twisting the cubes into place is still a bit of a mental challenge.

Improve this answer
$\endgroup$
10
  • $\begingroup$ 14 hrs!? Wow, that's pretty intense. I've been thinking about writing such a program myself. But I usually just sit down until the urge passes. Well done for doing it. I believe there's only one solution to the puzzle if you allow for the various symmetries $\endgroup$
    – Dr Xorile
    Commented Aug 20, 2021 at 21:37
  • $\begingroup$ @DrXorile I mean, whatever; it's 14 hours of some machine's time, not your time. Between work and kids, 14 hours goes by in a jiffy. This is running in a language that runs a kind of byte code VM, and using a fairly slow approach with objects and whatnot. A graph representation which traces hamiltonian circuits will likely run faster, plus a native-compiled language can be used. Still, I don't even own a 4x4x4 snake; the code is virtually instant on a 3x3x3 instance. $\endgroup$
    – Kaz
    Commented Aug 20, 2021 at 21:48
  • $\begingroup$ I know that feeling. I've done many Euler Project puzzles in, let's say, significantly more than the allotted 1 minute. But with much less of my more valuable time, so I'm with you all the way. And you got it done, so well done. +1 $\endgroup$
    – Dr Xorile
    Commented Aug 20, 2021 at 21:51
  • 1
    $\begingroup$ @DrXorile Actually I wrote this program out of frustration. I have one of these puzzles, as I mentioned. I've solved it quite easily a number of times in the past. It's been in a cabinet for a few years. My toddler got his hands on it and unravelled it. I'm just too tired or whatever, but I just wasn't able to solve it like before. I was up until 2 a.m. that day doing it. So I said, screw this, the time is better spent teaching the machine how to solve it than to solve it. Weeks later, I found this question. $\endgroup$
    – Kaz
    Commented Aug 20, 2021 at 22:05
  • 1
    $\begingroup$ @DrXorile I see. First and second. So of course that has no effect on s000 s001 e002. But we see the swap in e012 versus e102. According to a visual spot check, I see that there is a consistent swap of coordinates. Swap of a pair of coordinates means, of course different chirality: mirror image. $\endgroup$
    – Kaz
    Commented Aug 20, 2021 at 22:07

Not the answer you're looking for? Browse other questions tagged or ask your own question.