Words Everywhere

Question

Given a list of words, output a square grid of characters, so that all the words can be read from the grid, by moving horizontally, vertically, or diagonally between characters, without reusing characters in the same word. The grid must be the smallest possible which allows all words to be read.

Example

B A D
R E T
E Y E

The above grid contains the words BAD, BAR, BARE, TAB, TEAR, EYE, EAR, TEE, TEED, BEAR, BEAD, BEET, DARE and YEAR (plus more, and duplicates of these in some cases). It could therefore be a valid output for the input list YEAR, BEET, DARE - the grid must be at least 3x3, since at least 8 characters are required (7 distinct characters, and 2 Es), which wouldn't fit in a 2x2 grid.

Y D R
B E A
T E E

The above grid would be another valid output for the input YEAR, BEET, DARE, but would not be valid if EYE was added to the input list, despite containing the same letters as the previous grid, since there is no way to reach the Y from two distinct Es.

There is no assumption that "words" in this challenge are English words, or even formed of letters - they are simply any string of at least 3 characters.

For input ☃️, ☃️❄️, ️

☃️  
❄️ ️ ☃️
  ❄️

would be a valid output. In this case, all the "words" can be read in straight lines, which wasn't possible with the previous example (no way to fit a 4 letter word into a 3x3 grid without a turn)

Rules

• Standard loopholes are forbidden.
• You can take input in any acceptable format (see Input/Output methods meta post)
• You can output in any acceptable format, as long as it is trivial to check that it is a square manually. For example, outputting BADRETEYE is not trivial to check - you need to count the characters, and take the square root of this, which is far too much effort for larger grids. Outputting BAD RET EYE is trivial to check - you count how many groups, and the length of any group, and if they are the same, the grid is square.
• You can fill in any gaps in the grid with any characters from the input
• Letters can only be used once in each word
• The grid should be as small as possible - the lower bound will be the square number above number of distinct characters required (e.g. 8 distinct characters would require 9 characters of output at minimum, but may require more characters if positioning means that they can't be read simultaneously)
• Languages without Unicode support (e.g. C64 BASIC, things that only run on calculators) may ignore the Unicode test case
• It's code-golf, so shortest answer in bytes wins!

Test Data

• ANT - should give a 2x2 grid, with one letter repeated
• ANT, TAN, NAT - may well give same grid as previous
• ANT, MAN - 2x2 grid, with each of A, N, T, and M included once
• YEAR, BEET, DARE - 3x3 grid
• YEAR, BEET, DARE, EYE - 3x3 grid
• BAD, BAR, BARE, TAB, TEAR, EYE, EAR, TEE, TEED, BEAR, BEAD, BEET, DARE, YEAR - 3x3 grid
• ANTMAN, BATMAN, BANANA - 3x3 grid
• CHAOS, ORDER - 3x3 grid, no spare spaces
• SUPERMAN, SHAZAM - 4x4 grid
• 123, 1337, 911, 999, 112 - non-letters, 3x3
• SUPERGIRL, FLASH, ARROW, GOTHAM, BLACKLIGHTNING, KRYPTON, TITANS, DOOMPATROL - no idea, but at least 6x6
• ABSENTMINDEDNESS, MINT, DINED, TABS, STAND, SEATED - no idea, but might be a 4x4, since only 16 required letters
• ☃️, ☃️❄️, ️ - Unicode characters, 3x3
• AUCTIONED, CAUTIONED, EDUCATION - 3x3
• COUNTRIES, CRETINOUS, NEUROTICS - at least 4x4 - both R and E need to be next to 6 distinct letters, which isn't possible on 3x3 grid

Notes

• Inspired by the game "Words Everywhere" in the Word Games Pro app from LittleBigPlay, available on Google Play
• Solving Is This a Boggle Pad? in the unrestricted NxN case might be useful to determine the minimum required size, but is unlikely to help with actually generating the output
• There is a kind of inverse of this challenge at Is This Word on the Boggle Pad

Answer 1

Python 3, 444 bytes

def p(g,v=[]):
	l=len(g);r=[*range(l)];k=[[(x,y)]for x in r for y in r if(x,y)not in v]
	if len(k)<2:return[k[0]]
	return[n+N for n in k for N in p(g,v+n)if max(abs(N[0][0]-n[0][0]),abs(N[0][1]-n[0][1]))<2]
from itertools import*
def f(a):
	i=2;w=set("".join(a))
	while 1:
		for f in product(*[w]*i*i):
			g=[f[k*i:][:i]for k in range(i)];P=["".join(g[x][y]for x,y in l)for l in p(g)]
			if all(any(c in n for n in P)for c in a):return g
		i+=1

Try it online!

Horribly inefficient. The function f takes a list of words and returns a grid of characters as a list of tuples. The footer is just for formatting to take input and pretty-print output.

(Also when I golf this I get to make a crossed-out-44 meme :D)