Here is my situation. I have a grid-type graph with obstacles. Every move (horizontally, vertically or diagonally with a range of 1) has a cost of exactly 1 (the graph is not weighted) provided that neither the source or the destination is an obstacle.
I need to, provided a starting node (a square), find any path that visits every single node that is reachable, without visiting any node twice. If there is no such path, then any path that would visit as many nodes as possible. In other words, I'm looking for an algorithm to find a Hamiltonian path in such a graph.
I am not looking for the shortest path.
The most important factor is the time the algorithm takes to complete (complexity).
I have searched Google and this site, and I only find variants of the travelling salesman, or algorithms for shortest path visiting all nodes, which won't work in my situation. My algorithm needs to find a path of any length visiting as many nodes as possible while never visiting a node twice. The path can end anywhere.
Does anyone have any tips? I've tried to do this with a variant of A*, but I couldn't make it work. I've succesfully done it by brute-forcing, but as the graph can be rather large, I need something a faster than O(n!).
It would be even better if the algorithm was non-deterministic, which means that if there are multiple possible solutions, we wouldn't always get the same one with the same graph and starting location. I have no idea how to do this without slowing it down though, and speed is more important.