An incremental approximate algorithm 

	int lookahead
	int step <= lookahead
	while there are acids to place
	   explore all positions for the next lookahead acids
	      that minimize the energy of configuration so far
	   place the first step of those lookahead acids
The algorithm decides between ties by choosing to progress in a straight line, insofar as possible. Thus if the sequence is ...-A-B-C-... and B has been placed to the East of A then the algorithm will try to place C in direction E, NE, SE, NW or SW in that preference order on the hexagonal grid. Of course C can't be West of B since A is already there.

When lookahead = step = 1 this is a straightforward greedy algorithm. When step is greater than the length of the chain this is the brute force algorithm.

The time complexity of this algorithm is big-O of 

	 n * (nbrs-1)lookahead
	----------------------
	         step
where n is the length of the chain and nbrs is the number of neighbors of a cell on the grid. For the hex, square, cubic and dodecahedral grids that number is 6, 4, 6, 12. The good news is that for fixed step and lookahead this is linear in n . The bad news is that the constant is exponential in lookahead and can be quite large. The actual exponent for the hexagonal grid seems to be about 4.4, which is less than the bound of 6-1 = 5 but not sufficiently less to make much practical difference.

(Truth in advertising. There's really a quadratic term too, but the constant there is negligible. And I could probably rewrite that part of the code to make it linear, but it's not worth the effort.)

You might try the incremental algorithm on a random chain of length 50, seed 7676, with lookahead 6 and step 3 and then again with lookahead 8 and step 4 (it takes a fair bit longer). Don't even think about folding this one with brute force.

The larger the value of lookahead the more global information about the chain can contribute to the final folded shape.

There are biological arguments for and against the appropriateness of the incremental algorithm. Some proteins do seem to fold while they are being constructed. Others can refold themselves into their proper shape even after being completely denatured - that is, straightened out.