Word search puzzle generation

Given a list of strings, find the smallest square matrix that contains each of the initial strings. The strings may appear horizontally, vertically or diagonally and forwards or backwards like in this question Word Search Puzzle.

Words should be placed in the square, with at least one word in each direction (horizontal, vertical and diagonal). Words should appear just one time.

So, the input is just a list of words. For example: CAT, TRAIN, CUBE, BICYCLE. One possible solution is:

B N * * * * *
* I * * C A T
* A C * * * *
* R * Y * * C
* T * * C * U
* * * * * L B
* * * * * * E


I replaced filling letters with asterisks just for clarity. The desired output should include random filling letters.

• Must each word be found in only one position (like typical word searches)? For instance, the letter left of AC in your example would make another CAT if it's T. Mar 2, 2015 at 17:45
• It's not clear to me what exactly you mean by "Words should be placed randomly in all directions". Would an answer meet this criterion if, having laid the words out deterministically, it randomly selects one of the eight symmetries of the square? Or, at the other extreme, should the output be selected uniformly from all the possible smallest squares which contain the words? Or is the line drawn somewhere in between those extremes? Mar 2, 2015 at 18:01
• Yes, it should be found only in one position. Mar 2, 2015 at 18:02
• Not really, no. I'm still not clear what the space from which an answer should randomly sample is, nor how much flexibility is allowed in weighting the elements of that space. Mar 2, 2015 at 23:10
• As of now, the question has inputs that can not be solved, but no mention is made of how you're supposed to deal with that. For example the set 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.
– orlp
Mar 21, 2015 at 2:55

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,


,A,U,B,C,
,T,A,E,Z,
,C,D,O,F,
,Q,C,G,A,


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,

• On your last test case, isn't it possible in a 3x3 grid? Mar 23, 2015 at 21:38
• @NathanMerrill no. More detail in the answer text Mar 23, 2015 at 22:02
• totally unreadable code :) but nice that is the downside of byte/point "award" don't be a human compiler Mar 24, 2015 at 8:49
• @firephil trying to add an explanation, it's not easy ... Mar 24, 2015 at 17:29

C#

Here's a simple implementation with still work to be done. There are very many combinations to get smallest size. So just used simplest algorithm in could think of.

class Tile
{
public char C;
public int X, Y;
}

class Grid
{
List<Tile> tiles;

public Grid()
{
tiles = new List<Tile>();
}
public int MaxX()
{
return tiles.Max(x => x.X);
}
public int MaxY()
{
return tiles.Max(x => x.Y);
}
{
int n = list.Count;
for (int i = 0; i < n; i++)
{
string s = list[i];
if(i==0)
{
Vert(s, 0, 0);
}
else if(i==n-1)
{
int my = MaxY();
Diag(s, 0, my+1);
}
else
{
Horiz(s, 0, i);
}
}

}
private void Vert(string s, int x, int y)
{
for (int i = 0; i < s.Length; i++)
{
Tile t = new Tile();
t.C = s[i];
t.X = x+i;
t.Y = y;
}
}
private void Horiz(string s, int x, int y)
{
for (int i = 0; i < s.Length; i++)
{
Tile t = new Tile();
t.C = s[i];
t.X = x+i;
t.Y = y;
}
}
private void Diag(string s, int x, int y)
{
for (int i = 0; i < s.Length; i++)
{
Tile t = new Tile();
t.C = s[i];
t.X = x++;
t.Y = y++;
}
}
public void Print()
{
int mx = this.MaxX();
int my = this.MaxY();
int S = Math.Max(mx, my) + 1;
char[,] grid = new char[S, S];
Random r = new Random(DateTime.Now.Millisecond);
//fill random chars
for (int i = 0; i < S; i++)
{
for (int j = 0; j < S; j++)
{
grid[i, j] = (char)(r.Next() % 26 + 'A');
}
}
//fill words
tiles.ForEach(t => grid[t.X, t.Y] = t.C);
//print
for (int i = 0; i < S; i++)
{
for (int j = 0; j < S; j++)
{
Console.Write("{0} ", grid[i,j]);
}
Console.WriteLine();
}
}
}

class WordSearch
{
public static void Generate(List<string>list)
{
list.Sort((x, y) =>
{ int s = 0; if (x.Length < y.Length)s = -1; else if (y.Length < x.Length)s = 1; return s; });
list.Reverse();
Grid g = new Grid();
g.Print();
}

}


Test

class Program
{
static void Main(string[] args)
{
string words = "CAT, TRAIN, CUBE, BICYCLE";
string comma=",";
List<string> w = words.Split(comma.ToArray()).ToList();
List<string> t = new List<string>();
foreach(string s in w)
{
}
WordSearch.Generate(t);

}
}

• it works but its not optimal : sample string words = "CAT,DOG,HR,RUN,CMD"; Mar 23, 2015 at 11:23
• Do you check if the random fill characters cause the repetition of a word in the grid? Mar 23, 2015 at 14:15
• -1 Tried it. Does not follow the specs at least one word in each direction (horizontal, vertical and diagonal). Running the test program, no horizontal word (3 vertical, 1 diag) Mar 23, 2015 at 16:36
• This question is code-golf, so you should post how many bytes in the title, and probably shorten your program a bunch. Thanks. Mar 23, 2015 at 18:28
• @edc65 It does one vertical, one diagonal and all others horizontal. As I commented to get perfect solution will require enormous number of combinations to check as well as the specifications of the question. Mar 24, 2015 at 11:38