<p>Knuth wrote a paper called "Dancing Links" e.g. at <a href="http://arxiv.org/pdf/cs.DS/0011047" rel="nofollow">http://arxiv.org/pdf/cs.DS/0011047</a> on a streamlined version of backtracking search. He uses it to e.g. tile a plane with polyonimoes. My guess is that this could be used to solve your problem - at some expense. I suspect that if a really general method existed to solve your problem, it could also be applied to Knuth's, which makes it unlikely that one will be found. Of course, your shapes are simpler than Knuth's, so perhaps there is some method particular to your problem which is more efficient.</p>
Algorithm to fill non-rectangular 2D tile-space with smaller 2D tile-based shapes
<p>I am trying to figure out how I would go about writing algorithm (in C#) that, when given:</p>

<ul>
<li><p>A set of generally small tile-based shapes. Often 2x2, but not always. Sometimes the shapes will be 2x1 or non-rectangular.</p></li>
<li><p>A tilemap (two-dimensional array) in which certain tiles are marked "free" and certain tiles are "reserved". The free tiles designate the area where the tile-based shapes are allowed to go, the reserved tiles cannot be occupied by the shapes.</p></li>
</ul>

<p>Example of a tile-based shape, other than 2x2s:
<a href="http://img850.imageshack.us/img850/9057/awk.png" rel="nofollow">http://img850.imageshack.us/img850/9057/awk.png</a></p>

<p>An example of "available space" in a tilemap:
<a href="http://img641.imageshack.us/img641/8263/spaceh.png" rel="nofollow">http://img641.imageshack.us/img641/8263/spaceh.png</a></p>

<ul>
<li>The white in this image designates the space to be filled, but I want the algorithm to be able to work just as well if the gray were the space to be filled and the whites were reserved.</li>
</ul>

<p>Basically, the algorithm should place the shapes in the available space, biased towards the top. The solution it comes up with does not have to be 'perfect', but it should <em>always</em> be able to find a solution if one exists. Also I would really like to avoid using any pseudo-random numbers in this algorithm. I want it to always find the same solution given the same input, even if that solution isn't the best one.</p>

<p>I have found other topics relating to this, but all of them had to do with filling a rectangular space rather than an arbitrary space.</p>

<p>EDIT: oh, and the shapes CAN be flipped both horizontally and/or vertically, but not rotated. Forgot to mention this.</p>

<p>EDIT2: let me clarify. I don't want the space to be filled, I want to determine where the shapes should go given a finite number of them. They should default towards the top.</p>