Cubesnakes

Wren

Flaccid Member
Oct 16, 2006
423
0
0
Marklar
₥0
I expected this to just be a little dorky thing of mine, but it appears to be interesting to a lot of my friends. So what the hell, for your possible enjoyment.

My roommate has a little puzzle called a cubesnake. Looks like this while unfolded:

64745a9e3af72428.jpg


And the idea is that you try to fold it up into a 3x3x3 cube, like this:

64745a9e3af6d60e.jpg


As people played with it over the quarter, it was only a matter of time really until someone broke it. So we went to go buy a new one and found 3 different places selling them. Interested in what different puzzles we might find, my roommate ordered all 3. We then discovered that they are all the same puzzle.

Now I'm sure if you think about it for a while you can see that there is more than one way to make a puzzle like this. But how many, exactly? I wrote a program in C++ to figure it out.

How many would you expect? I find this an interesting exercise in human estimation. Answer in the tags.

There are 11,487 snakes that can be solved to at least one 3x3x3 cube.
Don't read on before you guess!

Naturally this spawned curiosity about other sizes. So after adapting the program to fit any dimensions and optomizing a little, I started it to work on 4x4x4 on Monday night. Midday Tuesday the program crashed when it found the 1,000,000th solution, exceeding the memory allocated for solution storage.

I reworked the code to let any number of snakes in, looked through the logs and developed a rough heuristic to estimate the total number of 4x4x4 snakes based on how fast it finds them in the first 12 hours. In total I estimate there are 75 million 4x4x4 snakes that can be folded at least one way into a cube. I also estimated that the program, had it not crashed, would have taken until early April to finish.

So I backed down a little and started it on a 4x3x3 rectangular solid. That started Wednesday, and is still going. It's found 630,319 so far, and my hueristic estimates it will find 1.75 million. It should be finished by late next week.

Here is the results output text file from 3x3x3:

results.txt
 
Wow, now THAT is some geeky luvin! How large is the program? Are you into math? I'm not even sure I'd know how to even begin writing such a program.
 
Wow, now THAT is some geeky luvin! How large is the program? Are you into math? I'm not even sure I'd know how to even begin writing such a program.

It's not that big. I just checked, and it says 86 lines long.

I'm competent at math, and every now and then a problem like this will catch my interest, and I'll enjoy solving it. Unfortunately if I tried to do it for a living I think it would drive me insane.

And yeah, it took me and 3 roommates like 2 hours of discussion to conceptualize a basic algorithm and code structure :p
 
So does it test each possible combination brute force style or is there some topology going on?
 
So does it test each possible combination brute force style or is there some topology going on?

Some, in a branching style. It finds solutions by trying paired indexed vectors. 0 and 1 are along the x axis, positive and negative, 2 and 3 are y, 4 and 5 are z. Fortunately for a problem like this, if n values are already untenable, any combinations beginning with those n values will also be. So for example if it finds that 002030 is untenable, then it skips all the attempts beginning with that.

It does this by feeding back and forth along a length of snake. When it finds one that works, it accepts it and tries to glue another brick on. When it doesn't, it tries the last one in a different place. If it's out of places to glue the last one, then it tries the one before that.

Sorry if that's unclear, it's difficult to summarize accurately.
 
Last edited:
Some, in a branching style. It finds solutions by trying paired indexed vectors. 0 and 1 are along the x axis, positive and negative, 2 and 3 are y, 4 and 5 are z. Fortunately for a problem like this, if n values are already untenable, any combinations beginning with those n values will also be. So for example if it finds that 002030 is untenable, then it skips all the attempts beginning with that.

It does this by feeding back and forth along a length of snake. When it finds one that works, it accepts it and tries to glue another brick on. When it doesn't, it tries the last one in a different place. If it's out of places to glue the last one, then it tries the one before that.

Sorry if that's unclear, it's difficult to summarize accurately.

would love to see your c0d3
 
Some, in a branching style. It finds solutions by trying paired indexed vectors. 0 and 1 are along the x axis, positive and negative, 2 and 3 are y, 4 and 5 are z. Fortunately for a problem like this, if n values are already untenable, any combinations beginning with those n values will also be. So for example if it finds that 002030 is untenable, then it skips all the attempts beginning with that.

It does this by feeding back and forth along a length of snake. When it finds one that works, it accepts it and tries to glue another brick on. When it doesn't, it tries the last one in a different place. If it's out of places to glue the last one, then it tries the one before that.

Sorry if that's unclear, it's difficult to summarize accurately.
It is unclear, but I got the mechanism. I'd say post the code but my C skills are weak.
 
would love to see your c0d3

I'm going to do it anyway, because I can.

It is unclear, but I got the mechanism. I'd say post the code but my C skills are weak.

Here's the excerpt I think you're interested in:

Code:
while (snake[2][0]<=2) // Until the third block, labled 2, finishes the +y segment (the rest are rotations).
      {
      //First the current values need to be checked (starting with block 2).  
      //If it does check out, then down the line farther. 
      if (check())
         {
         length++;
         //And now checking for and handling a complete string.
         if (length==bricks)
            {
            store(); //Flattens and stores cubesnake, then displays it if it's a new flat snake.
	    snake[length-1][0]=0; 
	    snake[length-2][0]=0; //Last 3 will always fit in only one way ...
	    length=length-3;
	    snake[length][0]++;
            exh();
            }
      }else{
           //If it doesn't check out, then we increase by one and normalize it with exh(); to the next valid node. 
           snake[length][0]++;
           exh();
           }
      }

void exh()
{
while (snake[length][0]==6) //6 is not a valid vector code, so it's ran out of thigns to try on this node. Moving back a node:
      {
      snake[length][0]=0;
      length--;
      snake[length][0]++;
      }
}

:n3rd:
 
Yeah, I couldnt make that faster. Im not sure how the puzzle is mechanically connected but couldnt you also just find every unique path through a 3x3x3 grid that goes through each vertex once? Then ditch rotations and mirrors.
 
Yeah, I couldnt make that faster. Im not sure how the puzzle is mechanically connected but couldnt you also just find every unique path through a 3x3x3 grid that goes through each vertex once? Then ditch rotations and mirrors.

Theoretically, but I don't really have a ball on if it would be faster or not. The problem is that the 3x3x3 cube can start in a corner, the middle of a side, the middle of a face, or the dead center. It can also end in each of those. So you'd produce an assload of mirrors, because you'd have to run at least n-1 of them, or 3. That would make the output roughly 2/3 mirrors. It would also still have the basic problem of generating many solutions for one snake. It could be better, I don't really know.

The other idea is to generate the flattened snakes systematically, then see if they have a solution. That might work ... it increases the amount of time needed to check things, but decreases the things to be checked/eliminated from 6^n (n is the length of the snake) to 2^n.
 
Theoretically, but I don't really have a ball on if it would be faster or not. The problem is that the 3x3x3 cube can start in a corner, the middle of a side, the middle of a face, or the dead center. It can also end in each of those. So you'd produce an assload of mirrors, because you'd have to run at least n-1 of them, or 3. That would make the output roughly 2/3 mirrors. It would also still have the basic problem of generating many solutions for one snake. It could be better, I don't really know.

The other idea is to generate the flattened snakes systematically, then see if they have a solution. That might work ... it increases the amount of time needed to check things, but decreases the things to be checked/eliminated from 6^n (n is the length of the snake) to 2^n.
Going further down the elegent math path is way out of my depth. I hated combination analysis.
 
Last edited:
Theoretically, but I don't really have a ball on if it would be faster or not. The problem is that the 3x3x3 cube can start in a corner, the middle of a side, the middle of a face, or the dead center. It can also end in each of those. So you'd produce an assload of mirrors, because you'd have to run at least n-1 of them, or 3. That would make the output roughly 2/3 mirrors. It would also still have the basic problem of generating many solutions for one snake. It could be better, I don't really know.

The other idea is to generate the flattened snakes systematically, then see if they have a solution. That might work ... it increases the amount of time needed to check things, but decreases the things to be checked/eliminated from 6^n (n is the length of the snake) to 2^n.
I really love reading about shit that is likely just beyond my current competency level. Thanks for the info so far.