How Many Unique Paths Through a 3x3x3 Cube Visiting All Vertices Once?

[trini]

ok, so here's the problem:

given a 3 x 3 x 3 cubic system of vertices, a starting vertex, and an end vertex, how many paths that pass through all vertices ONLY ONCE and start and end at the given vertices(for example let's say the starting and end vertices are two opposite corner vertices) can be formed? rules:

a)a vertex may only be passed through once
b) all vertices(in this case 27) must be passed
c)all motions are in the x, y, or z direction only(ie, diagonal vertices not connected) eg:
D----------E
| ..C
| ./
| /
A----------B

so if A is the starting vertex(a corner) it can then only go to B,C or D(not E as it is not immediately adjacent)[ps ignore the full stops by the path going to C, they are just there for spacing)

 

[trini]

here's what i have so far:

1)the path length would be 26(assuming adjacent vertices are separated by length one), ie, there are 26 moves to get from start to finish

2)an exhaustive tree can be used(though it is very tedious, which is why i want a better way to do this, especially for larger systems) eg:

A --> B --> E
A --> C -->...
A --> D -->E

and so on, with each new element in the path branching off to all its possible next steps. using this method, the end vertex is ignored as a possible next step of a vertex until turn 26 so as to satisfy condition (a) in the first post

 

[trini]

no ideas?

i'll try to write a MATLAB script to do this for me and post the results for future reference if anyone needs, will appreciate any thoughts in the meantime

 

[honestrosewater]

Well, I can think of a solution but not a necessarily nice one. If I were writing a procedure, I would model the nodes as 3-tuples (x,y,z) where the components denote, say, the plane, row, and column respectively, thinking of the graph as being matrices lined up behind each other parallel to you. So (1,1,1) is the top left node of the plane closest to you, and (2,3,2) is the bottom middle node of the middle plane.

The rule for moving is that the new node can differ from the current one by exactly 1 in exactly one component (and must of course be in the allowed range of {1,2,3} or whatever). So from (1,1,1), you can move to (2,1,1), (1,2,1), or (1,1,2). Then determining the possible next moves is easy.

How would you do it otherwise?

If you're more theoretically-inclined, the move relation on the nodes is irreflexive, symmetric, and antitrasitive (er, meaning (M(n₁,n₂) & M(n₂,n₃)) -> ~M(n₁,n₃)). I don't know anything about these kinds of relations, but surely they've been studied by someone.? You're looking for the simple paths where Edge(n₁,n₂) is in the path only if M(n₁,n₂). I.e., you want a simple-path filter for M.

 

[trini]

thats what I'm doing actually, however, you must remember, i am not only traveling the edges, i am traversing the entire cube(center of body and faces included) so some vertices have 4 nearest neighbours(edge ones), some have 5(face centers), and some have 6(inner vertices).

i used a lettering system for the model which, forgive the roughness, looks generally like this(fullstops there for spacing) :


......R----------X---------AA
....../|..../|..../|
...../.L.../.T.../.Z
......K-+--------S+--------Y..|
....../|.G.../|.O.../|..W
....../.F.../.N.../.V./
......E--+-------M-+-------U..|/
......|...C...|..I...|..Q
......B----------H----------P/
......|.....|.....|/
......A----------D---------J

for clarity, the back face is

R,X,AA
L,T,Z
G,O,W

the middle is

K,S,Y
F,N,V
C,I,Q

and the front is

E,M,U
B,H,P
A,D,J


So as you can see, N goes to 6 points[F,H,V,T,I,S]and O goes to [G,W,I,T]

thats how I am going to lay it out in matlab, assign an array to each vertex which has a list of that vertices nearest neighbours. at each step, it will create a new row vector for each nearest neighbour which can be moved to of the previous step's nearest neighbours.

If AA is the last step for example, it will be removed from the lists of all its nearest neighbours until turn 26.

 

[honestrosewater]

Right, I'm using "edge" generally as a connection between any two nodes.

The benefit of using tuples of numbers is that you don't need to manually input all the nearest neighbors. You can derive them automatically with a function that adds 1 and -1 to each component and throws out the result if it's out of range. The function for the next possible moves just additionally keeps track of (or references the variable containing) the nodes that have already been included in the path and your end node if you want to limit it that way.

 

[trini]

so, i got a working program, just started running it, broke it after about half an hour, was on path number 330,000 at turn 15! i think i will have to leave this running for a long time to get my answer...thank goodness i didn't try to do this by hand!

i find this amazing, a simple 3x3 cube, and my current estimates put me at about 80 million or more UNIQUE paths to get from one corner to the opposite!(though it should be noted only a select few of these actually manage to traverse the entire path, many simply collapse at some point) i have attached the code for anyone who is interested in this type of program =)

*note: path is the main file to be run, the other is the function file*

for larger cubes, one would have to expand the basis set in the function file as well as modify the number of turns to suit(total vertices -2)

i will post the final answer to the question whenever i do get it( i think this may take a few days tbh)

 

[trini]

good grief, its still running, anyone have access to a supercomputer to eat up this program for me? =)

 

[Edgardo]

I have written a program in python. The idea is similar to yours, namely to consider the neighbours
of a vertex:

Start at vertex 0, consider the neighbours of 0. For each of these vertices, consider its neighbours.
For each of those neighbours consider its neighbours etc. This resembles a breadth first search
(or rather a depth first search when programmed recursively).
Below is the algorithm in pseudo code where I have left out some details:

// Code for recursive algorithm
// v is a vertex, pathLength a nonnegative integer

function(v,pathLength):

  // stopping condition for recursive call
   if(pathLength==27 and v==endVertex):
      print path
   
  // recursive call continues
   else:
      for all neighbours w of v:
          if(neighbour w not yet visited):
                    function(w,pathLength+1)

You start with

// choose startVertex, e.g. startVertex=0
// set initialPathLength to 1 
// (path consists of startVertex at beginning) 

function(startVertex,1)

I first examined the 2x2 cube with 8 vertices. I labeled them with 0,1,2...,7 where the first plane is
0 1
2 3
and the second plane behind the first one is
4 5
6 7
(see also attachment)

This graph with 8 vertices can be implemented as an http://www.youtube.com/watch?v=2guA5uMEmZQ":
0: [1,2,4]
1: [0,3,5]
2: [0,3,6]
3: [1,2,7]
4: [0,5,6]
5: [1,4,7]
6: [2,4,7]
7: [3,5,6]

Example (to illustrate meaning):
0: [1,2,4] means the neigbours of vertex 0 are the vertices 1,2 and 4.


When I run the Python program the results for startVertex=0 and endVertex=7 are:
[0, 1, 3, 2, 6, 4, 5, 7] 1
[0, 1, 5, 4, 6, 2, 3, 7] 2
[0, 2, 3, 1, 5, 4, 6, 7] 3
[0, 2, 6, 4, 5, 1, 3, 7] 4
[0, 4, 5, 1, 3, 2, 6, 7] 5
[0, 4, 6, 2, 3, 1, 5, 7] 6

Example (to illustrate meaning):
[0, 1, 3, 2, 6, 4, 5, 7] 1
This means the path passes the vertices 0,1,3,2,6,4,5 and 7. The
number behind the square bracket is a just a counter for total number of paths.

This means there are 6 paths from the (front,top,left) corner to the (back,bottom,right) corner.
I have attached the actual code in python (cubePath2x2.py).


For the 3x3x3 cube my result is 18536 paths from the (front,top,left) corner to the (back,bottom,right) corner. I have attached the actual code in python (cubePath3x3.py).


Actual python code for the 2x2 case

# To start this program type the following in linux console:
# python cubePath2x2.py 


# This program computes all paths from a start vertex to 
# and end vertex in a 2x2 cube with 8 vertices
# (see: https://www.physicsforums.com/showthread.php?t=460112)

# The algorithm is recursive (heavily influenced by Haskell)
# It resembles a breadth first search



# v: vertex, whose neighbours are examined in the next step

# visited: A boolean array that tells if a vertex i has been visited, e.g. visited[i]=True means i 
# has been visited

# lengthPath: This must be specified by the user in the function definition. If you want 
#             to have all vertices exactly once in your path, set lengthPath to 
#             the number of vertices of your graph. Here, it is set to 8 (total number of vertices). 

# adjList: The graph written as an adjacency list

# path: saves the current path, e.g. [0,1] means the path consists of the vertices 0 and 1

# endVertex: this value must be specified by the user


def visitNeighbours(v,visited,lengthPath,adjList,path,endVertex,counter):
	if(lengthPath==8 and v==endVertex):
		counter[0] = counter[0]+1	# I only used a list here because I needed a global variable
		print path, counter[0]		# and lists are passed as "call by reference"
	else:
		for i in adjList[v]:
			if(visited[i]==False):
				visitedCopy = visited[:]   # [:] is the slicing operator for a copy 
				visitedCopy[i]=True
				pathCopy = path[:]
				pathCopy.append(i)
				visitNeighbours(i,visitedCopy,lengthPath+1,adjList,pathCopy,endVertex,counter)
				

def main():

	# define your graph
	adjList = [ [1,2,4], [0,3,5], [0,3,6], [1,2,7], [0,5,6], [1,4,7], [2,4,7], [3,5,6] ]
	
	
	visited = []
	for i in range(0,8):
		visited.append(False)
	
	# ----this part is for the user----
	startVertex = 0
	endVertex = 7
	#----------------------------------
	
	path=[startVertex]
	visited[startVertex]=True
	counter = [0]
	lengthPath = 1
	
	
	visitNeighbours(startVertex,visited,lengthPath,adjList,path,endVertex,counter)
	
	
	
# execute main()
main()

 

[trini]

very nice edgardo ^_^, i don't have python but i had a feeling a dedicated counting system would have done this faster, which it seems to have done. my MATLAB code is STILL running, maybe because of the way it has to do long searches and matrix edits(very inefficient for this) I've waited so long for this i may as well let it run and finish so i can verify your results, thanks for the effort!(how long did your code take to run btw)

imo it is an interesting problem to consider, have you tried using different start and end vertices? in particular i am interested in the following 3 situations(all start at the same corner vertex, A)[i will use my diagram's labeling to illustrate the idea since it is the 3x3 case i am interested in]

-last vertex(AA)[opposite corner vertices, this is the one you did already and i am running]

-last vertex(U)[opposite diagonal vertices]

-last vertex(J)[opposite edge vertices]i wanted to know these more than any other because of its symmetry with the options available in the 2x2 case(in your illustration , for eg, starting at 0 and then ending at 7,3, and 1 respectively.these are the 3 path 'classes' of the 2x2, so i wanted to use this as my base of comparison with n x n systems).

of course in a 3x3 more options are available, such as ending on an edge or face etc, but i look at opp corner, opp diag, and opp edge as the three major classes, if u understand me.

if your program isn't very expensive, could you test the remaining 2 cases for me(i don't think i'd ever finish xD)

 

[Edgardo]

I noticed that I forgot an edge in the 3x3x3 cube, namely the edge from vertex 21 to vertex 24.
The adjacency list for vertex 21 is not [12,18,22] but [12,18,22,24].
See the attachment for how I chose the labeling.
As a consequence there are now more paths than in my earlier post.

----

The correct results are now:

Paths from 0 to 26: 30880
(case: start vertex A, last vertex AA)

Paths from 0 to 2: 26892
(case: start vertex A, last vertex J)

Paths from 0 to 8: 28431
(case: start vertex A, last vertex U)

---

My program runs for 6 minutes and 50 seconds.
I've also attached the python programs. You can download python here:
http://www.python.org/download/
Maybe you could test it (or someone else) and tell me what time you've got since my notebook is a
little slow.

http://www.youtube.com/watch?v=4Mf0h3HphEA"
Here is a tutorial on how to run a python script in Windows:
http://www.annedawson.net/Python_Editor_IDLE.htm" by Anne Dawson PhD
----

I agree, this is indeed an interesting problem. In which context did you find this problem?

 

[trini]

i ran the program, it seems you forgot another vertex as well(i already appended my main file so i can't remember which now, but it's one of your arrays with 3 vertices, as the initial file posted had 10 arrays with 3 vertices(implying 10 corners). After updating i found:

0-->26 = 38,256 = 6376 x 6
0-->2 = 31,164 = 5194 x 6
0-->8 = 36,372 = 6062 x 6

all have 6 as their only common factor(other than 1 and 2 of course), which is good because it further supports my idea that the 2x2x2 is the basis of this type of system.

as for the context, it has to do with a statistical theory of heat transfer i am trying to develop.

 

[Edgardo]

Oops , you are right. I forgot the edge from vertex 7 to vertex 4.
The adjacency list of 7 is not [6,8,16] but [4,6,8,16].

Besides, the paths you are searching for are also known as Hamiltonian Paths (see this http://mathworld.wolfram.com/HamiltonianPath.html" ).

 

[trini]

hey Edgardo, i was trying to understand your code a little better to see if i could use any of those ideas in the MATLAB file(which I have saving ALL of the paths, including the ones that don't complete a hamiltonian path), but I'm not sure which part of your code tells the compiler not to use endVertex until the last turn, could you show me?(not familiar with python)

 

[Edgardo]

def visitNeighbours(v,visited,lengthPath,adjList,path,endVertex,counter):
	if(lengthPath==27 and v==endVertex):
		counter[0] = counter[0]+1   # I only used a list here because I needed a global variable
		print path, counter[0]      # and lists are passed as "call by reference"
	else:
		for i in adjList[v]:
			if(visited[i]==False):
				visitedCopy = visited[:]   # [:] is the slicing operator for a copy 
				visitedCopy[i]=True
				pathCopy = path[:]
				pathCopy.append(i)
				visitNeighbours(i,visitedCopy,lengthPath+1,adjList,pathCopy,endVertex,counter)

The recursive call stops if
lengthPath==27 and v==endVertex.

So, endVertex is visited (not only as last vertex) but only paths with
endVertex as last vertex are accepted.
I guess you could optimize the code further by only visiting endVertex as last vertex.

 

[trini]

ok i get it, makes sense.

now, I'm trying to modify this for a 4x4 cube, so i assigned the vertices to suit, and i changed the lengthPath to 64, and range to (0,64), but now when i run i get an indexing error, any clue as to why??

def visitNeighbours(v,visited,lengthPath,adjList,path,endVertex,counter):
	if(lengthPath==64 and v==endVertex):
		counter[0] = counter[0]+1   # I only used a list here because I needed a global variable
		print path, counter[0]      # and lists are passed as "call by reference"
	else: 
		for i in adjList[v]:
			if(visited[i]==False):
				visitedCopy = visited[:]   # [:] is the slicing operator for a copy 
				visitedCopy[i]=True
				pathCopy = path[:]
				pathCopy.append(i)
				visitNeighbours(i,visitedCopy,lengthPath+1,adjList,pathCopy,endVertex,counter)
				

def main():

	# define your graph
	adjList = [ 
	            [1,16,4],        [0,2,5,17],         [1,3,6,18],         [2,7,19], 
	            [0,5,20,8],      [1,4,9,6,21],       [2,5,7,10,22],      [3,6,11,23],
	            [4,9,12,24],     [5,8,10,13,25],     [6,9,14,11,26],     [7,10,15,27],
	            [8,13,28],       [9,12,14,29],       [10,13,15,30],      [11,14,31],
	            [0,32,17,20],    [1,16,18,21,33],    [2,17,19,22,34],    [3,18,23,35],
	            [4,16,21,24,36], [5,17,20,22,25,37], [6,18,21,23,26,38], [7,19,22,27,39],
	            [8,20,25,28,40], [9,21,24,26,29,41], [10,22,25,27,30,42],[11,23,26,31,43],
	            [12,24,29,44],   [13,25,28,30,45],   [14,26,29,31,46],   [15,27,30,47],
	            [16,33,36,48],   [17,32,34,37,49],   [18,33,35,38,40],   [19,34,39,51],
	            [20,32,37,40,52],[21,33,36,38,41,53],[22,34,37,39,42,54],[23,35,38,43,55],
                    [24,36,41,44,56],[25,37,40,42,45,57],[26,38,41,43,46,58],[27,39,42,47,59],
                    [28,40,45,60],   [29,41,44,46,61],   [30,42,45,47,62],   [31,43,46,63],
                    [32,49,52],      [33,48,50,53],      [34,49,51,54],      [50,35,55],
                    [36,48,53,56],   [37,49,52,54,57],   [38,50,53,55,58],   [39,51,54,59],
                    [40,52,57,60],   [41,53,56,58,61],   [42,54,57,59,62],   [43,55,58,63],
                    [44,56,61],      [45,57,60,62],      [46,68,61,63],      [47,59,62]
                  ]
	
	
	visited = []
	for i in range(0,64):
		visited.append(False)
	
        # ----this part is for the user----	
	startVertex = 0
	endVertex = 63
	#----------------------------------
	
	path=[startVertex]
	visited[startVertex]=True
	counter = [0]
	lengthPath = 1
	
	
	visitNeighbours(startVertex,visited,lengthPath,adjList,path,endVertex,counter)
	
	
	

# execute main()
main()

 

[Edgardo]

The second last adjacency list [46,68,61,63] has a wrong label. There is no vertex 68.

 

[Edgardo]

I was able to reduce the run time further upon your suggestion of not following the branch at endVertex if it is not the last vertex in the path. In the code below I added the part highlighed blue.
The run time is now not 9 minutes but 3 minutes.

def visitNeighbours(v,visited,lengthPath,adjList,path,endVertex,counter):
	if(lengthPath==27 and v==endVertex):
		counter[0] = counter[0]+1   # I only used a list here because I needed a global variable
		print path, counter[0]      # and lists are passed as "call by reference"
	else:
		for i in adjList[v]:
			if(visited[i]==False [B]and not(i==endVertex and lengthPath+1<27)[/B] ):
				visitedCopy = visited[:]   # [:] is the slicing operator for a copy 
				visitedCopy[i]=True
				pathCopy = path[:]
				pathCopy.append(i)
				visitNeighbours(i,visitedCopy,lengthPath+1,adjList,pathCopy,endVertex,counter)

 

[trini]

ah ok good stuff, I've been trying this code on the 4x4, its taken a day now and i haven't even worked out 0-->63, I'm on path 160000 right now, and it still hasn't begun to check past the 0,1... series. amazing to see how exponentially the system grows.

 

[Edgardo]

I translated the python program into C++ (using the STL).

I have attached two programs:
1) cube_PathsDisplayed.cpp has the same output as the python program,
i.e. it displays all Hamiltonian paths and numbers them.
Runtime for the 3x3x3 cube: 2 mins

2) cube_NoPathsDisplayed.cpp only displays the number
of Hamiltonian paths.
Runtime for the 3x3x3 cube: 43 seconds

Version 1

// This program calculates the number of Hamiltonian paths 
// in a 3x3x3 graph, see:
// https://www.physicsforums.com/showthread.php?t=460112

// Here, the Hamiltonian paths are displayed and numbered.


#include<iostream>
#include<vector>
using namespace std;


// This function is used to print the Hamiltonian path if one is found.
// The argument 'counter' is used to tell which path is found, e.g. the 732nd path is found.
void print(vector<int> path, int counter){
	vector<int>::iterator itr;
	itr = path.begin();
	
	cout << "[ ";
	while(itr<path.end()){
		cout << *itr << " ";
		itr++;
	}
	cout << "] ";
	cout << counter;
	cout << endl;
}



// This is the recursive function
void visitNeighbours(int v, vector<int> visited, int lengthPath, vector<int>* adjList, vector<int> path, int endVertex, int& counter){

	if(lengthPath==27 && v==endVertex){
		counter++;
		print(path, counter);
	}
	
	else{
		
		vector<int>::iterator itr;
		itr=adjList[v].begin();
		
		while(itr<adjList[v].end()){        // python: for i in list => C++: use iterator itr
			if(visited[*itr]==0 && !(*itr==endVertex && lengthPath+1<27) ){
				
			   vector<int> visitedCopy;
			   visitedCopy = visited;   // luckily this is not a "copy by reference"
			   visitedCopy[*itr]=1;
				
			   vector<int> pathCopy;
			   pathCopy = path;
			   pathCopy.push_back(*itr);
				
			   visitNeighbours(*itr,visitedCopy,lengthPath+1,adjList,pathCopy,endVertex,counter);
			}
		itr++;      // iterator moves
		}
	}
}  








int main(){

	// main program
	cout << "PROGRAM STARTS" << endl;


	vector<int> adjList[27];
	
	
	
	
	// begin: define your graph ---------------------------------------------------
	// node0
	int node0[] = {1,3,9};
	adjList[0].assign(node0,node0+3);  // the "+3" comes from the length of the array 'node0[]'
	
	// node1
	int node1[] = {0,2,4,10};
	adjList[1].assign(node1,node1+4);  // here "+4" since the array has 4 elements
	
	// node2
	int node2[] = {1,5,11};
	adjList[2].assign(node2,node2+3);  // here "+3" since the array has 3 elements
	
	//-----------------------------------------------------------------------------------------
	
	// node3
	int node3[] = {0,4,6,12};
	adjList[3].assign(node3,node3+4);
	
	// node4
	int node4[] = {1,3,5,7,13};
	adjList[4].assign(node4,node4+5);
	
	// node5
	int node5[] = {2,4,8,14};
	adjList[5].assign(node5,node5+4);
	
	//----------------------------------------------------------------------------------------
	
	// node6
	int node6[] = {3,7,15};
	adjList[6].assign(node6,node6+3);
	
	// node7
	int node7[] = {4,6,8,16};
	adjList[7].assign(node7,node7+4);
	
	// node8
	int node8[] = {5,7,17};
	adjList[8].assign(node8,node8+3);
	
	//---------------------------------------------------------------------------------------
	
	// node9
	int node9[] = {0,10,12,18};
	adjList[9].assign(node9,node9+4);
	
	// node10
	int node10[] = {1,9,11,13,19};
	adjList[10].assign(node10,node10+5);
	
	// node11
	int node11[] = {2,10,14,20};
	adjList[11].assign(node11,node11+4);
	
	//---------------------------------------------------------------------------------------
	
	// node12
	int node12[] = {3,9,13,15,21};
	adjList[12].assign(node12,node12+5);
	
	// node13
	int node13[] = {4,10,12,14,16,22};
	adjList[13].assign(node13,node13+6);
	
	// node14
	int node14[] = {5,11,13,17,23};
	adjList[14].assign(node14,node14+5);
	
	//---------------------------------------------------------------------------------------------
	
	// node15
	int node15[] = {6,12,16,24};
	adjList[15].assign(node15,node15+4);
	
	// node16
	int node16[] = {7,13,15,17,25};
	adjList[16].assign(node16,node16+5);
	
	// node17
	int node17[] = {8,14,16,26};
	adjList[17].assign(node17,node17+4);
	
	
	//---------------------------------------------------------------------------------------------
	
	// node18
	int node18[] = {9,19,21};
	adjList[18].assign(node18,node18+3);
	
	// node19
	int node19[] = {10,18,20,22};
	adjList[19].assign(node19,node19+4);
	
	// node20
	int node20[] = {11,19,23};
	adjList[20].assign(node20,node20+3);
	
	//---------------------------------------------------------------------------------------------
	
	// node21
	int node21[] = {12,18,22,24};
	adjList[21].assign(node21,node21+4);
	
	// node22
	int node22[] = {13,19,21,23,25};
	adjList[22].assign(node22,node22+5);
	
	// node23
	int node23[] = {14,20,22,26};
	adjList[23].assign(node23,node23+4);
	
	//---------------------------------------------------------------------------------------------
	
	// node24
	int node24[] = {15,21,25};
	adjList[24].assign(node24,node24+3);
	
	// node25
	int node25[] = {16,22,24,26};
	adjList[25].assign(node25,node25+4);
	
	// node26
	int node26[] = {17,23,25};
	adjList[26].assign(node26,node26+3);
	
	
	// end: define your graph  ---------------------------------------------------
	
	
	
	// This array tells us if a vertex has already been visited.
	vector<int> visited;
	for(int i=0; i<27; i++){
		visited.push_back(0);
	}
	
	// Start and end vertex
	int startVertex=0;
	int endVertex=26;
	
	// Initialize data structures
	vector<int> path;
	path.push_back(startVertex);
	visited[startVertex]=1;
	int counter = 0;
	int lengthPath = 1;
	
	visitNeighbours(startVertex,visited,lengthPath,adjList,path,endVertex,counter);
	
	cout << "Number of Hamiltonian paths: " << counter << endl;
	cout << "PROGRAM ENDS" << endl;
	
	
	return 0;
}



/*
[ 0 9 18 21 24 25 22 23 20 19 10 13 16 15 12 3 6 7 8 5 4 1 2 11 14 17 26 ] 38256
Number of Hamiltonian paths: 38256
PROGRAM ENDS

real	1m56.932s
user	1m55.651s
sys	0m0.716s
*/

Version 2

// This program calculates the number of Hamiltonian paths 
// in a 3x3x3 graph, see:
// https://www.physicsforums.com/showthread.php?t=460112

// Here, the Hamiltonian paths are not numbered to speed up the 
// calculation. 
  

#include<iostream>
#include<vector>
using namespace std;


// This is the recursive function
void visitNeighbours(int v, vector<int> visited, int lengthPath, vector<int>* adjList, int endVertex, int& counter){

	if(lengthPath==27 && v==endVertex){
		counter++;
	}
	
	else{
		
		vector<int>::iterator itr;
		itr=adjList[v].begin();
		
		while(itr<adjList[v].end()){        // python: for i in list => C++: use iterator itr
			if(visited[*itr]==0 && !(*itr==endVertex && lengthPath+1<27) ){
				
			   vector<int> visitedCopy;
			   visitedCopy = visited;   // luckily this is not a "copy by reference"
			   visitedCopy[*itr]=1;
				
			   	
			   visitNeighbours(*itr,visitedCopy,lengthPath+1,adjList,endVertex,counter);
			}
		itr++;      // iterator moves
		}
	}
}  














int main(){

	// main program
	cout << "PROGRAM STARTS" << endl;


	vector<int> adjList[27];
	
	
	
	
	// begin: define your graph ---------------------------------------------------
	// node0
	int node0[] = {1,3,9};
	adjList[0].assign(node0,node0+3);  // the "+3" comes from the length of the array 'node0[]'
	
	// node1
	int node1[] = {0,2,4,10};
	adjList[1].assign(node1,node1+4);  // here "+4" since the array has 4 elements
	
	// node2
	int node2[] = {1,5,11};
	adjList[2].assign(node2,node2+3);  // here "+3" since the array has 3 elements
	
	//-----------------------------------------------------------------------------------------
	
	// node3
	int node3[] = {0,4,6,12};
	adjList[3].assign(node3,node3+4);
	
	// node4
	int node4[] = {1,3,5,7,13};
	adjList[4].assign(node4,node4+5);
	
	// node5
	int node5[] = {2,4,8,14};
	adjList[5].assign(node5,node5+4);
	
	//----------------------------------------------------------------------------------------
	
	// node6
	int node6[] = {3,7,15};
	adjList[6].assign(node6,node6+3);
	
	// node7
	int node7[] = {4,6,8,16};
	adjList[7].assign(node7,node7+4);
	
	// node8
	int node8[] = {5,7,17};
	adjList[8].assign(node8,node8+3);
	
	//---------------------------------------------------------------------------------------
	
	// node9
	int node9[] = {0,10,12,18};
	adjList[9].assign(node9,node9+4);
	
	// node10
	int node10[] = {1,9,11,13,19};
	adjList[10].assign(node10,node10+5);
	
	// node11
	int node11[] = {2,10,14,20};
	adjList[11].assign(node11,node11+4);
	
	//---------------------------------------------------------------------------------------
	
	// node12
	int node12[] = {3,9,13,15,21};
	adjList[12].assign(node12,node12+5);
	
	// node13
	int node13[] = {4,10,12,14,16,22};
	adjList[13].assign(node13,node13+6);
	
	// node14
	int node14[] = {5,11,13,17,23};
	adjList[14].assign(node14,node14+5);
	
	//---------------------------------------------------------------------------------------------
	
	// node15
	int node15[] = {6,12,16,24};
	adjList[15].assign(node15,node15+4);
	
	// node16
	int node16[] = {7,13,15,17,25};
	adjList[16].assign(node16,node16+5);
	
	// node17
	int node17[] = {8,14,16,26};
	adjList[17].assign(node17,node17+4);
	
	
	//---------------------------------------------------------------------------------------------
	
	// node18
	int node18[] = {9,19,21};
	adjList[18].assign(node18,node18+3);
	
	// node19
	int node19[] = {10,18,20,22};
	adjList[19].assign(node19,node19+4);
	
	// node20
	int node20[] = {11,19,23};
	adjList[20].assign(node20,node20+3);
	
	//---------------------------------------------------------------------------------------------
	
	// node21
	int node21[] = {12,18,22,24};
	adjList[21].assign(node21,node21+4);
	
	// node22
	int node22[] = {13,19,21,23,25};
	adjList[22].assign(node22,node22+5);
	
	// node23
	int node23[] = {14,20,22,26};
	adjList[23].assign(node23,node23+4);
	
	//---------------------------------------------------------------------------------------------
	
	// node24
	int node24[] = {15,21,25};
	adjList[24].assign(node24,node24+3);
	
	// node25
	int node25[] = {16,22,24,26};
	adjList[25].assign(node25,node25+4);
	
	// node26
	int node26[] = {17,23,25};
	adjList[26].assign(node26,node26+3);
	
	
	// end: define your graph  ---------------------------------------------------
	
	
	
	// This array tells us if a vertex has already been visited.
	vector<int> visited;
	for(int i=0; i<27; i++){
		visited.push_back(0);
	}
	
	// Start and end vertex
	int startVertex=0;
	int endVertex=26;
	
	// Initialize data structures
	visited[startVertex]=1;
	int counter = 0;
	int lengthPath = 1;
	
	visitNeighbours(startVertex,visited,lengthPath,adjList,endVertex,counter);
	
	cout << "Number of Hamiltonian paths: " << counter << endl;
	cout << "PROGRAM ENDS" << endl;
	
	
	return 0;
}



/*
PROGRAM STARTS
Number of Hamiltonian paths: 38256
PROGRAM ENDS

real	0m42.929s
user	0m42.755s
sys	0m0.040s

*/

Did you finish the calculations on the 4x4x4 cube last time? If yes, how long did it take?

 

[Edgardo]

I discovered another way to speed up the calculation. Use the http://www.linuxjournal.com/article/7269" -O2.
Instead of just compiling the cpp file with

g++ myFile.cpp

use

g++ -O2 myFile.cpp

The runtimes are now:
1) cube_PathsDisplayed.cpp has the same output as the python program,
i.e. it displays all Hamiltonian paths and numbers them.
Runtime for the 3x3x3 cube: 50 seconds

2) cube_NoPathsDisplayed.cpp only displays the number
of Hamiltonian paths.
Runtime for the 3x3x3 cube: 14 seconds

 

[trini]

hey edgardo, great work with the new algorithms, I've been trying this on visual basic, but i don't know how to compile the file using the command. btw, after 3 days, i gave up on the 4x4...it barely scratched the first series...

 

[Edgardo]

hey edgardo, great work with the new algorithms, I've been trying this on visual basic, but i don't know how to compile the file using the command. btw, after 3 days, i gave up on the 4x4...it barely scratched the first series...

hey trini, I also tried to determine the number of Hamiltonian paths for the 4x4x4 yesterday (startVertex=0 and endVertex=63). But after 29 hours I stopped the program. At that time the counter showed 38,020,000 paths, i.e. more than 38 million paths.

Besides, I found an interesting thread on the xkcd forums. They mention this paper:
Exact enumeration of Hamiltonian circuits, walks, and chains in two and three dimensions, Jesper Lykke Jacobsen

In the paper Jacobsen determines C_1, the total number of Hamiltonian paths in a cube (not just from one corner to another). The numbers get pretty big.

In the xkcd thread they also mention a link to OEIS, unfortunately data is only available for the two-dimensional nxn grid.