Finding a hamiltonianISH path in a graph

Problem statement

Given a graph of all the blue squares in the following image where each blue square is connected to other blue squares in all 4 cardinal directions.

Given any starting node.

What algorithm will allow for finding the longest(ish) path.

Considering that each node can only be visited once.

Considering that we don't care where the path ends.

Considering that speed is more important than necessarily visiting each node.

Example

I have traced an example of the desired result in the image below. As you can see, the path does not visit each node and that is fine. I'm looking for a fast algorithm that will give me one of the longest possible path on this graph. 80% coverage or more is what I'm shooting for.

This is the longest path problem. It's NP-hard to find the longest path in a general graph. You can try applying any standard algorithm for finding longest paths. Search on this site for "longest path" and "Hamiltonian path" to find many references. Since you're willing to accept suboptimal solutions, you might look for a heuristic or approximation algorithm (e.g., using a local search algorithm).

StackExchange Computer Science Q#122087, answer score: 2