Minimal Boggle-like Arrangements

Question

Consider how a word could be arranged on an arbitrarily large Boggle grid if the rule about not using the same letter cube more than once is ignored. Also assume that you have an unlimited number of letter cubes (with all letters present), and Qu is just Q.

The word MISSISSIPPI could be arranged using only 6 cubes. Here is one possible arrangement:

 S
MIS
 PP

Starting at the M we repeatedly take any step horizontally, vertically, or diagonally until the entire word is spelled out.

Surprisingly, a longer phrase like AMANAPLANACANALPANAMA also only needs 6 cubes:

MAN
PLC

However, the minimum number of cubes needed for longer, more complex strings is not always obvious.

Challenge

Write a program that takes in a string and arranges it in this Boggle-like fashion such that the minimum number of cubes are used. (The dimensions of the resulting grid and the number of empty cells are irrelevant.)

Assume you have have an unlimited number of cubes for each printable ASCII character except space (hex codes 21 to 7E), since it's used as an empty grid cell. Only printable ASCII strings (without spaces) will be input.

Input should be taken from stdin or the command line. Output should go to stdout (or closest alternative).

Leading or trailing newlines and spaces in the output are fine (but hopefully there aren't an inordinate amount).

The search space blows up exponentially as the string gets longer, but you are not required to attempt to make your algorithm efficient (though that would be nice :) ). This is code-golf, so the shortest solution in bytes wins.

Example

If the input were Oklahoma! (8 character minimum), these would all be valid outputs because the all have exactly 8 filled grid cells and they follow the (revised) Boggle reading pattern:

Oklaho
   !m

or

  !
Oamo
klh

or

   lkO   
  !amo              
    h    

etc.

Answer 1

Python 342 355 398

R=(-1,0,1)
A=[];b={}
def s(w,x,y):
 if w: # not at the end of the word yet?
  for I in R: # search adjacent squares
   for j in R:
    if I|j: # skip the square we are on
     i=I+x;j+=y;c=b.get((i,j)) # get square in board
     if c==w[0]:s(w[1:],i,j) # square is what we are looking for?
     elif not c:b[i,j]=w[0];s(w[1:],i,j);del b[i,j] # we can set square?
 else:A.append(dict(b)) # all solutions
s(raw_input(),9,9) # run the search
A=min(A,key=len) # A is now the shortest solution
C=sum(map(list,A),[]) # put all board coords together
C=range(min(C),max(C)+1) # find the board biggest square bound
for r in C:print"".join(A.get((c,r)," ") for c in C)

Indent at four spaces is actually a tab character.

AMANAPLANACANALPANAMA:

MC 
NA 
PL

MISSISSIPPI:

S  
SI 
PPM

Oklahoma!:

oh    
 ma   
 ! l  
    k 
     O

Llanfairpwllgwyngyll is lethal ;)