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.

• Martin Ender: This sounds like a tough optimisation problem. I think it would have made a nice code challenge.
• Peter Taylor: I can't edit because there's a pending edit from a low-rep user, but Mississippi has two double-s.
• proud haskeller: What about case sensitivity?
• Martin Ender: @proudhaskeller I'm sure the input is case insensitive, because: 1) the input is just any printable ASCII 2) the OP didn't mention otherwise 3) The oklahoma example wouldn't be minimal if the input was case insensitive.
• Ypnypn: @MartinBüttner I think you meant case sensitive

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 ;)

• Calvin's Hobbies: Looks good now, just really slow :/
• Calvin's Hobbies: You can shorten it a bit by removing import sys and replacing sys.argv[1] with raw_input().
• Will: @Calvin'sHobbies thx again, neat tip :) To get an early out you can just change the elif to elif not c and (not A or len(b)<len(A[-1])): and it runs a lot faster
• FryAmTheEggman: if "Oklahoma!" is OK input, you could just use input() instead of raw_input().