Code Golf: Scrabble-able

Question

Code Golf: Scrabble-able

Input: a list of words

Output: a legal arrangement for the words on a scrabble board (or false if impossible). Format of output is entirely up to you, as long as it is comprehensible. Bonus points for pretty printing. Scrabble board size is unbounded, no un-listed words should be found in solution.

Examples:

input: {"alice", "bob", "eve"}
output: false

input: {"alice", "eve", "victoria"}
output: a|l|i|c|e
                v|i|c|t|o|r|i|a
                e

Usual code golf conditions apply. Have fun :)

---

Answer 1

Rebmu: 443 chars

(Note: Originally this was tagged with "fun". I deleted that tag, since 4 months of no one else answering plus my own experience in coding up a solution to this supports the idea that it's actually not so fun. :P)

Ssp Nl?A L0feZa[LmxLl?Z]Vad2mpBKlADeOD?n1[0]dvN2 Mai^Vsi^Vs Ga~[ZcydM MaZ]Fa|[ZpcMscA XfsA ZigX0[iZ[skZbkX]] iZ[iT?z[Zno]]eZz{ }]Tc|[Xno Q~[Z1br]ieSfsFsbBc[wh[Zf+A][JfB KfsJeeSk[OrvCYcEEsFSfADbO[eeSfsFadBngO[chJz]q]q][X1ineKzQ]BadBc]ieSfsFb[anY?xN?z]]]Ra|[Q~[iUbr]eT?aON[ZntSBvL rtXz[rtYz[O[0 1]lo2[JgM UeTfsAre[xY]o[rNTa][eH?a[rNTa]no]eU0[gJ]rvOq]q]q]u]]wErA[JmWH[Kf+J][iM?trtK[JbkJtkJ]]feZm[Kf+Zwh[Jf+Z][ZntISbkZegKs[egJs{|}s]s Kj]]m]{false}

This is a fairly straightforward implementation of a brute force solver. I'd go for length optimization if there was any competition, but lacking any I'll just show how "naive" Rebmu programming is naturally quite brief, despite the lack of native matrix operations (yet). You'll find the commented source here:

http://github.com/hostilefork/rebmu/blob/master/examples/scrabbleable.r

As with problems of this nature, some are going to find solutions right away whereas others it will take a long time to exhaust the search space in a way that "proves" no solution is possible. For example, this was fast:

>> rebmu/args %scrabbleable.r ["mysterious" "rebmu" "scrabble" "solver"]
m
y
s|c|r|a|b|b|l|e
t
e
r|e|b|m|u
i
o
u
s|o|l|v|e|r

OTOH, this one took a couple minutes as it went through and exhausted the space:

>> rebmu/args %scrabbleable.r ["some" "examples" "do" "not" "work"]      
false

In the code, N is the number of input strings, L is the length of the longest string, and V is the upper bound on the edge size of a "board" for a legal solution. I could have been lazy and just said VmpNl (which equates to v: mp n l, where mp is multiply). But instead I went with the math to get a better upper bound Vad2mpBKlADeOD?n1[0]dvN2 since I didn't want it to take absolutely forever to run on small examples. :)

But it would save 20 characters at a huge cost to performance; I think this presents a good example of why such problems aren't really suited to code golf.