Unless I'm overlooking something, it sounds like a job for backtracking.. Abigail-II recently posted a meditation on using the regex engine in Perl to solve backtracking problems (in his case, the N-queens problem).

Makeshifts last the longest.