  Given $N$ cities and $R < N^2 - N$ directed (unidirectional/one way) roads
does there exist a tour of all $N$ cities stopping at each city exactly once
using the given roads (a Hamiltonian cycle)? This Hamiltonian cycle problem
(HCP) is an NP-complete problem, for which there is no known polynomial time
solution algorithm. The HCP has important practical applications, for example,
to logistical problems. It was claimed that an adiabatic quantum computer could
solve an NP-complete problem faster than classical algorithms, but claim
appears to have been debunked. Here we demonstrate an algorithm which runs on a
standard computer that efficiently and effectively solves the HCP for at least
up to 500 cities: We first optimized a simulated annealing based algorithm used
for smaller sized HCP problems. Then we found that when a tour was deliberately
inserted in a list of otherwise randomly chosen roads, crucially, if "extra"
random roads are added to bring the total number of roads up to $0.58 N log_e
N$ or more there is a 100% chance our algorithm will find a HC, but conversely
when a list of roads does not include a pre-inserted tour random roads have to
be added until there are $0.9 N log_e N$ roads to have a chance of finding a
HC. We found similarly for a set of roads non-randomly chosen. Thus, the
presence of a HC in a set of roads induces "connectivity" throughout the roads
and a HC can be found with an insertion of a modest number of extra roads. Our
algorithm also shows that only weakly non-local information is needed to find
an HCP that is a global state.
