Perl, 170 194

A perfect task for a language created by Larry Wall.

#!perl -pa $_=(1x($x=2/($y=pop@F)*map{1..$_}@F)." ")x$y;sub f{my$l=$_;$-|=!@_;for$=(@_){$Z=_ x~-$=;$f=0;s/1{$=}1{$=}/[$Z$Z]/&!/\]..{$x}\[/s&&f(grep$=ne$_||$f++,@_);$-or$_=$l;}}f@F 

Brute force, but quite fast on the test cases (<1s). Usage:

$ perl ~/wall.pl <<<"1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 5" [][__][__] [__][__][] [][__][__] [__][__][] [][__][__] 

Test me.