English dictionary fun

[Mike Lewis]

I don't know if anyone is still lurking in this forum. If so, here's a little exercise for you:

What are the longest words in English that can be made up from each row of a standard English typewriter keyboard?

So, each word can only contain letters from a single row, but each letter can be used multiple times.

I recently downloaded a file that contains 194,000 English words, and I hope to use it to generate various word games and puzzles. I started out by writing a program to find the answer to the above question. The results are quite interesting.

Mike

__________________________________
Mike Lewis (Edinburgh, Scotland)

Visual FoxPro articles, tips and downloads

 

[strongm]

>If you get to the end and the test has not failed, then you have a hit.

Also need to consider that if the test fails there may still be a different starting point that provides a hit (e.g. consider ATOC for current puzzle - fails if we use the first A in the grid, succeeds if we use the 2nd A)

 

[Chris Miller]

strongm,

good point, that's why I thought about working with the 9 digits. You then can create the allowed paths as a digit srting and turn these to letters or you can convert words to digits. In that direction you can take into account that letters may appear in more than one place.

Chriss

 

[Mike Lewis]

if the test fails there may still be a different starting point that provides a hit

Yes, that's why I said "I search the puzzle word for each occurrence of the first letter of the pair." I envisage an outer loop for each consecutive pair; then an inner loop for each occurrence of the first letter of the pair within the puzzle word.

Got a bad idea to make the puzzle more difficult : avoid the path crossing itself.

That would make it mind-bogglingly difficult (at least, for me).

I wondered about establishing a rule to say that every solution must go through the centre cell. I think that would make it easier. In any semi-automatic solution, you could greatly reduce the number of words to manually inspect, by discarding all words that don't contain the middle letter.

Mike

__________________________________
Mike Lewis (Edinburgh, Scotland)

Visual FoxPro articles, tips and downloads

 

[Mike Lewis]

Got a bad idea to make the puzzle more difficult : avoid the path crossing itself.

It occurs to me that that would make it much too easy to solve the first part of the puzzle, that is, finding the nine-letter word. You would have to arrange the puzzle so that the word in question always starts in of the corners, and always follows a horizontal or vertical path (row by row or column by column). In that case, the word would probably jump out at you. And if it didn't, there would only be eight possible paths to check (two directions for each of the four corners).

Mike

__________________________________
Mike Lewis (Edinburgh, Scotland)

Visual FoxPro articles, tips and downloads

 

[Chris Miller]

If you work with a graph implementation you can store which node edges cross each other and deny path that have that. Another way extending the idea to always include the middle node: Create all possible graphs with non-crossing edges, this may even be feasible to do manually, any diagonal edge can be slash or backslash, connecting either the middle node to a corner node or an edge node (2,4,6,8) with each other. That means you always have 4 slashes for the diagonals that can be slash or backslash and thus have 2^4= 16 graphs instead of the one where all nodes are connected to all neighbors.

To illustrate it.

That's the graph with all neighbor nodes connected:

1-2-3
!X!X!
4-5-6
!X!X!
7-8-9

That's a graph avoiding the crossings, ie avoiding the X and only using slash or backslash connections:

1-2-3
!/!/!
4-5-6
!\!\!
7-8-9

It's one of 16 graphs you can traverse in any way without any crossing.

 

[feherke]

Hi

Found the solution for my bad idea posted at 17 Sep 21 09:11.
Actually is pretty simple, just have to record the midpoints between the checked coordinate pairs :
[pre]
[gray]0 1 2[/gray]
[gray]0.5 1.5[/gray]
[gray]0[/gray] L A R
[silver]\ / \ /[/silver]
[gray]0.5[/gray] [silver]X X[/silver]
[silver]/ \ / \[/silver]
[gray]1[/gray] C O I
[silver]\ / \ /[/silver]
[gray]1.5[/gray] [silver]X X[/silver]
[silver]/ \ / \[/silver]
[gray]2[/gray] T A F
[/pre]
[spoiler trackword-no-cross.rb][pre]
word_maze = ARGV[0]
word_list = File.readlines 'english3.txt', chomp: true

3.upto 9 do |length|
[*0...9].permutation length do |order|
previous = nil
path = []
next unless order.all? do |i|
if previous then
next if (previous / 3 - i / 3).abs > 1 or (previous % 3 - i % 3).abs > 1
path.push [previous / 3 + i / 3, previous % 3 + i % 3]
end
previous = i
end
next if path.uniq!

word = order.map {|i| word_maze }.join

puts word if word_list.include? word
end
end[/pre]
[/spoiler]
This results only 82 words ( again, output changed a bit to avoid posting 82 lines ) :

3 letters : lar lac lao lor lot act air aia rac rai roc rot ria rio ria car col cor coi cot cat oar ora oca oca oat oaf ira tol tor tac tao tai act aia air for foi fir fat
4 letters : lair loir lota loaf aria acta raca rota rial riot clot caro cola coal cora coir coif coat oral octa iota tola tori taco atoc foal fora fiar fiat fact fair
5 letters : ariot actor claro clair coral cairo taira tafia acari focal
6 letters : lariat
7 letters :
8 letters :
9 letters :

This way the number od words that can be tracked on 2 different paths gets reduced to the 3 letter words ( which are not affected by my bad idea ) : act, aia, air, oca, ria.


Feherke.
feherke.github.io

 

[Mike Lewis]

I haven't tried to follow up Feherke's soltuion yet - I may get to it later - but I've been refining my brute force method.

In my previous attempt, I found all words whose letters were all present in the puzzle, but without regard to the navigation rules. In the case of the FACTORIAL puzzle, that produced 165 words. I've now inserted a test for "adjacency", which means that a word will be rejected if no consecutive pair of letters in the word matches a pair of letters in adjacent cells of the puzzle. This brought the word count down to 76.

But I'm not quite there yet. As Strongm pointed out, this won't work if any letter occurs more than once in the puzzle, as is the case with the A in FACTORIAL. In that case, we will get false positives. For example, it finds RAT, even though this does not follow the navigation rule. That's because R is adjacent to A, and A is adjacent to T - but it's a different A.

However, I reckon on always doing a manual review of the results, to eliminate proper nouns, etc. as well as any ultra-obscure words. So I can manually eliminate any words that fail the navigation test at the same time. In this case, that brought the score down from 76 to 38, which matches the figure I got from my initial attempt (as per the solution in post dated 16 Sep 21 15:21 above).

I'm just tidying up my code and adding comments. If anyone is interested, I'll post it here.

Mike

__________________________________
Mike Lewis (Edinburgh, Scotland)

Visual FoxPro articles, tips and downloads

 

[Mike Lewis]

So here is the code for my latest solution, as described in my previous post. The code is in Visual FoxPro. For the benefit of those not intimate with the language, I have added some explanatory comments, which I hope you will find helpful.

First, here is the code for my initial brute-force method. This finds all words that contain the correct letters, but fails to take account of the navigation rules. For the moment, disregard the text flagged as TEMP COMMENTED-OUT. This is code that wasn't present in the initial version.

* Trackword solver. Written in Visual FoxPro 9.0.

LOCAL lcWord, lcPuzzle, lcPuzzleMain, lnI, llFound

CREATE CURSOR csrSolution (cWord c(9))
    && In VFP, a "cursor" is a temporary table.

* The Words table contains two columns; cWord is the dictionary word;
* nLen is the length of the word. Both columns are indexed.
IF NOT USED("Words")
    USE Words IN 0
ENDIF
SELECT Words
SET ORDER TO nLen

lcPuzzleMain = "LARCOITAF"
    && Here, we are hard-coding the puzzle word (FACTORIAL); in practice
    && we would pass it in as a parameter or read it in from an
    && external source.
LOCATE FOR nLen = 3
SCAN WHILE nLen <= 9
    * Do a pass or the Words table, looking at all rows whose word length
    * is between 3 and 9.
    lcWord = UPPER(ALLTRIM(Words.cWord))
    lcPuzzle = lcPuzzleMain

    llFound = .F.
    && In VFP, .F. means False and .T. means True

    * For each letter in the puzzle word, remove the corresponding letter
    * (if any) in the dictionary word.
    FOR lnI = 1 TO LEN(lcWord)
        lcLetter = SUBSTR(lcWord, lnI, 1)
        IF AT(lcLetter, lcPuzzle, 1) > 0
            lcPuzzle = STRTRAN(lcPuzzle, lcLetter, "", 1, 1)
            llFound = .T.
        ELSE
            * Letter not present in puzzle word, so skip remainder of this word
            llFound = .F.
            EXIT
        ENDIF
    ENDFOR

    IF llFound
        * All letters in dictionary word are also present in the puzzle word.
    ***    * Now test for adjacency    TEMP COMMENTED-OUT
    ***    IF IsAdjacent(lcPuzzleMain, Words.cWord)   TEMP COMMENTED-OUT
            INSERT INTO csrSolution (cWord) VALUES (Words.cWord)
    ***    ENDIF   TEMP COMMENTED-OUT
    ENDIF

ENDSCAN

* Remove duplicates from the solution
SELECT distinct * FROM csrSolution INTO CURSOR csrSolution

* We now have all the valid results in a cursor, which we can copy
* to permanent table or a text file, or use as the source
* for a report.

In order to take account of the navigation rules, I then added a function to test pairs of letters for adjacency. If a word from the result set fails this test, it is discarded. So, now un-comment the text flagged as TEMP COMMENTED-OUT, then add this function:

FUNCTION IsAdjacent
LPARAMETERS tcPuzzle, tcTestWord
* Returns true if each pair of letters in the test word corresponds
* to an adjacent pair of letters in the puzzle word.

LOCAL lnI, lnJ, lnTestLen, llMatch, lcLeft, lcRight

tcPuzzle = UPPER(ALLTRIM(tcPuzzle))
tcTestWord = UPPER(ALLTRIM(tcTestWord))

* Copy letters of puzzle word to an array; this is done purely to
* simplify the syntax of the code that follows.
LOCAL ARRAY laP(9)
FOR lnI = 1 TO 9
    laP(lnI) = SUBSTR(tcPuzzle, lnI, 1)
ENDFOR

lnTestLen = LEN(tcTestWord)

llMatch = .T.
FOR lnI = 1 TO lnTestLen - 1
    * For each consecutive pair of letters in the test word
    lcLeft = SUBSTR(tcTestWord, lnI, 1)	&& first letter of pair
    lcRight = SUBSTR(tcTestWord, lnI+1, 1)	 && second letter of pair
    FOR lnJ = 1 TO OCCURS(lcLeft, tcPuzzle)
        * For each occurrence of the first letter of the pair within the
        * puzzle, compare the second letter of the pair with each of
        * the adjacent cells. To understand this, it helps to think of the
        * puzzle as a 3 x 3 grid, with the cells numbered row by row. So
        * the letter in cell 1, for example, is being compared with those in
        * cells 2, 4 and 5.
        lnPos = AT(lcLeft, tcPuzzle, lnJ)
        llMatch = ICASE( ;
            lnPos = 1, INLIST(lcRight, laP(2), laP(4), laP(5)), ;
            lnPos = 2, INLIST(lcRight, laP(1), laP(3), laP(4), laP(5), laP(6)), ;
            lnPos = 3, INLIST(lcRight, laP(2), laP(5), laP(6)), ;
            lnPos = 4, INLIST(lcRight, laP(1), laP(2), laP(5), laP(7), laP(8)), ;
            lnPos = 5, INLIST(lcRight, laP(1), laP(2), laP(3), laP(4), laP(6), laP(7), laP(8), laP(9)), ;
            lnPos = 6, INLIST(lcRight, laP(2), laP(3), laP(5), laP(8), laP(9)), ;
            lnPos = 7, INLIST(lcRight, laP(4), laP(5), laP(8)), ;
            lnPos = 8, INLIST(lcRight, laP(4), laP(5), laP(6), laP(7), laP(9)), ;
            lnPos = 9, INLIST(lcRight, laP(5), laP(6), laP(8)))
        IF llMatch
            * The second letter of the pair matches an adjacent cell, so skip any
            * further occurrences of the first letter within the puzzle.
            EXIT
        ENDIF
    ENDFOR

    IF NOT llMatch
        * No match in the current pair of letters, so skip any further pairs.
        EXIT
    ENDIF

ENDFOR

RETURN llMatch

ENDFUNC

It's not the most elegant code I have ever written, but I hope it makes sense.

Mike

__________________________________
Mike Lewis (Edinburgh, Scotland)

Visual FoxPro articles, tips and downloads

 

[strongm]

>But I'm not quite there yet.

Nor me. I am at about the same place as you. I have a fairly simple funbction called Walkable that verifies if a word can be walked, but currently does not handle multiple letter occurrences. But only because I am being dumb ...

 

[strongm]

Ok, got it! Now just need to clean up the code and optimise ...

 

[Mike Lewis]

currently does not handle multiple letter occurrences. But only because I am being dumb ...

No you're not. It turns out to be harder than you probably thought.

Ok, got it! Now just need to clean up the code and optimise ...

Looking forward to seeing the results. I've also got an idea how to solve the duplicate-letter problem. What I lack right now is the time to do anything about it.

Mike

__________________________________
Mike Lewis (Edinburgh, Scotland)

Visual FoxPro articles, tips and downloads

 

[Chris Miller]

Since the letter position in the 3x3 grid plays a role, I think my suggestion to first work with numbers 1 to 9 and then replace them with the letter at that position would help to figure out whether a letter that's twice in the grid works at the place it is.

I based my try on an idea for a python graph class, which includes a "find_all_paths" method:

https://www.python-course.eu/graphs_python.php

And used that in a Jypiter notebook online:

https://hub.gke2.mybinder.org/user/ipython-ipython-in-depth-kh6h85fi/notebooks/binder/pygraph3.ipynb

Which gives about 10000 paths.

Now it becomes a query finding the numbers translated to the words in the word list.


Chriss

 

[Chris Miller]

Sorry, sharing that Jypiter notebook cannot be shared that way, but here's the python code outputting the ~10000 paths:

g = { "1" : {"2", "4", "5"},
      "2" : {"1", "3", "4", "5", "6"},
      "3" : {"2", "5", "6"},
      "4" : {"1", "2", "5", "7", "8"},
      "5" : {"1", "2", "3", "4", "6", "7", "8", "9"},
      "6" : {"2", "3", "5", "8", "9"},
      "7" : {"4", "5", "8"},
      "8" : {"4", "5", "6", "7", "9"},
      "9" : {"8", "5", "6"}
    }


graph = Graph(g)

allnodes = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
for startnode in allnodes:
    for endnode in allnodes:
        paths = graph.find_all_paths(startnode, endnode)
        for path in paths:
            print (path)

Once I had the path list I created data with path and path (digits) translated to wordcandidates. Included english3.txt as table of word and then let SQL do it:

Select wordcandidates.* From wordcandidates Inner Join words On wordcandidates.Word = words.Word

wordcandidates has path, word (well, candidate word).

Chriss

 

[Chris Miller]

And from that path list you can deduce the words (including their path on the numpad):

Spoiler

84236 acari
247 act
847 act
2478 acta
84753 actor
24753 actor
86 ai
26 ai
268 aia
862 aia
863 air
263 air
21 al
25 ao
85 ao
23 ar
2368 aria
23657 ariot
87 at
8754 atoc
4 c
48 ca
42 ca
42635 cairo
48635 cairo
42153 calor
423 car
4235 caro
42351 carol
487 cat
4875 cato
41263 clair
41235 claro
4157 clot
45 co
4521 coal
4587 coat
456 coi
4569 coif
4563 coir
451 col
4512 cola
453 cor
4532 cora
45321 coral
457 cot
9 f
98 fa
9847 fact
98475 facto
984753 factor
984753621factorial
9863 fair
987 fat
96 fi
9623 fiar
9687 fiat
963 fir
95 fo
9521 foal
95421 focal
956 foi
953 for
9532 fora
6 i
69 if
65 io
6578 iota
632 ira
12 la
124 lac
1263 lair
125 lao
123 lar
123687 lariat
14 lc
15 lo
1589 loaf
1563 loir
153 lor
157 lot
1578 lota
5 o
589 oaf
523 oar
587 oat
548 oca
542 oca
5478 octa
59 of
56 oi
53 or
532 ora
5321 oral
3 r
32 ra
324 rac
3248 raca
326 rai
36 ri
368 ria
362 ria
3621 rial
365 rio
3657 riot
35 ro
354 roc
357 rot
3578 rota
7 t
78 ta
784 tac
7845 taco
78962 tafia
786 tai
78632 taira
785 tao
75 to
751 tol
7512 tola
753 tor
7536 tori

Notice some paths result in the same word.

Chriss

 

[strongm]

Found a teeny bug in mine. Just working on the fix. My code has some similarities to Chriss's in that it usilises numeric paths. The version I have got working deals with repeated letters (as that is not an actual issue with the number ptahs), and as a side effect also doesn't provide duplicate words. In essence:

1. Generate all walkable paths, and represent as numeric strings
2. Use regexp similar to initial puzzle to find all unique 1 - 9 letter words that only use letters from the puzzles word
3. Don't worry that these words are not anagrams of the puzzle word* (e.g. aaa), just check each one against the walkable paths. If there is a match, then we have a legit word


*This means that the letter sorting I mentioned in a previous post is no longer required

 

[strongm]

So, nowhere near as succint as feherke's solution:

[blue]Option Explicit

Public CandidatePath() As String
Dim p As Long

Public Const legitsteps = "12 15 14 21 23 24 25 26 32 35 36 41 42 45 47 48 51 52 53 54 56 57 58 59 62 63 65 68 69 74 75 78 84 85 86 87 89 96 95 98"

[COLOR=green]' Kick it all off ...[/color]
Public Sub DoIt()
    Puzzle "LARCOITAF"
End Sub

Public Sub Puzzle(source As String)
    Dim re As RegExp
    Dim mymatches As MatchCollection
    Dim fso As New FileSystemObject
    Dim lp As Long
    Dim item As Variant
    Dim LegitResults  As New Collection
    
    source = LCase(source)
    
    Permutations [COLOR=green]' Generate array containing all legitimate candidate paths (permutationss) of the puzzle[/color]

    [COLOR=green]' Regexp brute force to get all words that only contain letters from the puzzle word[/color]
    Set re = New RegExp
    With re
        .pattern = "^([" & source & "]+)$"
        .MultiLine = True
        .Global = True
        Set mymatches = .Execute(fso.OpenTextFile("d:\downloads\english3.txt", ForReading).ReadAll)
    End With

   [COLOR=green] ' Originally had a routine hear to prune the word list so that it only contained anagramns and puzzle string (and puzzle substrings).
    ' However this is effectively dealt with by looking for legitimate paths, so we can subsume this functionality into our
    ' path walking verification[/color]

    
    [COLOR=green]' Check word  fits parameters of puzzle (3 to 9 chars) and is walkable, and add to legitresults if so[/color]
    For lp = 0 To mymatches.Count - 1
        If Len(mymatches(lp)) > 2 And Len(mymatches(lp)) <= Len(source) Then
            If NewWalkable(mymatches(lp), source) Then
                LegitResults.Add mymatches(lp), mymatches(lp)
            End If
        End If
    Next

    [COLOR=green]' Show results in immediate window[/color]
    For lp = 3 To 9
    Debug.Print
        Debug.Print lp; " ";
        For Each item In LegitResults
            If Len(item) = lp Then Debug.Print item; " ";
        Next
    Next
End Sub


[COLOR=green]' Initiate building walkable permutations of the puzzle grid
' hacked together recursion. Not optimal ...[/color]
Sub Permutations()
    ReDim CandidatePath(0)
    p = 0
    RecursePerms "", "123456789"
End Sub

[COLOR=green]' This does the recursion heavy lifting[/color]
Sub RecursePerms(c00, c01)
    Dim pathlen As Long
    Dim lp As Long
    
    If Len(c01) = 0 Then
        pathlen = Verify(c00 & c01)
        If pathlen Then
            ReDim Preserve CandidatePath(p) As String
            If p <> 0 Then
                If CandidatePath(p - 1) = Left(c00 & c01, pathlen) Then p = p - 1 'Try to avoid replicating subpaths
            End If
            CandidatePath(p) = Left(c00 & c01, pathlen) [COLOR=green]'Add a verified path to our candidate path list[/color]
            p = p + 1
        End If
    Else
        For lp = 1 To Len(c01)
            RecursePerms c00 & Mid(c01, lp, 1), Left(c01, lp - 1) & Right(c01, Len(c01) - lp)
        Next
    End If
End Sub

[COLOR=green]' Is the proposed solution a viable path?[/color]
Public Function Verify(Solution) As Long
    Dim lp As Long
    Dim path As String

    ' Build a path to test
    For lp = 1 To Len(Solution) - 1
        path = path & Mid(Solution, lp, 1) & Mid(Solution, lp + 1, 1) & " "
    Next
    path = Trim(path)
    
    Verify = Len(Solution)
    For lp = 1 To Len(path) Step 3
        If InStr(legitsteps, Mid(path, lp, 2)) = 0 Then
            Verify = (lp \ 3) + 1 [COLOR=green]' This is the point the walk fails, capture how far we were successful[/color]
            Exit For
        End If
    Next
End Function

Public Function NewWalkable(testword As String, Puzzle As String) As Boolean
    Dim lp As Long
    Dim lp2 As Long
    Dim testee As String
    'Dim source As String
     

    For lp = 1 To UBound(CandidatePath)
        'source = CandidatePath(lp)
        testee = ""
        If Len(CandidatePath(lp)) >= Len(testword) Then
            For lp2 = 1 To Len(testword)
                 testee = testee & LCase(Mid(Puzzle, Mid(CandidatePath(lp), lp2, 1), 1))
                 If InStr(testword, testee) <> 1 Then Exit For
            Next
            If testee = testword Then
               NewWalkable = True
               Exit For
            End If
        End If
    Next
End Function[/blue]

 

[strongm]

Reawakaniung this thread temporarily - just interested in the efficiency of Ruby in feherke's solution to the core wordmaze problem. Just curious as to how long it takes to generate all the permutations . For comparison, my recursive VBA routine takes just under 2 seconds which I'd imagine is dramatically slower (but is admittedly far from optimised; could probably be speeded up somewhat if I simply switched to byte arrays rather than using strings)- but just interested to see the scale of the difference.

 

[Mike Lewis]

I can't speak for Feherke's Ruby solution, but my brute-force Visual FoxPro method takes 0.30 seconds to generate all the valid solutions, including saving the results to a cursor but excluding the time taken to display them on the screen.

A quick update. My program is now fully working, in that it correctly identifies all the solutions. But it still has one fault: it gives false positives in cases where any letter appears more than once in the puzzle. I still have to weed these out by hand. I think I found a way of avoiding that, and have started to amend the code accordingly, but I got side-stepped by some real work (very annoying) and have had to put it on one side for the moment. I want to get back to it as soon as I can.

Mike

__________________________________
Mike Lewis (Edinburgh, Scotland)

Visual FoxPro articles, tips and downloads

 

[Chris Miller]

Why just Ruby?

The Jypiter Python binder I used earlier is already lost and a new binder session I used also already expired. But you can still see it measured ca. 27 ms for finding all paths (without printing them).

I don't know the specs of the server running online, I guess it's having more resources than a usual desktop and without that a timing is less informative. I found it a bit irritating that Python still has no graph implementation, it has dictionaries, sets and the nice concept or arbitrary long integers. But you see you can easily find code for anything.

Before I hijack this as a thread about favorite or most useful programming languages: If your question is driven from whether to step up from VBA to anything else: Yes, pretty much anything is faster. But you see from my profile you can be pretty stuck on legacy languages, too, and it's still lucrative, even becomes more lucrative the more developers turn their back and move to other languages and tools.

I would welcome a discussion and though this forum was meant for logic puzzles more than for puzzling questions about what to learn and use, I think this forum could bring together all kinds of programmers, if pointing to a new thread within your usual forums. The only other mentionable forum under the category "Development Methodologies and Architecture" is forum678. Perhaps there should be a new one more general, as OOP also isn't the only standard paradigm anymore.

Maybe also in forum656. It's more general than just about programming, but there's nothing wrong about that, too.




Chriss

 

[feherke]

Hi

Well, the earlier posted solution is painfully slow :

[blue]master #[/blue] time ruby trackword-all-in-maze.rb larcoitaf > /dev/null
0m23.690s

That because [tt]Array#include?[/tt] is quite slow.

But if we store the word list in a [tt]Set[/tt] instead of [tt]Array[/tt], becomes faster :

Spoiler

[pre]
require 'set'

word_maze = ARGV[0]
word_list = File.readlines('english3.txt', chomp: true).to_set

3.upto 9 do |length|
[*0...9].permutation length do |order|
previous = nil
next unless order.all? {|i| next if previous and ((previous / 3 - i / 3).abs > 1 or (previous % 3 - i % 3).abs > 1); previous = i }

word = order.map {|i| word_maze }.join

puts word if word_list.include? word
end
end[/pre]

[blue]master #[/blue] time ruby trackword-all-in-maze.rb larcoitaf > /dev/null 
0m0.810s

Also possible to speed it up by using a single [tt]Array#intersection[/tt] instead of many [tt]Array#include?[/tt], but that way the words with multiple paths are listed only once :

Spoiler

[pre]
word_maze = ARGV[0]
word_list = File.readlines 'english3.txt', chomp: true

candidate_list = []

3.upto 9 do |length|
[*0...9].permutation length do |order|
previous = nil
next unless order.all? {|i| next if previous and ((previous / 3 - i / 3).abs > 1 or (previous % 3 - i % 3).abs > 1); previous = i }

candidate_list << order.map {|i| word_maze }.join
end
end

puts word_list.intersection candidate_list[/pre]

[blue]master #[/blue] time ruby trackword-all-in-maze.rb larcoitaf > /dev/null
0m0.685s

Feherke.
feherke.github.io