  We provide a simple algorithm for constructing Hamiltonian graph cycles
(visiting every vertex exactly once) on a set of arbitrarily large finite
subgraphs of aperiodic two-dimensional Ammann-Beenker (AB) tilings. Using this
result, and the discrete scale symmetry of AB tilings, we find exact solutions
to a range of other problems which lie in the complexity class NP-complete for
general graphs. These include the equal-weight traveling salesperson problem,
providing, for example, the most efficient route a scanning tunneling
microscope tip could take to image the atoms of physical quasicrystals with AB
symmetries; the longest path problem, whose solution demonstrates that
collections of flexible molecules of any length can adsorb onto AB quasicrystal
surfaces at density one, with possible applications to catalysis; and the
three-coloring problem, giving ground states for the $q$-state Potts model ($q
\ge 3$) of magnetic interactions defined on the planar dual to AB, which may
provide useful models for protein folding.
