A word search puzzle typically consists of a grid of letters in which words are hidden.

There are many varieties of word search puzzles. For the task at hand we will use a rectangular grid in which the words may be placed horizontally, vertically, or diagonally. The words may also be spelled backwards.

The words may overlap but are not allowed to zigzag, or wrap around.




Task 
Create a 10 by 10 word search and fill it using words from the unixdict. Use only words that are longer than 2, and contain no non-alphabetic characters.

The cells not used by the hidden words should contain the message: Rosetta Code, read from left to right, top to bottom. These letters should be somewhat evenly distributed over the grid, not clumped together. The message should be in upper case, the hidden words in lower case. All cells should either contain letters from the hidden words or from the message.

Pack a minimum of 25 words into the grid.

Print the resulting grid and the solutions.




Example
     0  1  2  3  4  5  6  7  8  9

0    n  a  y  r  y  R  e  l  m  f 
1    y  O  r  e  t  s  g  n  a  g 
2    t  n  e  d  i  S  k  y  h  E 
3    n  o  t  n  c  p  c  w  t  T 
4    a  l  s  u  u  n  T  m  a  x 
5    r  o  k  p  a  r  i  s  h  h 
6    a  A  c  f  p  a  e  a  c  C 
7    u  b  u  t  t  t  O  l  u  n 
8    g  y  h  w  a  D  h  p  m  u 
9    m  i  r  p  E  h  o  g  a  n 

parish     (3,5)(8,5)   gangster   (9,1)(2,1)
paucity    (4,6)(4,0)   guaranty   (0,8)(0,1)
prim       (3,9)(0,9)   huckster   (2,8)(2,1)
plasm      (7,8)(7,4)   fancy      (3,6)(7,2)
hogan      (5,9)(9,9)   nolo       (1,2)(1,5)
under      (3,4)(3,0)   chatham    (8,6)(8,0)
ate        (4,8)(6,6)   nun        (9,7)(9,9)
butt       (1,7)(4,7)   hawk       (9,5)(6,2)
why        (3,8)(1,8)   ryan       (3,0)(0,0)
fay        (9,0)(7,2)   much       (8,8)(8,5)
tar        (5,7)(5,5)   elm        (6,0)(8,0)
max        (7,4)(9,4)   pup        (5,3)(3,5)
mph        (8,8)(6,8)




Other tasks related to string operations:

Metrics
 Array length
 String length
 Copy a string
 Empty string  (assignment)
Counting
 Word frequency
 Letter frequency
 Jewels and stones
 I before E except after C
 Bioinformatics/base count
 Count occurrences of a substring
 Count how many vowels and consonants occur in a string
Remove/replace
 XXXX redacted
 Conjugate a Latin verb
 Remove vowels from a string
 String interpolation (included)
 Strip block comments
 Strip comments from a string
 Strip a set of characters from a string
 Strip whitespace from a string -- top and tail
 Strip control codes and extended characters from a string
Anagrams/Derangements/shuffling
 Word wheel
 ABC problem
 Sattolo cycle
 Knuth shuffle
 Ordered words
 Superpermutation minimisation
 Textonyms (using a phone text pad)
 Anagrams
 Anagrams/Deranged anagrams
 Permutations/Derangements
Find/Search/Determine
 ABC words
 Odd words
 Word ladder
 Semordnilap
 Word search
 Wordiff  (game)
 String matching
 Tea cup rim text
 Alternade words
 Changeable words
 State name puzzle
 String comparison
 Unique characters
 Unique characters in each string
 Extract file extension
 Levenshtein distance
 Palindrome detection
 Common list elements
 Longest common suffix
 Longest common prefix
 Compare a list of strings 
 Longest common substring
 Find common directory path
 Words from neighbour ones
 Change e letters to i in words
 Non-continuous subsequences
 Longest common subsequence
 Longest palindromic substrings
 Longest increasing subsequence
 Words containing "the" substring
 Sum of the digits of n is substring of n
 Determine if a string is numeric
 Determine if a string is collapsible
 Determine if a string is squeezable
 Determine if a string has all unique characters
 Determine if a string has all the same characters
 Longest substrings without repeating characters
 Find words which contains all the vowels
 Find words which contains most consonants
 Find words which contains more than 3 vowels
 Find words which first and last three letters are equals
 Find words which odd letters are consonants and even letters are vowels or vice_versa
Formatting
 Substring
 Rep-string
 Word wrap
 String case
 Align columns
 Literals/String
 Repeat a string
 Brace expansion
 Brace expansion using ranges
 Reverse a string
 Phrase reversals
 Comma quibbling
 Special characters
 String concatenation
 Substring/Top and tail
 Commatizing numbers
 Reverse words in a string
 Suffixation of decimal numbers
 Long literals, with continuations 
 Numerical and alphabetical suffixes
 Abbreviations, easy
 Abbreviations, simple
 Abbreviations, automatic
Song lyrics/poems/Mad Libs/phrases
 Mad Libs
 Magic 8-ball
 99 Bottles of Beer
 The Name Game (a song)
 The Old lady swallowed a fly
 The Twelve Days of Christmas
Tokenize
 Text between
 Tokenize a string
 Word break problem
 Tokenize a string with escaping
 Split a character string based on change of character
Sequences
 Show ASCII table
 De Bruijn sequences
 Self-referential sequences
 Generate lower case ASCII alphabet




Module Module1
 
    ReadOnly Dirs As Integer(,) = {
        {1, 0}, {0, 1}, {1, 1},
        {1, -1}, {-1, 0},
        {0, -1}, {-1, -1}, {-1, 1}
    }
 
    Const RowCount = 10
    Const ColCount = 10
    Const GridSize = RowCount * ColCount
    Const MinWords = 25
 
    Class Grid
        Public cells(RowCount - 1, ColCount - 1) As Char
        Public solutions As New List(Of String)
        Public numAttempts As Integer
 
        Sub New()
            For i = 0 To RowCount - 1
                For j = 0 To ColCount - 1
                    cells(i, j) = ControlChars.NullChar
                Next
            Next
        End Sub
    End Class
 
    Dim Rand As New Random()
 
    Sub Main()
        PrintResult(CreateWordSearch(ReadWords("unixdict.txt")))
    End Sub
 
    Function ReadWords(filename As String) As List(Of String)
        Dim maxlen = Math.Max(RowCount, ColCount)
        Dim words As New List(Of String)
 
        Dim objReader As New IO.StreamReader(filename)
        Dim line As String
        Do While objReader.Peek() <> -1
            line = objReader.ReadLine()
            If line.Length > 3 And line.Length < maxlen Then
                If line.All(Function(c) Char.IsLetter(c)) Then
                    words.Add(line)
                End If
            End If
        Loop
 
        Return words
    End Function
 
    Function CreateWordSearch(words As List(Of String)) As Grid
        For numAttempts = 1 To 1000
            Shuffle(words)
 
            Dim grid As New Grid()
            Dim messageLen = PlaceMessage(grid, "Rosetta Code")
            Dim target = GridSize - messageLen
 
            Dim cellsFilled = 0
            For Each word In words
                cellsFilled = cellsFilled + TryPlaceWord(grid, word)
                If cellsFilled = target Then
                    If grid.solutions.Count >= MinWords Then
                        grid.numAttempts = numAttempts
                        Return grid
                    Else
                        'grid is full but we didn't pack enough words, start over
                        Exit For
                    End If
                End If
            Next
        Next
 
        Return Nothing
    End Function
 
    Function PlaceMessage(grid As Grid, msg As String) As Integer
        msg = msg.ToUpper()
        msg = msg.Replace(" ", "")
 
        If msg.Length > 0 And msg.Length < GridSize Then
            Dim gapSize As Integer = GridSize / msg.Length
 
            Dim pos = 0
            Dim lastPos = -1
            For i = 0 To msg.Length - 1
                If i = 0 Then
                    pos = pos + Rand.Next(gapSize - 1)
                Else
                    pos = pos + Rand.Next(2, gapSize - 1)
                End If
                Dim r As Integer = Math.Floor(pos / ColCount)
                Dim c = pos Mod ColCount
 
                grid.cells(r, c) = msg(i)
 
                lastPos = pos
            Next
            Return msg.Length
        End If
 
        Return 0
    End Function
 
    Function TryPlaceWord(grid As Grid, word As String) As Integer
        Dim randDir = Rand.Next(Dirs.GetLength(0))
        Dim randPos = Rand.Next(GridSize)
 
        For d = 0 To Dirs.GetLength(0) - 1
            Dim dd = (d + randDir) Mod Dirs.GetLength(0)
 
            For p = 0 To GridSize - 1
                Dim pp = (p + randPos) Mod GridSize
 
                Dim lettersPLaced = TryLocation(grid, word, dd, pp)
                If lettersPLaced > 0 Then
                    Return lettersPLaced
                End If
            Next
        Next
 
        Return 0
    End Function
 
    Function TryLocation(grid As Grid, word As String, dir As Integer, pos As Integer) As Integer
        Dim r As Integer = pos / ColCount
        Dim c = pos Mod ColCount
        Dim len = word.Length
 
        'check bounds
        If (Dirs(dir, 0) = 1 And len + c >= ColCount) Or (Dirs(dir, 0) = -1 And len - 1 > c) Or (Dirs(dir, 1) = 1 And len + r >= RowCount) Or (Dirs(dir, 1) = -1 And len - 1 > r) Then
            Return 0
        End If
        If r = RowCount OrElse c = ColCount Then
            Return 0
        End If
 
        Dim rr = r
        Dim cc = c
 
        'check cells
        For i = 0 To len - 1
            If grid.cells(rr, cc) <> ControlChars.NullChar AndAlso grid.cells(rr, cc) <> word(i) Then
                Return 0
            End If
 
            cc = cc + Dirs(dir, 0)
            rr = rr + Dirs(dir, 1)
        Next
 
        'place
        Dim overlaps = 0
        rr = r
        cc = c
        For i = 0 To len - 1
            If grid.cells(rr, cc) = word(i) Then
                overlaps = overlaps + 1
            Else
                grid.cells(rr, cc) = word(i)
            End If
 
            If i < len - 1 Then
                cc = cc + Dirs(dir, 0)
                rr = rr + Dirs(dir, 1)
            End If
        Next
 
        Dim lettersPlaced = len - overlaps
        If lettersPlaced > 0 Then
            grid.solutions.Add(String.Format("{0,-10} ({1},{2})({3},{4})", word, c, r, cc, rr))
        End If
 
        Return lettersPlaced
    End Function
 
    Sub PrintResult(grid As Grid)
        If IsNothing(grid) OrElse grid.numAttempts = 0 Then
            Console.WriteLine("No grid to display")
            Return
        End If
 
        Console.WriteLine("Attempts: {0}", grid.numAttempts)
        Console.WriteLine("Number of words: {0}", GridSize)
        Console.WriteLine()
 
        Console.WriteLine("     0  1  2  3  4  5  6  7  8  9")
        For r = 0 To RowCount - 1
            Console.WriteLine()
            Console.Write("{0}   ", r)
            For c = 0 To ColCount - 1
                Console.Write(" {0} ", grid.cells(r, c))
            Next
        Next
 
        Console.WriteLine()
        Console.WriteLine()
 
        For i = 0 To grid.solutions.Count - 1
            If i Mod 2 = 0 Then
                Console.Write("{0}", grid.solutions(i))
            Else
                Console.WriteLine("   {0}", grid.solutions(i))
            End If
        Next
 
        Console.WriteLine()
    End Sub
 
    'taken from https://stackoverflow.com/a/20449161
    Sub Shuffle(Of T)(list As IList(Of T))
        Dim r As Random = New Random()
        For i = 0 To list.Count - 1
            Dim index As Integer = r.Next(i, list.Count)
            If i <> index Then
                ' swap list(i) and list(index)
                Dim temp As T = list(i)
                list(i) = list(index)
                list(index) = temp
            End If
        Next
    End Sub
 
End Module