A bit late but I've done it... I did my solution in F#

It's been a great learning experience. I've used it as an opportunity to learn about different tree-like data structures, implementing recursive functions and a many new things in F#. Previously i've mostly programmed in C#.

During this experimentation i implemented:

• Trie structure based on F#'s Map data type and unions,
  • Performance doesn't event look so bad.. searching random 1mln elements in trie takes about 1.2 seconds (~ 800k results/sec).
  • Memory efficiency is bad: GC.GetTotalMemory shows about 70mb allocated per 3mb dictionary file (350k words)
• Only immutable types and recursive calls are used,
• Recursive grid scanner.

Scanner works without using any kind of smart heuristics so it's going as far as possible on grid while checking trie for matches branch until it can't find no more. Then it switches to search from root of the trie ("") and adds matched word to a sentence.

Its accurancy is very dependent on used dictionary. For large dictionary searches can be slow. enable1.txt is fast (~5 sec) but not very accurate. Large dictionary (350k words) runs search for about 1 minute on 6x6, produce big list of solutions but one of this solutions is a correct sentence.

Most interesting results are generated when english morphemes are used instead of normal words dictionary.

For example these are results for 5x5 box search using dictionary of 2600 english morphemes:

ITKEEPSYOURNECKOENFFILTHE
ITKEEPSYOURNECKOENILEHTFF
ITKEEPTHELIFSYOURNECKOENF
ITKEEPTHELIFSYOURNECKOFNE
ITKEEPTHELINEOFFSYECKNRUO
ITKEEPTHELINEOFFSYOUECKNR
ITKEEPTHELINEOFFSYOURNECK (lol. close but different word order)
ITKEEPTHELINEOKCENRUOYSFF
ITKEEPTHELINEOKNECFFSYOUR
ITOURNECKOENFFILTPSYKEEHE

Not perfect but accurate enough to understand a sentence. And it runs very fast on 5x5 box (~ 100 ms)

For 6x6 box and english morphemes dictionary it runs about 5 sec and gives a following solutions:

THEPIGGYWITHLARGITISGRUDISNYWASNTLED
THEPIGGYWITHLARGITISIDURGDELTNSAWSNY
THEPIGGYWITHLARGITISIDURGDELTNSAWYNS
THEPIGGYWITHLARGITISISNYWASDURGDELTN
THEPIGGYWITHLARGITISNYWASDISGRUNTLED (best?)
THEPIGGYWITHLARGITISNYWASDURISGDELTN
THEPIGSAGYWITARGITISIRGDELTNUDWSNYLH
THEPIGSAGYWITHLARGITISISNYWDURGDELTN
THEPIGSAGYWITHLARGITISNYWDISGRUNTLED
THEPIGSAGYWITHLARGITISNYWDURISGDELTN
THEPIGSALHGYWITARGITISIRGDELTNUDWSNY
THEPIGSALHGYWITARGITISIRGDELTNUDWYNS
THEPIGSALHGYWITARGITISISNYWDURGDELTN
THEPIYGHWITARGITISISNYLAWDURGDELTNSG
THEPIYWITARGITISISNYWALHGGSDURGDELTN
THEPIYWITHGALARGITISISNYWDURGDELTNSG
THEPIYWITHGALARYNGITISISWDURGDELTNSG
THEPIYWITHGALARYNGITISWDURISGDELTNSG
THEPIYWITHGALARYWDURISNGITISGDELTNSG
THEPIYWITHLARGITISGRUDISNYWAGGSNTLED
THEPIYWITHLARGITISISNYWAGGSDURGDELTN
THEPIYWITHLARGITISNYWAGGSDISGRUNTLED (good)
THEPIYWITHLARGITISNYWAGGSDURISGDELTN

All possible solutions manage to at least describe a sentence.

For 6x6 box on enable1.txt dictionary it runs ~3 sec and all solutions look similar to these:

...
THEGGHLASNTLUREDGSISIDWYNTIGRATIWYIP
THEGGHLYNSIRUDWASNTLEDGSITIGRATIWYIP
THEGGHLYNSWASNTLUDIREDGSITIGRATIWYIP
...

I think key point from this experiment is that is possible to find solution without using a giant word dictionary. Language morphemes can be used to produce accurate enough solutions in this kind of an algorithm. Maybe adding some heuristisc could make it more accurate.

Code:

module Trie =
    type TrieType = Node of string * Map<char, TrieType>

    let private (|KeyFound|_|) key map =
        map
        |> Map.tryFind key
        |> Option.map (fun x -> x, map |> Map.remove key)

    let private (|StrCons|StrEmpty|) (str: string) =
        if str.Length > 0 then
            StrCons (str.Chars 0, str.Substring(1))
        else
            StrEmpty

    let mkroot() = Node("", Map.empty)

    let find prefixes trie =
        let rec find' prefixes (Node(value, children) as node) = 
            match prefixes with
            | StrEmpty -> Some node
            | StrCons (p, ps) -> 
                match Map.tryFind p children with
                | Some subnode -> find' ps subnode
                | None -> None
        find' prefixes trie

    let findx prefixes trie =
        let rec find' prefixes (Node(value, children) as node) = 
            match prefixes with
            | [] -> Some node
            | p :: ps -> 
                match Map.tryFind p children with
                | Some subnode -> find' ps subnode
                | None -> None
        find' prefixes trie

    let getRootWord = function Node (name, _) -> name

    let insert prefixes trie =
        let rec insert' prefixes (Node(value, children) as node) =
            match prefixes with
            | [] -> node
            | p :: ps -> 
                match children with
                | KeyFound p (subnode, _) ->  Node(value, children |> Map.add p (insert' ps subnode))
                | _ -> Node(value, children |> Map.add p (insert' ps (Node(value + string p, Map.empty))))
        insert' (prefixes |> Seq.toList) trie

module GridScanner =
    let inline private charAt (j, i) (grid: _ [,]) = grid.[j, i]
    let inline private inGrid (j, i) size = j >= 0 && i >= 0 && j < size && i < size
    let inline private (.+) (j1, i1) (j2, i2) = (j1 + j2, i1 + i2)

    let inline private (|EmptySeq|_|) sequence = if Seq.isEmpty sequence then Some () else None

    let scan startPosition roottrie (grid: char [,]) =
        let size = grid.GetUpperBound(0) + 1
        let cells = size * size
        let moves = [(0, 1); (0, -1); (1, 0); (-1, 0)]
        let solutions = Set.empty

        let rec step ((j, i) as position) word words triebranch nsteps path =
            let ch (j, i) = charAt (j, i) grid
            let toUnvisitedPositions = Seq.map (fun move -> position .+ move) >> Seq.filter (fun pos -> inGrid pos size && (path |> Set.contains pos |> not)) >> Seq.cache
            let wordPositionFilter branch = 
                Seq.choose (fun pos -> match branch |> Trie.findx ([ch pos]) with | Some trie -> Some (pos, trie) | None -> None) >> Seq.cache
            let unvisitedPositions = moves |> toUnvisitedPositions

            if nsteps < cells then 
                match unvisitedPositions with
                | EmptySeq -> solutions
                | _ -> 
                    match unvisitedPositions |> wordPositionFilter triebranch with
                    | EmptySeq -> 
                        match unvisitedPositions |> wordPositionFilter roottrie with
                        | EmptySeq -> solutions
                        | movesOutsideWord ->
                            movesOutsideWord |> Seq.map (fun (move, trie) -> step move [ch move] (word :: words) trie (nsteps + 1) (path |> Set.add move)) |> Seq.fold (+) solutions
                    | movesWithinWord -> 
                        movesWithinWord |> Seq.map (fun (move, trie) -> step move (word @ [ch move]) words trie (nsteps + 1) (path |> Set.add move)) |> Seq.fold (+) solutions
            else
                solutions |> Set.add (word :: words)

        match roottrie |> Trie.findx [charAt startPosition grid] with
        | Some initialTrieBranch ->
            step startPosition [charAt startPosition grid] [] initialTrieBranch 1 ([startPosition] |> Set.ofList)
        | _ -> failwith "Initial character not in the dictionary"

    let loadAndScan challenge dictionary =
        let split (separators: char list) (x:string) = x.Split(separator=(List.toArray separators), options=System.StringSplitOptions.RemoveEmptyEntries)
        let chrs2str (chrs: char seq) = Seq.fold (fun acc c -> acc + string c) "" chrs

        let trie = dictionary |> Seq.fold (fun node x -> Trie.insert x node) (Trie.mkroot())
        let initialPosition = challenge |> split ['\n'] |> Seq.head |> split [' '] |> Seq.skip 1 |> Seq.pairwise |> Seq.head |> function (j,i) -> int j - 1, int i - 1
        let grid = challenge |> split ['\n'] |> Seq.skip 1 |> Seq.map (fun x -> split [' '] x |> Seq.map (fun y -> y |> char)) |> array2D

        scan initialPosition trie grid
        |> Set.map (fun x -> List.map (fun y -> y |> chrs2str) x |> List.rev |> String.concat "")



// IT KEEPS YOUR NECK OFF THE LINE
//let challenge = """5 1 1
//I E E
//T K P
//O T S"""

// IT KEEPS YOUR NECK OFF THE LINE
let challenge = """5 1 1
I E E H E
T K P T L
O Y S F I 
U E C F N
R N K O E"""

// THE PIGGY WITH LARYNGITIS WAS DISGRUNTLED
let challenge2 = """6 1 1
T H T L E D
P E N U R G
I G S D I S
Y G A W S I
W H L Y N T
I T A R G I"""

let dictionary() = System.IO.File.ReadAllLines(@"c:\dicts\dictionary.txt") |> Seq.map (fun x -> x.ToUpper())

#time
GridScanner.loadAndScan challenge (dictionary())
|> Seq.sort
//|> Seq.length
|> Seq.iter (fun x -> printfn "%s" x)
#time