JavaScript (ES6), 595 628 680
Edit Some cleanup and merge:
- function P merged inside function R
- calc x and z in the same .map
- when solution found, set x to 0 to exit outer loop
- merged definiton and call of W
Edit2 more golfing, random fill shortened, outer loop revised ... see history for something more readable
Unlike the accepted answer, this should work for most inputs. Just avoid single letter words. If an output is found, it's optimal and using all 3 directions.
The constraint of avoiding repeating words is very hard.
I had to look for repeating word at each step adding word to the grid, and at each random fill character.
Main subfunctions:
P(w) true if palindrome word. A palindrom word will be found twice when checking for repeated words.
R(s) check repeating words on grid s
Q(s) fill the grid s with random characters - it's recursive and backtrack in case of repeating word - and can fail.
W() recursive, try to fill a grid of given size, if possibile.
The main function use W() to find an output grid, trying from a size of the longest word in input up to the sum of the length of all words.
F=l=>{
for(z=Math.max(...l.map(w=>(w=w.length,x+=w,w),x=0));
++z<=x;
(W=(k,s,m,w=l[k])=>w?s.some((a,p)=>!!a&&
D.some((d,j,_,r=[...s],q=p-d)=>
[...w].every(c=>r[q+=d]==c?c:r[q]==1?r[q]=c:0)
&&R(r)&&W(k+1,r,m|1<<(j/2))
)
)
:m>12&&Q(s)&&(console.log(''+s),z=x)
)(0,[...Array(z*z-z)+99].map((c,i)=>i%z?1:'\n'))
)
D=[~z,-~z,1-z,z-1,z,-z,1,-1]
,R=u=>!l.some(w=>u.map((a,p)=>a==w[0]&&D.map(d=>n+=[...w].every(c=>u[q+=d]==c,q=p-d)),
n=~([...w]+''==[...w].reverse()))&&n>0)
,Q=(u,p=u.indexOf(1),r=[...'ABCDEFGHIJHLMNOPQRSTUVWXYZ'])=>
~p?r.some((v,c)=>(r[u[p]=r[j=0|c+Math.random()*(26-c)],j]=v,R(u)&&Q(u)))||(u[p]=1):1
//,Q=u=>u.map((c,i,u)=>u[i]=c!=1?c:' ') // uncomment to avoid random fill
}
Ungolfed and explained (incomplete, sorry guys it's a lot of work)
F=l=>
{
var x, z, s, q, D, R, Q, W;
// length of longest word in z
z = Math.max( ... l.map(w => w.length))
// sum of all words length in x
x = 0;
l.forEach(w => x += w.length);
for(; ++z <= x; ) // test square size from z to x
{
// grid in s[], each row of len z + 1 newline as separator, plus leading and trailing newline
// given z==offset between rows, total length of s is z*(z-1)+1
// gridsize: 2, z:3, s.length: 7
// gridsize: 3, z:4, s.length: 13
// ...
// All empty, nonseparator cells, filled with 1, so
// - valid cells have a truthy value (1 or string)
// - invalid cells have falsy value ('\n' or undefined)
s = Array(z*z-z+1).fill(1)
s = s.map((v,i) => i % z != 0 ? 1 : '\n');
// offset for 8 directions
D = [z+1, -z-1, 1-z, z-1, z, -z, 1, -1]; // 4 diags, then 2 vertical, then 2 horizontal
// Function to check repeating words
R = u => // return true if no repetition
! l.some( w => // for each word (exit early when true)
{
n = -1 -([...w]+''==[...w].reverse()); // counter starts at -1 or -2 if palindrome word
u.forEach( (a, p) => // for each cell if grid
{
if (a == [0]) // do check if cell == first letter of word, else next word
D.forEach( d => // check all directions
n += // word counter
[...w].every( c => // for each char in word, exit early if not equal
u[q += d] == c, // if word char == cell, continue to next cell using current offset
q = p-d // starting position for cell
)
) // end for each direction
} ) // end for each cell
return n > 0 // if n>0 the word was found more than once
} ) // end for each word
// Recursive function to fill empty space with random chars
// each call add a single char
Q =
( u,
p = u.indexOf(1), // position of first remaining empty cell
r = [...'ABCDEFGHIJHLMNOPQRSTUVWXYZ'] // char array to be random shuffled
) => {
if (~p) // proceed if p >= 0
return r.some((v,c)=>(r[u[p]=r[j=0|c+Math.random()*(26-c)],j]=v,R(u)&&Q(u)))||(u[p]=1)
else
return 1; // when p < 0, no more empty cells, return 1 as true
}
// Main working function, recursive fill of grid
W =
( k, // current word position in list
s, // grid
m, // bitmask with all directions used so far (8 H, 4V, 2 or 1 diag)
w = l[k] // get current word
) => {
var res = false
if (w) { // if current word exists
res = s.some((a,p)=>!!a&&
D.some((d,j,_,r=[...s],q=p-d)=>
[...w].every(c=>r[q+=d]==c?c:r[q]==1?r[q]=c:0)
&&R(r)&&W(k+1,r,m|1<<(j/2))
)
)
}
else
{ // word list completed, check additional constraints
if (m > 12 // m == 13, 14 or 15, means all directions used
&& Q(s) ) // try to fill with random, proceed if ok
{ // solution found !!
console.log(''+s) // output grid
z = x // z = x to stop outer loop
res = x//return value non zero to stop recursion
}
}
return res
};
W(0,s)
}
}
Test in Firefox/FireBug console
F(['TRAIN', 'CUBE','BOX','BICYCLE'])
,T,C,B,O,X,B,H,
,H,R,U,H,L,I,H,
,Y,A,A,B,E,C,B,
,D,H,S,I,E,Y,I,
,H,E,R,L,N,C,T,
,G,S,T,Y,F,L,U,
,H,U,Y,F,O,E,H,
not filled
,T,C,B,O,X,B, ,
, ,R,U, , ,I, ,
, , ,A,B, ,C, ,
, , , ,I,E,Y, ,
, , , , ,N,C, ,
, , , , , ,L, ,
, , , , , ,E, ,
F(['TRAIN','ARTS','RAT', 'CUBE','BOX','BICYCLE','STORM','BRAIN','DEPTH','MOUTH','SLAB'])
,T,A,R,C,S,T,H,
,S,R,R,L,U,D,T,
,T,B,A,T,N,B,P,
,O,B,O,I,S,A,E,
,R,B,A,X,N,H,D,
,M,R,M,O,U,T,H,
,B,I,C,Y,C,L,E,
F(['AA','AB','AC','AD','AE','AF','AG'])
,A,U,B,C,
,T,A,E,Z,
,C,D,O,F,
,Q,C,G,A,
F(['AA','AB','AC','AD','AE','AF'])
output not filled - @nathan: now you can't add another Ax without repetitions. You'll need a bigger grid.
,A, ,C,
, ,A,F,
,D,E,B,
AC
in your example would make anotherCAT
if it'sT
. \$\endgroup\$A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
has no solution. \$\endgroup\$