  Self-avoiding walks (SAWs) were introduced in chemistry to model the
real-life behavior of chain-like entities such as solvents and polymers, whose
physical volume prohibits multiple occupation of the same spatial point. In
mathematics, a SAW lives in the n-dimensional lattices.
  In this paper, SAWs are a metaphor for walks across faces of n-dimensional
dice, or more formally, a hyperhedron family H(Theta, b, n). Each face is
assigned a label {x:Theta(x)}; x represents a unique n-dimensional coordinate
string, Theta(x) is the value of the function. The walk searches Theta(x) for
optima by following five simple rules: (1) select a random coordinate and mark
it as the `initial pivot'; (2) probe all unmarked adjacent coordinates, then
select and mark the coordinate with the 'best value' as the new pivot; (3)
continue the walk until either the 'best value' <= `target value' or the walk
is being blocked by adjacent coordinates that are already pivots; (4) if the
walk is blocked, restart the walk from a randomly selected `new initial pivot';
(5) if needed, manage the memory overflow with a streaming-like buffer of
appropriate size.
  Hard instances from a number of problem domains, including the 2D protein
folding problem, with up to (2^{25})*(3^{24}) coordinates, have been solved
with SAWs in less than 1,000,000 steps -- while also exceeding the quality of
best known solutions to date.
