I was trying to write a function that will take a positive integer n as an input and will put the integers 1 through n in an order such that the sum of every adjacent number is a perfect square (if such an order exists). I realized that if I create a graph where vertices are the numbers, and there is an edge between two vertices if their sum is a perfect square, then this problem is equivalent to trying to find a Hamiltonian path in a graph. So, I am trying to write a function that will find a Hamiltonian graph, if it exists, in a given graph. Here's my code:
def hampath_finder(moves, start, path=None):
if path is None:
path = []
if len(path) == bound:
return path
if not path:
path = path + [start]
for candidate in moves[start]:
if candidate not in path:
path = path + [candidate]
new_path = hampath_finder(moves, candidate, path)
if new_path:
return new_path
else:
continue
else:
return None
return None
"Moves" is a dictionary of the graph (the variable "graph" was already used, and I am not good at naming variables), where every vertex is a key and the value of every key is a list containing other vertices adjacent to the key vertex. For example, when the input is 15, this is the dictionary:
{1: [3, 8, 15], 2: [7, 14], 3: [1, 6, 13], 4: [5, 12], 5: [4, 11], 6: [3, 10], 7: [2, 9], 8: [1], 9: [7], 10: [6, 15], 11: [5, 14], 12: [4, 13], 13: [3, 12], 14: [2, 11], 15: [1, 10]}
Start is the starting point of the Hamiltonian path. (I've tried to write this function without a starting point such that the function itself tries every point as a starting point, but it got complicated. For now, I just iterate through all the vertices by myself.)
I know that for the number 15, it is supposed to give me the following list:
[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8]
However, it gives me this list instead:
[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 1, 8, 15, 10, 6]
Thinking about how the function operates, I realized that once it gets to 1, it first adds 8 as the next number. However, 8 has no edge between a vertex other than 1. Honestly, I have no idea what it does next. I realized that once it has no possible candidates to try, it needs to backtrack and go back to the last normal position. I don't know how to implement this.
How could I fix this issue? Also, how can I improve my code?
I am quite new to Python, so I apologize if this question is trivial or my code is terrible.
Edit: I think I fixed the main problem, and it now returns the correct list. Here's the new code:
def hampath_finder(moves, start, path=None):
if path is None:
path = []
if len(path) == bound:
return path
if not path:
path = path + [start]
for candidate in moves[start]:
if candidate not in path:
new_path = hampath_finder(moves, candidate, path + [candidate])
if new_path:
return new_path
I think the problem was that once we got to a dead-end, the incorrect path had already been appended to the list path, which is why there was an 8 in the output of the previous code.
Now, the problem is that the function returns None after returning the list. So, here's the output when I run this function for the number 15 i.e. the graph is the dictionary that I mentioned previously:
[8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9]
None
How can I fix this so it doesn't return None? By the way, I still have to try every number as a starting point myself. Here's what I do:
for number in range(1, 16):
if hampath_finder(moves, number):
print(hampath_finder(moves,number))
In other words, I have to try every number as the start of the path manually. How can I adjust the original function so it doesn't require a starting point, and tries all possible numbers itself?
Also, this function takes a long time even for small numbers. How can I make it more efficient?
Edit: I realize that including the entire function instead of only the Hamiltonian path part is more helpful since some variables are otherwise undefined.
from math import sqrt
def adjacent_square(bound):
def blueprint(bound):
graph = {}
for number in range(1, bound + 1):
pos_neighbours = []
for candidate in range(1, bound + 1):
if sqrt(number + candidate) == int(sqrt(number + candidate)) and number != candidate:
pos_neighbours.append(candidate)
graph[number] = pos_neighbours
return graph
graph = blueprint(bound)
def hampath_finder(mapping, start, path=None):
if path is None:
path = []
if len(path) == bound:
return path
if not path:
path = path + [start]
for candidate in mapping[start]:
if candidate not in path:
new_path = hampath_finder(mapping, candidate, path + [candidate])
if new_path:
return new_path
for num in range(1, bound+1):
if hampath_finder(graph, num):
print(hampath_finder(graph, num))
break
else:
print("No such order exists.")
The function blueprint creates the graph by checking the sum of every possible pair. I've already explained hampath_finder. Afterwards, I try every number as the start of a path using a for loop.
I think the reason you are getting None is because in the hampath_finder function you are only returning a value if new_path:. If there is not a new path and the function returns, then Python will return None. You can see that with this example:
def testfunct(test):
if test:
return True
print(testfunct(False))
>>> None
Additionally, you are computing the hampath_finder twice. Once to see if it exists, then again to print it. I would change this section of your code:
for num in range(1, bound+1):
if hampath_finder(graph, num):
print(hampath_finder(graph, num))
break
To be something more like this:
for num in range(1, bound+1):
this_path = hampath_finder(graph, num)
if len(this_path) > 0:
print(this_path)
break
This will help with the speed a small amount.
However, a cursory look at the Hamiltonian Path Problem looks like it is an NP-Complete problem. So it is going to be very slow. There are some research papers that have faster implementations that are out of the scope of StackOverflow. Also, if speed is necessary, then you will probably want to switch the implementation to something like C or C++.