What dice do I need to display my words?

Question

A sequel to What dice do I need to display every integer up to X?

Numbers are great, but let's take it to the next level. I'd like to have a set of dice that can be arranged and rotated to display any words I want. Think Boggle:

And not just that; I want to specify the number of sides those dice have. The set should contain the fewest number of dice possible.

For example—
If I want to be able to display any of the following words with 4-sided dice:

CODE
GOLF
IS
VERY
FUN

I would need 4 dice with the following letters on their sides (each line represents a die):

C G I V
O S R U
D L N Y
E F

Note that the last die only has letters on two of its sides.

The challenge:

• Given a number of sides N, and 1 or more words, write a program that outputs the N-sided dice that are required to be able to display all of the words (one at a time).
• The first input is always an integer, 4 at minimum. This number determines the number of sides that each of the dice will have.
• All other inputs are strings of English-alphabet capital letters, at least 1 character in length. They may be provided in any format you like; delimited, a list, array, etc.
• Each side of a die must be either blank or contain a single English-alphabet capital letter.
• Unlike the number challenge, you do not need to ensure that every die is used for every word. If there's a two-letter word and 4 total dice required, you only need to ensure that 2 dice have the correct letters on them.
• Output must be provided so that all the letters on each die is shown, and each die is separated somehow. So CGIVOSRUDLNYEF is not valid output for the above example, but these are valid:

CGIV OSRU DLNY EF

CGIV
OSRU
DLNY
EF

["CGIV", "OSRU", "DLNY", "EF"]

[["C", "G", "I", "V"], ["O", "S", "R", "U"], ["D", "L", "N", "Y"], ["E", "F"]]

• The dice in the output, and the letters in each side do not need to be in any particular order.
• A correct solution outputs the fewest possible dice given the inputs.
• There may be multiple correct outputs for a given input. You need only output one.

Here are a couple more test cases:

Input: 4,EASY,TEST,TEASE
Output:
E
A T
S
Y T
E

Input: 5,MEDIC,FROG,WOW,ZEBRA,SCENES,ZOOM,BABOON,LOITER,XRAY,MEDIUM,GUEST,SUNDAY,ROMP
Output:
M S B L G
Z A F W E
D E B T M
M Y S O R
I N W X P
U C O A Y

Bonus challenges:

• Your program must also handle the number of sides being 3, 2, or 1.
• Your program must assume that an M can be rotated and used as a W. W can never appear in the output. This also goes for C and U, Z and N, H and I.
• A correct solution outputs the fewest possible letters for a given input, not just the fewest dice.

Answer 1

Python 3, 205 bytes

from itertools import*
def f(n,w,k=1):
 for s in product(*[[*product(*[{*''.join(w)}]*n)]]*k):
  if all(any(all(W.count(c)<=F.count(c)for c in W)for F in product(*s))for W in w):return s
 return f(n,w,k+1)

A recursive function that accepts a positive integer, n, and a list of strings w and returns a tuple (collection) of tuples (dice) of characters (faces).

Try it online! (adding 'FFF' requires four dice)

It's too slow for the test cases as it is checking all possibilities (hence the inputs given in the TIO links, with n=3 and a very small set of letters). We could prune the dice being considered by only using those with min(n, number of unique letters in inputted words) unique faces, which most of the time would mean we only consider those with n different faces, and we could start our considerations with min(word length) dice, but doing both still won't be enough to complete the given test cases on TIO.

Answer 2

Python3, 1070 bytes:

from itertools import*
P=permutations
def U(w,c):c=[i for i in c if i];t=[''.join(j)for i in P(c,len(c))for j in product(*i)];return[i for i in w if all(i not in j for j in t)]
E=enumerate
def f(w,n):
 C=-1;G=eval(str(w))
 while 1:
  C+=1
  q,S=[(G[:i]+G[i+1:],[[j]for j in a]+[[]for _ in range(len(max(G,key=len))-len(a))]+[[]for _ in range(C)])for i,a in E(G[:1])],[]
  while q:
   a,b=q.pop(0)
   if not a:return b
   F=0
   for m in sorted([K for i in P([*E(b)],len(a[0]))if(K:=[(u,I)for(u,x),(I,y)in zip(E(a[0]),i)if x in y])],key=len)[::-1]:
    I={i for i,_ in E(b)}-{i for _,i in m};w={i for i,_ in E(a[0])}-{u for u,_ in m};W=0
    for i in P(I,len(w)):
     B=eval(str(b));T=1
     for x,y in zip(i,w):
      if len(B[x])<n:B[x]+=[a[0][y]]
      else:T=0;break
     if T and B not in S:q+=[(U(a,B),B)];S+=[B];W=1
     else:W=max(W,0)
    if W:F=1
    else:F=max(F,0)
   if F==0:
    for i in P(E(b),len(a[0])):
     B=eval(str(b));T=1
     for(x,_),y in zip(i,a[0]):
      if len(B[x])<n:B[x]+=[y]
      else:T=0
     if T and B not in S:q+=[(U(a,B),B)];S+=[B]

Try it online!

Answer 3

Charcoal, 133 bytes

ＮθＷＳ⊞υι≔⟦⊞ＯＥ⌈⊞ＯＥυＬιＬ⪪⪫υωθωυ⟧υ≔⟦⟧ηＦυ«≔⊟ιζ≔§ζ⁰εＦΦＥＸＬιＬε﹪÷κＸＬιＥενＬι⬤κ⁼¹№κμ«≔Ｅι⁺λ…§ε⌕κμ›№κμ№λ§ε⌕κμκ¿⬤꬛Ｌλθ¿⊖Ｌζ⊞υ⊞ＯκΦζμ⊞ηΦκλ»»⊟Φη⁼Ｌι⌊ＥηＬλ

Try it online! Link is to verbose version of code. Takes input as an integer and a list of newline-terminated strings. Explanation: Brute force, so incredibly slow; link only has two words because that's all it can solve in a reasonable amount of time.

ＮθＷＳ⊞υι

Input N and the words.

≔⟦⊞ＯＥ⌈⊞ＯＥυＬιＬ⪪⪫υωθωυ⟧υ

Start off with a number of blank dice equal to the minimum of the length of the longest word or the minimum number of dice needed to write each letter of each word on its own face, and all of the words needing to be placed.

≔⟦⟧η

Start collecting possible placements.

Ｆυ«

Process all of the partial placements.

≔⊟ιζ

Get the remaining words.

≔§ζ⁰ε

Get the first word.

ＦΦＥＸＬιＬε﹪÷κＸＬιＥενＬι⬤κ⁼¹№κμ«

Get all of the permutations (even on the first iteration where it makes no difference whatsoever) of placing the letters of the word onto the dice.

≔Ｅι⁺λ…§ε⌕κμ›№κμ№λ§ε⌕κμκ

Get the result of this letter placement.

¿⬤꬛Ｌλθ

Check that there aren't too many letters on any of the dice.

¿⊖Ｌζ

If there are more words left to place, then...

⊞υ⊞ＯκΦζμ

... create the next partial placement to be processed, otherwise...

⊞ηΦκλ

... collect the possible placement, removing any empty dice.

»»⊟Φη⁼Ｌι⌊ＥηＬλ

Output any of the placements that have the fewest dice.

Since the above version is so inefficient, I have also written a slightly less inefficient 175 byte version that can handle slightly less trivial cases:

ＮθＷＳ⊞υι≔⌈ＥυＬιη≔⊟Φυ⁼Ｌιηζ≔⟦⊞ＯＥ⌈⟦ηＬ⪪⪫υωθ⟧⎇‹ιη§ζιω⁻υ⟦ζ⟧⟧υ≔⟦⟧ηＦυ«≔⊟ιζ¿ζ«≔§ζ⁰ε≔Φζλζ≔ＥΦＥＸＬιＬε﹪÷κＸＬιＥενＬι⬤κ⁼¹№κμＥι⁺μ…§ε⌕κν›№κν№μ§ε⌕κνδ≔⌊ＥδＬ⪫κωεＦδ¿›⁼εＬ⪫κω⊙κ›Ｌλθ⊞υ⊞Ｏκζ»⊞ηΦικ»⊟Φη⁼Ｌι⌊ＥηＬλ

Try it online! Link is to verbose version of code. Explanation: Only one permutation of the longest string and only word placements that reuse the most possible dice are considered, so for the example of TOO and ON, the letters of TOO will be put on three dice, and then the O of ON will never be matched with the T.