Word search puzzle generation

Question

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.

• Geobits: 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.
• Peter Taylor: 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?
• Migue: Yes, it should be found only in one position.
• Peter Taylor: 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.
• orlp: 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.

Answer 1

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,

• Nathan Merrill: On your last test case, isn't it possible in a 3x3 grid?
• edc65: @NathanMerrill no. More detail in the answer text
• firephil: totally unreadable code :) but nice that is the downside of byte/point "award" don't be a human compiler
• edc65: @firephil trying to add an explanation, it's not easy ...

Answer 2

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);
 }
 public void AddWords(List<string> list)
 {
 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;
 tiles.Add(t);
 }
 }
 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;
 tiles.Add(t);
 }
 }
 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++;
 tiles.Add(t);
 }
 }
 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.AddWords(list);
 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)
 {
 t.Add(s.Trim());
 }
 WordSearch.Generate(t);
 Console.ReadKey();
 }
}

• firephil: it works but its not optimal : sample string words = "CAT,DOG,HR,RUN,CMD"
• edc65: Do you check if the random fill characters cause the repetition of a word in the grid?
• edc65: -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)
• mbomb007: This question is code-golf, so you should post how many bytes in the title, and probably shorten your program a bunch. Thanks.
• bacchusbeale: @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.