Алгоритмы для нахождения числа гамильтоновых путей в графе

Я пытаюсь решить слегка измененную версию задачи Hamiltonian Path . . Он изменен тем, что нам даются начальная и конечная точки, и вместо определения того, существует ли решение, мы хотим найти число решений (которое может быть 0).

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

Я написал решение методом грубой силы, которое пробует все 4 (3 или 2 для узлов на краях) возможных ходов в каждом узле, а затем подсчитывает количество решений (когда оно достигает цели и просматривает все остальные узлы). ), но он работал смешно долго на входах скромного размера (например, массив 7x7).

Я также подумал об использовании двунаправленного поиска , поскольку мы знаем цель, но это не очень помогло, поскольку мы не просто хотим, чтобы границы совпадали, мы также хотим убедиться, что все узлы были посещены. Более того, может случиться так, что когда все узлы между двумя границами исчерпаны, они заканчиваются так, что их нельзя соединить.

Я чувствую, что есть что-то, чего я не знаю, что оставляет мне только решение грубой силы. Я знаю, что проблема сама по себе NP-полная, но мне интересно, есть ли какие-либо улучшения по сравнению с грубой силой. Может ли кто-нибудь предложить что-нибудь еще?

- Изменить -

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