The Sleigh Packing problem
Haskell, 312 318 chars

import Data.List
s(ξ:υ:_,λ:σ:η:_)(x:y:_,l:w:_)=(ξ+λ&lt;=x||ξ&gt;=x+l||υ+σ&lt;=y||υ&gt;=y+w)&amp;&amp;ξ+λ&lt;7&amp;&amp;υ+σ&lt;13&amp;&amp;η&lt;6
y p l=[(v,r):l|v&lt;-[[x,y,0]|x&lt;-[0..5],y&lt;-[0..11]],r&lt;-permutations p,all(s(v,r))l]
main=do
 n&lt;-readLn
 p&lt;-mapM(fmap(map read.words).const getLine)[1..n]
 putStr.r$foldr((=&lt;&lt;).y)[[([9,0],[0..])]]p
r[]="NO"
r _="YES"


For some reason that I don't fully understand at the moment, it doesn't finish your tests #9 and #16 in reasonable time. But you didn't say anything about performance, did you?



373 383 chars

This version runs much faster for the examples: it first checks if it's not impossible simply because the area is too small, and then it starts with the largest parcels rather then inserting them in the given order. Note that the area detection is not perfect: it doesn't consider rotations, so it may on some inputs give wrong results. But it does work with the test script.

import Data.List
s(ξ:υ:_,λ:σ:η:_)(x:y:_,l:w:_)=(ξ+λ&lt;=x||ξ&gt;=x+l||υ+σ&lt;=y||υ&gt;=y+w)&amp;&amp;ξ+λ&lt;7&amp;&amp;υ+σ&lt;13&amp;&amp;η&lt;6
y p l=[(v,r):l|v&lt;-[[x,y,0]|x&lt;-[0..5],y&lt;-[0..11]],r&lt;-permutations p,all(s(v,r))l]
π=product
main=do
 n&lt;-readLn
 p&lt;-mapM(fmap(map read.words).const getLine)[1..n]
 putStr$if sum(map(π.init)p)&gt;72||null(foldr((=&lt;&lt;).y)[[([9,0],[0..])]].sortBy((.π).compare.π)$p)then"NO"else"YES"