Написание функции Python, которая находит гамильтонов путь в графе

Я пытался написать функцию, которая будет принимать положительное целое число n в качестве входных данных и размещать целые числа от 1 до n в таком порядке, чтобы сумма каждого соседнего числа была идеальным квадратом (если такой порядок существует). Я понял, что если я создам граф, где вершины — числа, и между двумя вершинами есть ребро, если их сумма — идеальный квадрат, то эта проблема эквивалентна попытке найти гамильтонов путь в графе. Итак, я пытаюсь написать функцию, которая найдет гамильтонов граф, если он существует, в заданном графе. Вот мой код:

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 — это словарь графа (граф переменных уже использовался, и я не умею называть переменные), где каждая вершина — это ключ, а значение каждого ключа — это список, содержащий другие вершины, соседние с ключевой вершиной. Например, когда на входе 15, это словарь:

{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]}

Старт — это начальная точка гамильтоновой траектории. (Я пытался написать эту функцию без начальной точки, чтобы сама функция пробовала каждую точку в качестве отправной точки, но это усложнилось. Сейчас я просто перебираю все вершины самостоятельно.)

Я знаю, что для числа 15 мне полагается дать следующий список:

[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8]

Однако вместо этого он дает мне этот список:

[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 1, 8, 15, 10, 6]

Размышляя о том, как работает функция, я понял, что как только она достигает 1, она сначала добавляет 8 в качестве следующего числа. Однако число 8 не имеет ребра между вершинами, отличными от 1. Честно говоря, я понятия не имею, что оно делает дальше. Я понял, что когда у него нет возможных кандидатов для попытки, ему нужно вернуться назад и вернуться к последней нормальной позиции. Я не знаю, как это реализовать.

Как я могу решить эту проблему? Кроме того, как я могу улучшить свой код?

Я новичок в Python, поэтому прошу прощения, если этот вопрос тривиален или мой код ужасен.

Изменить: я думаю, что исправил основную проблему, и теперь он возвращает правильный список. Вот новый код:

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

Я думаю, проблема была в том, что как только мы зашли в тупик, неправильный путь уже был добавлен в список path, поэтому в выводе предыдущего кода была цифра 8.

Теперь проблема в том, что функция возвращает None после возврата списка. Итак, вот результат, когда я запускаю эту функцию для числа 15, т.е. график представляет собой словарь, о котором я упоминал ранее:

[8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9]
None

Как я могу это исправить, чтобы он не возвращал None? Между прочим, я все еще должен попробовать каждый номер в качестве отправной точки. Вот что я делаю:

for number in range(1, 16):
    if hampath_finder(moves, number):
        print(hampath_finder(moves,number))

Другими словами, я должен попробовать каждое число как начало пути вручную. Как я могу настроить исходную функцию, чтобы она не требовала отправной точки и сама пробовала все возможные числа?

Кроме того, эта функция занимает много времени даже для небольших чисел. Как я могу сделать его более эффективным?

Изменить: я понимаю, что включение функции всей вместо только части пути Гамильтона более полезно, поскольку в противном случае некоторые переменные не определены.

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.")

Функция blueprint создает график, проверяя сумму всех возможных пар. Я уже объяснил hampath_finder. После этого я пробую каждое число как начало пути, используя цикл for.