Snakes

N-space Snakes are special maximal length loops through an N-space cube. They’re full of intriguing symmetries, puzzles and surprises. They’re simple structures that baffle us with their complexities. Fascinating creatures. Let’s go find some Snakes.

In this session: We’ll define what a Snake is, Search for 3,4, and 5-space snakes by hand, Identify snakes with binary names, Identify snakes by their column changes, Find the unique snakes up through 6-space, Look at a snake’s physique-l makeup, and ask some questions that maybe you will answer.

Me.

So, what IS an N-space Snake?

A “Snake” is a closed path (loop) through an N-space cube. But, the path must follow one special rule. You must understand that rule in order to create valid snakes.

000

001

010

100

011

101

110

111

The green lines form a valid 3-space snake of length 6.

That special rule is: No point on a snake (other than the preceding and succeeding points on the snake) can be within one line length of any other point on the snake. 000

001

010

100

011

101

110

111

This is an invalid snake because point 011 is one length away from 010, and both points are already part of the snake.

Every point (b) on the snake has one point that comes before it (a), and one that comes after it (c). Points a and c are one length away from b. a

000

b

001

010

100

c

011

101

110

111

No other point on the snake can be just one length away from point b. If it is, the snake is invalid. That’s the case here. Point 101 is one length away from point 001.

A point is “adjacent” to another if it is one line length away. The “adjacents” of a point are those points that are one line length away. a b

001

c

011

d

000

010

100

101

110

111

The points a, c, and d are adjacent to point b. a, c, and d are the adjacents of point b.

We will be looking for maximal length snakes which I call Great Snakes. The snake shown here is valid, but is not a Great Snake because it is not the longest snake possible in 3-space. a b

001

c

011

d

000

010

100

101

110

111

This is a valid 3-space snake of length 4. It is not a maximal length (Great) snake.

The longest snake possible in a 3-space cube is a snake of length 6.

a b

001

c

011

d

000

010

100

101

110

111

This is a valid 3-space Great Snake.

The longest snake in a 4-space cube is of length 8. You may wish to print this page and try to find a 4-space Great Snake on your own. 0000

0001

0011

0101

0111

0010

0100

1001

0110

1011

1101

1111

1000

1010

1110

1100

This is an invalid 4-space snake. Do you see why?

0000

0001

0011

0101

0111

0010

0100

1001

0110

1011

1101

1111

1000

1010

1110

1100

It is invalid because points 0010 and 0110 (which are already on the snake) are within one line length of each other.

0000

0001

0011

0101

0111

0010

0100

1001

0110

1011

1101

1111

1000

1010

1110

1100

Do you see why this snake is invalid? 0000

0001

0011

0101

0111

0010

0100

1001

0110

1011

1101

1111

1000

1010

1110

1100

Actually, there are two problems here. The point 1010 is adjacent to both 0010 and 1011 which are part of the snake.

0000

0001

0011

0101

0111

0010

0100

1001

0110

1011

1101

1111

1000

1010

1110

1100

Is this a valid 4-space snake? Is it a Great Snake? 0000

0001

0011

0101

0111

0010

0100

1001

0110

1011

1101

1111

1000

1010

1110

1100

This snake is a valid 4-space Great Snake.

0000

0001

0011

0101

0111

0010

0100

1001

0110

1011

1101

1111

1000

1010

1110

1100

Here’s another 4-space Great Snake. From now on, when I say “snake”, I will usually be talking about Great Snakes. 0000

0001

0011

0101

0111

0010

0100

1001

0110

1011

1101

1111

1000

1010

1110

1100

Once you know the rules for finding a snake, it is trivial to find a 3-space snake and easy to find a 4-space snake. 5-space snakes take a little more work, although most people can find several without too much trouble. Give it a try...

Find me...

A 5-space cube

Maximal length snake = 14 00000

00001

00010

00100

01000

10000

00011

00101

01001

10001

00110

01010

10010

01100

10100

11000

00111

01011

10011

01101

10101

11001

01110

10110

11010

11100

01111

10111

11011

11111

11101

11110

Here’s a 5-space Great Snake 00000

00001

00010

00100

01000

10000

00011

00101

01001

10001

00110

01010

10010

01100

10100

11000

00111

01011

10011

01101

10101

11001

01110

10110

11010

11100

01111

10111

11011

11111

11101

11110

To become more familiar with our snakes, we have to uniquely identify them . We have to name them. My name is Joe Finklesnake III

One way to name a snake is to list the points that make up the snake. They must be listed in order; otherwise they won’t be a valid snake. 0000

0000 0001

0010

0100

1000

0001 0011 0111 1111

0011

0101

1001

0110

1010

1100

1110 1100 1000

0111

1011

1101

1111

1110

But since there is no head or tail to the snake, you can start anywhere on the snake, and list the points as you follow the path back to your starting point. 0000

0001

0011

0101

0111

0010

0100

1001

0110

1011

1101

1111

1000

1010

1110

1100

0000

1111

0001

0111

0011

0011

0111

0001

1111

0000

1110

1000

1100

1100

1000

1110

Although the two “lists” are different, they are really the same snake. They just start at different points and go in opposite directions. Start 0000

0001

0011

0101

0111

0010

0100

1001

0110

1011

1101

1111

Start

1000

1010

1110

1100

0000

1111

0001

0111

0011

0011

0111

0001

1111

0000

1110

1000

1100

1100

1000

1110

So a single snake can have many different binary names. Since these particular lists appear to rotate vertically, they are called “vertical rotations” of each other. 0000

1000

1100

1110

1111

0111

0011

0001

0001

0000

1000

1100

1110

1111

0111

0011

0011

0001

0000

1000

1100

1110

1111

0111

0111

0011

0001

0000

1000

1100

1110

1111

1111

0111

0011

0001

0000

1000

1100

1110

1110

1111

0111

0011

0001

0000

1000

1100

1100

1110

1111

0111

0011

0001

0000

1000

1000

1100

1110

1111

0111

0011

0001

0000

Pretend that our 4-cube is a round transparent Christmas tree ornament suspended by a red ribbon from the 0000 point.

There are other rotations too. 0000

0001

0010

0100

0000

1000

0001 0011 0111

0011

0101

1001

0110

1010

1100

1111 1110 1100 1000

0111

1011

1101

1111

1110

0000 0001 0011 0111 0000

1111 1110

0001

0010

0100

1000

1100 1000

0011

0101

0111

1001

0110

1011

1101

1111

1010

1110

1100

If we slowly twirl the ornament, some of the points would appear to change places with other points on the same level and the snake would appear to move around the ornament.

0000 0001 1001 1101 0000

1111 1110

0001

0010

0100

1000

0110 0010

0011

0101

0111

1001

0110

1011

1101

1111

1010

1110

1100

If you twirled just the snake, and not the ornament, you could make an intuitive leap and call the resulting snakes “horizontal rotations” of each other.

Rotate the 4 Column to the right hand side.

Rotated Snake

Old Snake

Columns

4321

4

3

2

1

3

2

1

4

3214

0000

0

0

0

0

0

0

0

0

0000

0001

0

0

0

1

0

0

1

0

0010

0011

0

0

1

1

0

1

1

0

0110

0111

0

1

1

1

1

1

1

0

1110

1111

1

1

1

1

1

1

1

1

1111

1110

1

1

1

0

1

1

0

1

1101

1100

1

1

0

0

1

0

0

1

1001

1000

1

0

0

0

0

0

0

1

0001

The horizontally rotated list of points looks very different, so you might think that you have a new, different snake. But, it’s really the same old snake rotated.

Horizontally inter-mixed Columns

New Snake

1

2

4

3

1

2431

0

0

0

0

0

0

0000

0

0

1

0

0

0

1

0001

0

0

1

1

1

0

0

1

1001

0111

0

1

1

1

1

0

1

1

1011

1111

1

1

1

1

1

1

1

1

1111

1110

1

1

1

0

1

1

1

0

1110

1100

1

1

0

0

0

1

1

0

0110

1000

1

0

0

0

0

1

0

0

0100

Old Snake

Columns

4321

4

3

2

0000

0

0

0001

0

0011

In fact, if you exchange any column of a given snake with any other column of the same snake, you have an intermixed rotation of the snake, and it is really the same snake as before even though the list of points is very different.

There are other intriguing ways to name our snakes.

You can call me Joe

My name is Joe Finklesnake III

This picture shows colored linesets as well as points of a 4-space cube.

0000

1

0001 2

0011

31

3

0010 4

1

0101 3

2

421

0111

1000

421

42

0110 3

4

1101 3

2

1111

3

1010

1

1011 4

0100 3

1001

42

4

31

1110 1

1100 2

0000 0001 0011 0111 1111 1110 1100 1000

0000 1

0001 2

0011 3

2

3

0010

4

0100

1000

Instead of using the3 points to name the42 4 1 421 snake, we can use the column number between each of the snake’s 8 points. 0101 1001 0110 This snake’s name would then be: 1010 12341234 31

42

421

0111

3

1

1011 4

4

1101 3

2

1111

31

1110 1

3

1100 2

Snake named by its points

Snake named by column changes

Columns

4321

4

3

2

1

0000

0

0

0

0

0001

0

0

0

1

1

0011

0

0

1

1

2

0111

0

1

1

1

3

1111

1

1

1

1

4

1110

1

1

1

0

1

1100

1

1

0

0

2

1000

1

0

0

0

3

0000

0

0

0

0

4

It turns out that the column-change naming convention is a more effective, efficient, easy method of naming snakes. And it highlights something we might not have seen otherwise.

Snake named by its points

Snake named by column changes

4321 0000

This snake appears to be made from two “identical” halves. 1

0001

1

2

0011

2

3

0111

3

4

1111

4

and

1110

1

1

1100

2

2

1000

3

3

0000

4

4

The column-change naming convention reveals structures within the snake that we did not expect to find.

Now, we can name this 5-space snake two different ways. 00000

Binary snake name 00000 00010 00110 01110 00011 11110 11010 11011 10011 00111 10001 10101 11101 01101 01001 01000

00001

00010

Column-change name

00100

01000

2

10000

3 00101

01001

01011

10011

01111

10001

01101

10111

00110

01010

10101

11001

11011

11111

10010

01110

11101

01100

10100

10110

11010

11110

4

11000

5 3 1 4 11100 2 3 4 5 3 1 4

A 5-space Cube

Symmetry, symmetry, everywhere and what a lot to think. 00001

A 4-space cube

00000

00010

00100

01000

10000

00011

00101

01001

10001

00110

01010

10010

01100

10100

11000

00111

01011

10011

01101

10101

11001

01110

10110

11010

11100

01111

A 4-space cube

10111

11011

11101

11110

2345314 2345314 11111

This gives us a clue as to how we might construct N-space snakes from (N-1)-space snakes. 00001

5-space cube A 4-space cube

00000

00010

00100

01000

10000

00011

00101

01001

10001

00110

01010

10010

01100

10100

11000

00111

01011

10011

01101

10101

11001

01110

10110

11010

11100

01111

A 4-space cube

10111

11011

11101

11110

23453142345314 11111

Just how big do these snakes get?

We don’t know how big they are above 7-space.

This Big 0-space 1-space 2-space 3-space 4-space 5-space 6-space 7-space

0 1 4 6 8 14 26 48

Now, it might be informative to catalog all of the snakes in an N-space cube to see how each of them is constructed. That could give us a clue as to how to construct snakes in higher N-space cubes. However, a lot of the snakes are just transformations of each other. The N-cubes appear to be infested with snakes!

If we throw out all of the duplicate snakes, how many are left? How many UNIQUE snakes are there in each N-cube?

First, you have to find them all. How do you do that? One way is to write a computer program that exhaustively searches for them. I wrote one and named it

TailWagger

You could find all of the snakes in an N-space cube if you tried all of the possible paths. This is called the BFI or Brute Force and Ignorance method. 0000

0001

0011

0101

0111

0010

0100

1001

0110

1011

1101

1111

1000

1010

1110

1100

TailWagger starts at point 0000. It chooses one of four possible points. It then has three more choices, chooses one and checks to see if the snake has violated any rules. 0000

0001

0011

0101

0111

0010

0100

1001

0110

1011

1101

1111

1000

1010

1110

1100

If TailWagger chooses a point that violates a rule, it backtracks and tries one of the other points. 0010 would have to link with 0000 but the snake is still too small. 0000

0001

0011

0101

0111

0010

0100

1001

0110

1011

1101

1111

1000

1010

1110

1100

If no rules have been violated, it continues choosing new points. If all three choices violate a rule, it backtracks to the previous point and chooses another point there. 0000

0001

0011

0101

0111

0010

0100

1001

0110

1011

1101

1111

1000

1010

1110

1100

When it finds a valid snake it prints it out. Then it backtracks (as if it had found an error) and chooses other points that haven’t been tried. 0000

0001

0011

0101

0111

0010

0100

1001

0110

1011

1101

1111

1000

1010

1110

1100

Eventually, it backtracks all the way to the third node where the program stops. Do you see why it isn’t necessary to backtrack to the first point to try all of the possibilities there? 0000

0001

0011

0101

0111

0010

0100

1001

0110

1011

1101

1111

1000

1010

1110

1100

Once TailWagger found all of the snakes (up through 6-space) all of the duplicate snakes had to be thrown out in order to determine the number of unique snakes and their composition.

X

X X

The matter required a bit of careful thought.

Are these two snakes the same?

12341243 12431234 They are if the second snake is a vertical, horizontal, or intermixed rotation of the first snake.

Yes, the second snake is a rotation of the first.

1234124312341243 12431234

Here, we duplicated the first snake (red numbers) and shifted the second snake to the right. The numbers match. The snakes are the same.

Are these two snakes the same?

12341243 32134214 They are if the second snake is a vertical, horizontal, or intermixed rotation of the first snake.

Yes, the second snake is a rotation of the first.

1234124312341243 41243123

Here, we duplicated the first snake (red numbers), turned the second snake around (32134214 to 41243123) and shifted the second snake to the right. The numbers match. The snakes are the same.

Are these two snakes the same?

12341243 41342132 They are if the second snake is a vertical, horizontal, or intermixed rotation of the first snake.

Yes, the second snake is a shifted, inter-mixed rotation of the first.

1 2 3 4 1 2 4 3 1 2 3 4 1 2 4 3 first snake 4 1 3 4 2 1 3 2 second snake 4 1 2 4 3 1 2 3 second snake with 3s and 2s swapped 4 1 2 4 3 1 2 3 second snake shifted right 1 2 3 4 1 2 4 3 1 2 3 4 1 2 4 3 first snake In the second snake we changed every 2 to a 3 and every 3 to a 2. Then we shifted it to the right. The numbers match. The snakes are the same.

I promised you a third way to name snakes.

I’m from the class of 65

My name is Joe Finklesnake III

Snakes can be partially described by using the following trick.

2345314234531423453142345314 .....1......1......1......1. 2......2......2......2...... .3..3...3..3...3..3...3..3.. ..4...4..4...4..4...4..4...4 ...5......5......5......5... 1 2 3 4 5

77 77 3434 4343 77

1 occurs every 7th number 2 occurs every 7th number 3 occurs every 3rd, 4th, 3rd, 4th number 4 occurs every 4th, 3rd, 4th, 3rd number 5 occurs every 7th number

Because transformations or rotations of snakes are equivalent, the following two snakes are in the same class. The are the same snake. Snake 1 Snake 2

23453142345314 25435142543514

Snake 1 1 77 2 77 3 3434 4 4343 5 77

Snake 2 1 77 2 77 3 77 4 4343 5 3434

In order to unmask the unique snakes, every snake in an N-space cube must be compared to every other snake in the N-space cube to see whether they are forward, backward (vertical) and / or intermixed rotations of each other. Will the Real Unique Snakes Please Step forward ?

These are unique snakes for N<7. 3-space

123123

4-space

12341234 12341243 12342143

5-space

12345214234524 12345231243253 12345241234524

6-space

12345612541561236541256154 12345612542341254361234254 12345634235415362564356253 12345634235431234563423543 12345634235431243563423543

Why hasn’t TailWagger found every snake in 7-space? Because the upper bound for the number of TailWags (iterations) for N>6 is

It will never find them all.

3-space 3**6

= 7.2x10**2

= 729

4-space 4**8

= 6.5x10**4

= 65536

5-space 5**14

= 6.1*10**9

= 6103515625

6-space 6**26

= 1.7*10**20

= 170581728179578208256

7-space 7**48

= 3.6x10**40

= 36703368217294125441230211032033660188801

So, we’ve come to the end with lots of questions. How long are the snakes in an N-space cube? What are the unique snakes in an N-space cube? What governs the construction of snakes? Are there equations that describe all of these things?

We don’t know… yet.