I think this is a fun idea and i will try that some time, should be possible. Of couse you never know if there is a posibility for the given words in the given size, but if you try tons of combinations with an algorithm i think that should get some "acceptable" results.
I'd just start with the first word put it on the map, and then you try all other words left in all positions. And so on. So you get really a damn lot of combinations, which you could delete if they break you wanted size, and in the end you might have a nice list of possibilites and show like the 10 smallest of that to choose from. My GF is away this weekend, maybe ill have a try. I think recursive could be the right way to do that.