How to find list of possible words from a letter matrix Boggle Solver

Question

Lately I have been playing a game on my iPhone called Scramble  Some of you may know this game as Boggle  Essentially  when the game starts you get a matrix of letters like so   F X I E A M L O E W B X A S T U   The goal of the game is to find as many words as you can that can be formed by chaining letters together  You can start with any letter  and all the letters that surround it are fair game  and then once you move on to the next letter  all the letters that surround that letter are fair game  except for any previously used letters  So in the grid above  for example  I could come up with the words LOB  TUX  SEA  FAME  etc  Words must be at least 3 characters  and no more than NxN characters  which would be 16 in this game but can vary in some implementations   While this game is fun and addictive  I am apparently not very good at it and I wanted to cheat a little bit by making a program that would give me the best possible words  the longer the word the more points you get      source  boggled org     I am  unfortunately  not very good with algorithms or their efficiencies and so forth  My first attempt uses a dictionary such as this one   2 3MB  and does a linear search trying to match combinations with dictionary entries  This takes a very long time to find the possible words  and since you only get 2 minutes per round  it is simply not adequate   I am interested to see if any Stackoverflowers can come up with more efficient solutions  I am mostly looking for solutions using the Big 3 Ps  Python  PHP  and Perl  although anything with Java or C   is cool too  since speed is essential   CURRENT SOLUTIONS    Adam Rosenfield  Python   20s   John Fouhy  Python   3s   Kent Fredric  Perl   1s   Darius Bacon  Python   1s   rvarcher  VB NET  live link    1s Paolo Bergantino  PHP  live link    5s   2s locally

User · Answer

My attempt in Java  It takes about 2 s to read file and build trie  and around 50 ms to solve the puzzle   I used the dictionary linked in the question  it has a few words that I didn t know exist in English such as fae  ima   0  main  INFO gineer bogglesolver util Util  - Reading the dictionary 2234  main  INFO gineer bogglesolver util Util  - Finish reading the dictionary 2234  main  INFO gineer bogglesolver Solver  - Found  FAM 2234  main  INFO gineer bogglesolver Solver  - Found  FAME 2234  main  INFO gineer bogglesolver Solver  - Found  FAMBLE 2234  main  INFO gineer bogglesolver Solver  - Found  FAE 2234  main  INFO gineer bogglesolver Solver  - Found  IMA 2234  main  INFO gineer bogglesolver Solver  - Found  ELI 2234  main  INFO gineer bogglesolver Solver  - Found  ELM 2234  main  INFO gineer bogglesolver Solver  - Found  ELB 2234  main  INFO gineer bogglesolver Solver  - Found  AXIL 2234  main  INFO gineer bogglesolver Solver  - Found  AXILE 2234  main  INFO gineer bogglesolver Solver  - Found  AXLE 2234  main  INFO gineer bogglesolver Solver  - Found  AMI 2234  main  INFO gineer bogglesolver Solver  - Found  AMIL 2234  main  INFO gineer bogglesolver Solver  - Found  AMLI 2234  main  INFO gineer bogglesolver Solver  - Found  AME 2234  main  INFO gineer bogglesolver Solver  - Found  AMBLE 2234  main  INFO gineer bogglesolver Solver  - Found  AMBO 2250  main  INFO gineer bogglesolver Solver  - Found  AES 2250  main  INFO gineer bogglesolver Solver  - Found  AWL 2250  main  INFO gineer bogglesolver Solver  - Found  AWE 2250  main  INFO gineer bogglesolver Solver  - Found  AWEST 2250  main  INFO gineer bogglesolver Solver  - Found  AWA 2250  main  INFO gineer bogglesolver Solver  - Found  MIX 2250  main  INFO gineer bogglesolver Solver  - Found  MIL 2250  main  INFO gineer bogglesolver Solver  - Found  MILE 2250  main  INFO gineer bogglesolver Solver  - Found  MILO 2250  main  INFO gineer bogglesolver Solver  - Found  MAX 2250  main  INFO gineer bogglesolver Solver  - Found  MAE 2250  main  INFO gineer bogglesolver Solver  - Found  MAW 2250  main  INFO gineer bogglesolver Solver  - Found  MEW 2250  main  INFO gineer bogglesolver Solver  - Found  MEWL 2250  main  INFO gineer bogglesolver Solver  - Found  MES 2250  main  INFO gineer bogglesolver Solver  - Found  MESA 2250  main  INFO gineer bogglesolver Solver  - Found  MWA 2250  main  INFO gineer bogglesolver Solver  - Found  MWA 2250  main  INFO gineer bogglesolver Solver  - Found  LIE 2250  main  INFO gineer bogglesolver Solver  - Found  LIM 2250  main  INFO gineer bogglesolver Solver  - Found  LIMA 2250  main  INFO gineer bogglesolver Solver  - Found  LIMAX 2250  main  INFO gineer bogglesolver Solver  - Found  LIME 2250  main  INFO gineer bogglesolver Solver  - Found  LIMES 2250  main  INFO gineer bogglesolver Solver  - Found  LIMB 2250  main  INFO gineer bogglesolver Solver  - Found  LIMBO 2250  main  INFO gineer bogglesolver Solver  - Found  LIMBU 2250  main  INFO gineer bogglesolver Solver  - Found  LEI 2250  main  INFO gineer bogglesolver Solver  - Found  LEO 2250  main  INFO gineer bogglesolver Solver  - Found  LOB 2250  main  INFO gineer bogglesolver Solver  - Found  LOX 2250  main  INFO gineer bogglesolver Solver  - Found  OIME 2250  main  INFO gineer bogglesolver Solver  - Found  OIL 2250  main  INFO gineer bogglesolver Solver  - Found  OLE 2250  main  INFO gineer bogglesolver Solver  - Found  OLM 2250  main  INFO gineer bogglesolver Solver  - Found  EMIL 2250  main  INFO gineer bogglesolver Solver  - Found  EMBOLE 2250  main  INFO gineer bogglesolver Solver  - Found  EMBOX 2250  main  INFO gineer bogglesolver Solver  - Found  EAST 2250  main  INFO gineer bogglesolver Solver  - Found  WAF 2250  main  INFO gineer bogglesolver Solver  - Found  WAX 2250  main  INFO gineer bogglesolver Solver  - Found  WAME 2250  main  INFO gineer bogglesolver Solver  - Found  WAMBLE 2250  main  INFO gineer bogglesolver Solver  - Found  WAE 2250  main  INFO gineer bogglesolver Solver  - Found  WEA 2250  main  INFO gineer bogglesolver Solver  - Found  WEAM 2250  main  INFO gineer bogglesolver Solver  - Found  WEM 2250  main  INFO gineer bogglesolver Solver  - Found  WEA 2250  main  INFO gineer bogglesolver Solver  - Found  WES 2250  main  INFO gineer bogglesolver Solver  - Found  WEST 2250  main  INFO gineer bogglesolver Solver  - Found  WAE 2250  main  INFO gineer bogglesolver Solver  - Found  WAS 2250  main  INFO gineer bogglesolver Solver  - Found  WASE 2250  main  INFO gineer bogglesolver Solver  - Found  WAST 2250  main  INFO gineer bogglesolver Solver  - Found  BLEO 2250  main  INFO gineer bogglesolver Solver  - Found  BLO 2250  main  INFO gineer bogglesolver Solver  - Found  BOIL 2250  main  INFO gineer bogglesolver Solver  - Found  BOLE 2250  main  INFO gineer bogglesolver Solver  - Found  BUT 2250  main  INFO gineer bogglesolver Solver  - Found  AES 2250  main  INFO gineer bogglesolver Solver  - Found  AWA 2250  main  INFO gineer bogglesolver Solver  - Found  AWL 2250  main  INFO gineer bogglesolver Solver  - Found  AWE 2250  main  INFO gineer bogglesolver Solver  - Found  AWEST 2250  main  INFO gineer bogglesolver Solver  - Found  ASE 2250  main  INFO gineer bogglesolver Solver  - Found  ASEM 2250  main  INFO gineer bogglesolver Solver  - Found  AST 2250  main  INFO gineer bogglesolver Solver  - Found  SEA 2250  main  INFO gineer bogglesolver Solver  - Found  SEAX 2250  main  INFO gineer bogglesolver Solver  - Found  SEAM 2250  main  INFO gineer bogglesolver Solver  - Found  SEMI 2250  main  INFO gineer bogglesolver Solver  - Found  SEMBLE 2250  main  INFO gineer bogglesolver Solver  - Found  SEW 2250  main  INFO gineer bogglesolver Solver  - Found  SEA 2250  main  INFO gineer bogglesolver Solver  - Found  SWA 2250  main  INFO gineer bogglesolver Solver  - Found  SWAM 2250  main  INFO gineer bogglesolver Solver  - Found  SWAMI 2250  main  INFO gineer bogglesolver Solver  - Found  SWA 2250  main  INFO gineer bogglesolver Solver  - Found  SAW 2250  main  INFO gineer bogglesolver Solver  - Found  SAWT 2250  main  INFO gineer bogglesolver Solver  - Found  STU 2250  main  INFO gineer bogglesolver Solver  - Found  STUB 2250  main  INFO gineer bogglesolver Solver  - Found  TWA 2250  main  INFO gineer bogglesolver Solver  - Found  TWAE 2250  main  INFO gineer bogglesolver Solver  - Found  TWA 2250  main  INFO gineer bogglesolver Solver  - Found  TWAE 2250  main  INFO gineer bogglesolver Solver  - Found  TWAS 2250  main  INFO gineer bogglesolver Solver  - Found  TUB 2250  main  INFO gineer bogglesolver Solver  - Found  TUX   Source code consists of 6 classes   I ll post them below  if this is not the right practice on StackOverflow  please tell me    gineer bogglesolver Main  package gineer bogglesolver   import org apache log4j BasicConfigurator  import org apache log4j Logger   public class Main       private final static Logger logger   Logger getLogger Main class        public static void main String   args                BasicConfigurator configure             Solver solver   new Solver 4                           FXIE                             AMLO                             EWBX                             ASTU            solver solve               gineer bogglesolver Solver  package gineer bogglesolver   import gineer bogglesolver trie Trie  import gineer bogglesolver util Constants  import gineer bogglesolver util Util  import org apache log4j Logger   public class Solver       private char   puzzle      private int maxSize       private boolean   used      private StringBuilder stringSoFar       private boolean     matrix      private Trie trie       private final static Logger logger   Logger getLogger Solver class        public Solver int size  String puzzle                trie   Util getTrie size           matrix   Util connectivityMatrix size            maxSize   size   size          stringSoFar   new StringBuilder maxSize           used   new boolean maxSize            if  puzzle length      maxSize                        this puzzle   puzzle toCharArray                      else                       logger error  The puzzle size does not match the size specified      puzzle length                 this puzzle   puzzle substring 0  maxSize  toCharArray                         public void solve                 for  int i   0  i  lt  maxSize  i                          traverseAt i                        private void traverseAt int origin                stringSoFar append puzzle origin            used origin    true             Check if we have a valid word         if   stringSoFar length    gt   Constants MINIMUM WORD LENGTH   amp  amp   trie containKey stringSoFar toString                            logger info  Found      stringSoFar toString                          Find where to go next         for  int destination   0  destination  lt  maxSize  destination                          if  matrix origin  destination   amp  amp   used destination   amp  amp  trie containPrefix stringSoFar toString     puzzle destination                                  traverseAt destination                                    used origin    false          stringSoFar deleteCharAt stringSoFar length   - 1              gineer bogglesolver trie Node  package gineer bogglesolver trie   import gineer bogglesolver util Constants   class Node       Node   children      boolean isKey       public Node                 isKey   false          children   new Node Constants NUMBER LETTERS IN ALPHABET              public Node boolean key                isKey   key          children   new Node Constants NUMBER LETTERS IN ALPHABET                       Method to insert a string to Node and its children        param key the string to insert  the string is assumed to be uppercase        return true if the node or one of its children is changed  false otherwise             public boolean insert String key                  If the key is empty  this node is a key         if  key length      0                        if  isKey                  return false              else                               isKey   true                  return true                                  else            otherwise  insert in one of its child              int childNodePosition   key charAt 0  - Constants LETTER A              if  children childNodePosition     null                                children childNodePosition    new Node                    children childNodePosition  insert key substring 1                    return true                            else                               return children childNodePosition  insert key substring 1                                                Returns whether key is a valid prefix for certain key in this trie       For example  if key  hello  is in this trie  tests with all prefixes  hel    hell    hello  return true        param prefix the prefix to check       return true if the prefix is valid  false otherwise             public boolean containPrefix String prefix                  If the prefix is empty  return true         if  prefix length      0                        return true                    else            otherwise  check in one of its child             int childNodePosition   prefix charAt 0  - Constants LETTER A              return children childNodePosition     null  amp  amp  children childNodePosition  containPrefix prefix substring 1                                  Returns whether key is a valid key in this trie       For example  if key  hello  is in this trie  tests with all prefixes  hel    hell  return false        param key the key to check       return true if the key is valid  false otherwise             public boolean containKey String key                  If the prefix is empty  return true         if  key length      0                        return isKey                    else            otherwise  check in one of its child             int childNodePosition   key charAt 0  - Constants LETTER A              return children childNodePosition     null  amp  amp  children childNodePosition  containKey key substring 1                         public boolean isKey                 return isKey             public void setKey boolean key                isKey   key            gineer bogglesolver trie Trie  package gineer bogglesolver trie   public class Trie       Node root       public Trie                 this root   new Node                        Method to insert a string to Node and its children        param key the string to insert  the string is assumed to be uppercase        return true if the node or one of its children is changed  false otherwise             public boolean insert String key                return root insert key toUpperCase                         Returns whether key is a valid prefix for certain key in this trie       For example  if key  hello  is in this trie  tests with all prefixes  hel    hell    hello  return true        param prefix the prefix to check       return true if the prefix is valid  false otherwise             public boolean containPrefix String prefix                return root containPrefix prefix toUpperCase                         Returns whether key is a valid key in this trie       For example  if key  hello  is in this trie  tests with all prefixes  hel    hell  return false        param key the key to check       return true if the key is valid  false otherwise             public boolean containKey String key                return root containKey key toUpperCase                 gineer bogglesolver util Constants  package gineer bogglesolver util   public class Constants        public static final int NUMBER LETTERS IN ALPHABET   26      public static final char LETTER A    A       public static final int MINIMUM WORD LENGTH   3      public static final int DEFAULT PUZZLE SIZE   4      gineer bogglesolver util Util  package gineer bogglesolver util   import gineer bogglesolver trie Trie  import org apache log4j Logger   import java io File  import java io FileNotFoundException  import java util Scanner   public class Util       private final static Logger logger   Logger getLogger Util class       private static Trie trie      private static int size   Constants DEFAULT PUZZLE SIZE                Returns the trie built from the dictionary   The size is used to eliminate words that are too long         param size the size of puzzle   The maximum lenght of words in the returned trie is  size   size        return the trie that can be used for puzzle of that size             public static Trie getTrie int size                if   trie    null   amp  amp  size    Util size              return trie           trie   new Trie            Util size   size           logger info  Reading the dictionary            final File file   new File  dictionary txt            try                       Scanner scanner   new Scanner file               final int maxSize   size   size              while  scanner hasNext                                  String line   scanner nextLine   replaceAll      p Alpha                           if  line length    lt   maxSize                      trie insert line                                   catch  FileNotFoundException e                        logger error  Cannot open file   e                      logger info  Finish reading the dictionary            return trie             static boolean   connectivityRow int x  int y  int size                boolean   squares   new boolean size   size           for  int offsetX   -1  offsetX  lt   1  offsetX                          for  int offsetY   -1  offsetY  lt   1  offsetY                                  final int calX   x   offsetX                  final int calY   y   offsetY                  if   calX  gt   0   amp  amp   calX  lt  size   amp  amp   calY  gt   0   amp  amp   calY  lt  size                       squares calY   size   calX    true                                   squares y   size   x    false   the current x  y is false          return squares                      Returns the matrix of connectivity between two points   Point i can go to point j iff matrix i  j  is true      Square  x  y  is equivalent to point  size   y   x    For example  square  1 1  is point 5 in a puzzle of size 4        param size the size of the puzzle       return the connectivity matrix             public static boolean     connectivityMatrix int size                boolean     matrix   new boolean size   size             for  int x   0  x  lt  size  x                          for  int y   0  y  lt  size  y                                  matrix y   size   x    connectivityRow x  y  size                                   return matrix

User · Answer

Here is the solution Using Predefined words in NLTK toolkit  NLTK has nltk corpus package in that we have package called words and it contains more than 2Lakhs English words you can simply use all into your program   Once creating your matrix convert it into a character array and perform this code  import nltk from nltk corpus import words from collections import Counter  def possibleWords input  charSet       for word in input          dict   Counter word          flag   1         for key in dict keys                if key not in charSet                  flag   0         if flag    1 and len word  gt 5   its depends if you want only length more than 5 use this otherwise remove that one               print word    nltk download  words   word list   words words     prints 236736 print len word list   charSet     h    e    l    o    n    v    t   possibleWords word list  charSet    Output   eleven eleventh elevon entente entone ethene ethenol evolve evolvent hellhole helvell hooven letten looten nettle nonene nonent nonlevel notelet novelet novelette novene teenet teethe teevee telethon tellee tenent tentlet theelol toetoe tonlet toothlet tootle tottle vellon velvet velveteen venene vennel venthole voeten volent volvelle volvent voteen   I hope you get it

User · Answer

I realize this question s time has come and gone  but since I was working on a solver myself  and stumbled onto this while googling about  I thought I should post a reference to mine as it seems a bit different from some of the others   I chose to go with a flat array for the game board  and to do recursive hunts from each letter on the board  traversing from valid neighbor to valid neighbor  extending the hunt if the current list of letters if a valid prefix in an index  While traversing the notion of the current word is list of indexes into board  not letters that make up a word  When checking the index  the indexes are translated to letters and the check done   The index is a brute force dictionary that s a bit like a trie  but allows for Pythonic queries of the index  If the words  cat  and  cater  are in the list  you ll get this in the dictionary      d      c     cat   cater          ca     cat   cater          cat     cat   cater          cate     cater          cater     cater           So if the current word is  ca  you know that it is a valid prefix because  ca  in d returns True  so continue the board traversal   And if the current word is  cat  then you know that it is a valid word because it is a valid prefix and  cat  in d  cat   returns True too   If felt like this allowed for some readable code that doesn t seem too slow  Like everyone else the expense in this system is reading building the index  Solving the board is pretty much noise   The code is at http   gist github com 268079  It is intentionally vertical and naive with lots of explicit validity checking because I wanted to understand the problem without crufting it up with a bunch of magic or obscurity

User · Answer

You could split the problem up into two pieces    Some kind of search algorithm that will enumerate possible strings in the grid  A way of testing whether a string is a valid word    Ideally   2  should also include a way of testing whether a string is a prefix of a valid word     this will allow you to prune your search and save a whole heap of time   Adam Rosenfield s Trie is a solution to  2    It s elegant and probably what your algorithms specialist would prefer  but with modern languages and modern computers  we can be a bit lazier   Also  as Kent suggests  we can reduce our dictionary size by discarding words that have letters not present in the grid   Here s some python   def make lookups grid  fn  dict txt          Make set of valid characters      chars   set       for word in grid          chars update word       words   set x strip   for x in open fn  if set x strip     lt   chars      prefixes   set       for w in words          for i in range len w  1               prefixes add w  i        return words  prefixes   Wow  constant-time prefix testing   It takes a couple of seconds to load the dictionary you linked  but only a couple  -   notice that words  lt   prefixes   Now  for part  1   I m inclined to think in terms of graphs   So I ll build a dictionary that looks something like this   graph      x  y  set   x0 y0    x1 y1    x2 y2         i e  graph  x  y   is the set of coordinates that you can reach from position  x  y    I ll also add a dummy node None which will connect to everything   Building it s a bit clumsy  because there s 8 possible positions and you have to do bounds checking   Here s some correspondingly-clumsy python code   def make graph grid       root   None     graph     root set         chardict     root           for i  row in enumerate grid           for j  char in enumerate row               chardict  i  j     char             node    i  j              children   set               graph node    children             graph root  add node              add children node  children  grid       return graph  chardict  def add children node  children  grid       x0  y0   node     for i in  -1 0 1           x   x0   i         if not  0  lt   x  lt  len grid                continue         for j in  -1 0 1               y   y0   j             if not  0  lt   y  lt  len grid 0    or  i    j    0                   continue              children add  x y     This code also builds up a dictionary mapping  x y  to the corresponding character   This lets me turn a list of positions into a word   def to word chardict  pos list       return    join chardict x  for x in pos list    Finally  we do a depth-first search   The basic procedure is    The search arrives at a particular node  Check if the path so far could be part of a word   If not  don t explore this branch any further  Check if the path so far is a word   If so  add to the list of results  Explore all children not part of the path so far    Python   def find words graph  chardict  position  prefix  results  words  prefixes           Arguments        graph    mapping  x y  to set of reachable positions       chardict    mapping  x y  to character       position    current position  x y  -- equals prefix -1        prefix    list of positions in current string       results    set of words found       words    set of valid words in the dictionary       prefixes    set of valid words or prefixes thereof             word   to word chardict  prefix       if word not in prefixes          return      if word in words          results add word       for child in graph position           if child not in prefix              find words graph  chardict  child  prefix  child   results  words  prefixes    Run the code as   grid     fxie    amlo    ewbx    astu   g  c   make graph grid  w  p   make lookups grid  res   set   find words g  c  None      res  w  p    and inspect res to see the answers   Here s a list of words found for your example  sorted by size      a    b    e    f    i    l    m    o    s    t     u    w    x    ae    am    as    aw    ax    bo     bu    ea    el    em    es    fa    ie    io    li     lo    ma    me    mi    oe    ox    sa    se    st     tu    ut    wa    we    xi    aes    ame    ami     ase    ast    awa    awe    awl    blo    but    elb     elm    fae    fam    lei    lie    lim    lob    lox     mae    maw    mew    mil    mix    oil    olm    saw     sea    sew    swa    tub    tux    twa    wae    was     wax    wem    ambo    amil    amli    asem    axil     axle    bleo    boil    bole    east    fame    limb     lime    mesa    mewl    mile    milo    oime    sawt     seam    seax    semi    stub    swam    twae    twas     wame    wase    wast    weam    west    amble    awest     axile    embox    limbo    limes    swami    embole     famble    semble    wamble     The code takes  literally  a couple of seconds to load the dictionary  but the rest is instant on my machine

User · Answer

I know I am really late at the party but I have implemented  as a coding exercise  a boggle solver in several programming languages  C    Java  Go  C   Python  Ruby  JavaScript  Julia  Lua  PHP  Perl  and I thought that someone might be interested in those  so I leave link here  https   github com AmokHuginnsson boggle-solvers

User · Answer

The fastest solution you re going to get will probably involve storing your dictionary in a trie   Then  create a queue of triplets  x  y  s   where each element in the queue corresponds to a prefix s of a word which can be spelled in the grid  ending at location  x  y    Initialize the queue with N x N elements  where N is the size of your grid   one element for each square in the grid   Then  the algorithm proceeds as follows    While the queue is not empty    Dequeue a triple  x  y  s    For each square  x   y   with letter c adjacent to  x  y       If s c is a word  output s c     If s c is a prefix of a word  insert  x   y   s c  into the queue   If you store your dictionary in a trie  testing if s c is a word or a prefix of a word can be done in constant time  provided you also keep some extra metadata in each queue datum  such as a pointer to the current node in the trie   so the running time of this algorithm is O number of words that can be spelled     Edit  Here s an implementation in Python that I just coded up      usr bin python  class TrieNode      def   init   self  parent  value           self parent   parent         self children    None    26         self isWord   False         if parent is not None              parent children ord value  - 97    self  def MakeTrie dictfile       dict   open dictfile      root   TrieNode None          for word in dict          curNode   root         for letter in word lower                if 97  lt   ord letter   lt  123                  nextNode   curNode children ord letter  - 97                  if nextNode is None                      nextNode   TrieNode curNode  letter                  curNode   nextNode         curNode isWord   True     return root  def BoggleWords grid  dict       rows   len grid      cols   len grid 0       queue          words          for y in range cols           for x in range rows               c   grid y  x              node   dict children ord c  - 97              if node is not None                  queue append  x  y  c  node       while queue          x  y  s  node   queue 0          del queue 0          for dx  dy in   1  0    1  -1    0  -1    -1  -1    -1  0    -1  1    0  1    1  1                x2  y2   x   dx  y   dy             if 0  lt   x2  lt  cols and 0  lt   y2  lt  rows                  s2   s   grid y2  x2                  node2   node children ord grid y2  x2   - 97                  if node2 is not None                      if node2 isWord                          words append s2                      queue append  x2  y2  s2  node2        return words   Example usage   d   MakeTrie   usr share dict words   print BoggleWords   fxie   amlo   ewbx   astu    d     Output        fa    xi    ie    io    el    am    ax    ae    aw    mi    ma    me    lo    li    oe    ox    em    ea    ea    es    wa    we    wa    bo    bu    as    aw    ae    st    se    sa    tu    ut    fam    fae    imi    eli    elm    elb    ami    ama    ame    aes    awl    awa    awe    awa    mix    mim    mil    mam    max    mae    maw    mew    mem    mes    lob    lox    lei    leo    lie    lim    oil    olm    ewe    eme    wax    waf    wae    waw    wem    wea    wea    was    waw    wae    bob    blo    bub    but    ast    ase    asa    awl    awa    awe    awa    aes    swa    swa    sew    sea    sea    saw    tux    tub    tut    twa    twa    tst    utu    fama    fame    ixil    imam    amli    amil    ambo    axil    axle    mimi    mima    mime    milo    mile    mewl    mese    mesa    lolo    lobo    lima    lime    limb    lile    oime    oleo    olio    oboe    obol    emim    emil    east    ease    wame    wawa    wawa    weam    west    wese    wast    wase    wawa    wawa    boil    bolo    bole    bobo    blob    bleo    bubo    asem    stub    stut    swam    semi    seme    seam    seax    sasa    sawt    tutu    tuts    twae    twas    twae    ilima    amble    axile    awest    mamie    mambo    maxim    mease    mesem    limax    limes    limbo    limbu    obole    emesa    embox    awest    swami    famble    mimble    maxima    embolo    embole    wamble    semese    semble    sawbwa    sawbwa     Notes  This program doesn t output 1-letter words  or filter by word length at all   That s easy to add but not really relevant to the problem   It also outputs some words multiple times if they can be spelled in multiple ways   If a given word can be spelled in many different ways  worst case  every letter in the grid is the same  e g   A   and a word like  aaaaaaaaaa  is in your dictionary   then the running time will get horribly exponential   Filtering out duplicates and sorting is trivial to due after the algorithm has finished

User · Answer

import java util HashSet  import java util Set           author Sujeet Kumar  mrsujeet gmail com  It prints out all strings that can            be formed by moving left  right  up  down  or diagonally and exist in            a given dictionary   without repeating any cell  Assumes words are            comprised of lower case letters  Currently prints words as many times            as they appear  not just once         public class BoggleGame         A sample 4X4 board 2D matrix      private static char     board        s    a    s    g                                          a    u    t    h                                           r    t    j    e                                          k    a    h    e           A sample dictionary which contains unique collection of words    private static Set lt String gt  dictionary   new HashSet lt String gt      private static boolean     visited   new boolean board length  board 0  length    public static void main String   arg        dictionary add  sujeet        dictionary add  sarthak        findWords           show all words  starting from each possible starting place private static void findWords         for  int i   0  i  lt  board length  i              for  int j   0  j  lt  board i  length  j                  StringBuffer buffer   new StringBuffer                dfs i  j  buffer                           run depth first search starting at cell  i  j  private static void dfs int i  int j  StringBuffer buffer                  base case  just return in recursive call when index goes out of the        size of matrix dimension             if  i  lt  0    j  lt  0    i  gt  board length - 1    j  gt  board i  length - 1            return                       base case  to return in recursive call when given cell is already        visited in a given string of word             if  visited i  j     true       can t visit a cell more than once         return                not to allow a cell to reuse     visited i  j    true          combining cell character with other visited cells characters to form        word a potential word which may exist in dictionary     buffer append board i  j            found a word in dictionary  Print it      if  dictionary contains buffer toString               System out println buffer                        consider all neighbors For a given cell considering all adjacent        cells in horizontal  vertical and diagonal direction             for  int k   i - 1  k  lt   i   1  k              for  int l   j - 1  l  lt   j   1  l                  dfs k  l  buffer                         buffer deleteCharAt buffer length   - 1       visited i  j    false

User · Answer

Not interested in VB     I couldn t resist  I ve solved this differently than many of the solutions presented here   My times are    Loading the dictionary and word prefixes into a hashtable   5 to 1 seconds  Finding the words  averaging under 10 milliseconds    EDIT  Dictionary load times on the web host server are running about 1 to 1 5 seconds longer than my home computer   I don t know how badly the times will deteriorate with a load on the server   I wrote my solution as a web page in  Net  myvrad com boggle  I m using the dictionary referenced in the original question   Letters are not reused in a word  Only words 3 characters or longer are found   I m using a hashtable of all unique word prefixes and words instead of a trie  I didn t know about trie s so I learned something there  The idea of creating a list of prefixes of words in addition to the complete words is what finally got my times down to a respectable number   Read the code comments for additional details   Here s the code   Imports System Collections Generic Imports System IO  Partial Class boggle Default       Bob Archer  4 15 2009       To avoid using a 2 dimensional array in VB I m not using typical X Y      coordinate iteration to find paths             I have locked the code into a 4 by 4 grid laid out like so        abcd       efgh       ijkl       mnop             To find paths the code starts with a letter from a to p then      explores the paths available around it  If a neighboring letter      already exists in the path then we don t go there             Neighboring letters  grid points  are hard coded into      a Generic Dictionary below          Paths is a list of only valid Paths found        If a word prefix or word is not found the path is not      added and extending that path is terminated      Dim Paths As New Generic List Of String        NeighborsOf  The keys are the letters a to p       The value is a string of letters representing neighboring letters       The string of neighboring letters is split and iterated later      Dim NeigborsOf As New Generic Dictionary Of String  String        BoggleLetters  The keys are mapped to the lettered grid of a to p       The values are what the user inputs on the page      Dim BoggleLetters As New Generic Dictionary Of String  String        Used to store last postition of path  This will be a letter      from a to p      Dim LastPositionOfPath As String            I found a HashTable was by far faster than a Generic Dictionary        - about 10 times faster  This stores prefixes of words and words       I determined 792773 was the number of words and unique prefixes that      will be generated from the dictionary file  This is a max number and      the final hashtable will not have that many      Dim HashTableOfPrefixesAndWords As New Hashtable 792773        Stores words that are found      Dim FoundWords As New Generic List Of String        Just to validate what the user enters in the grid      Dim ErrorFoundWithSubmittedLetters As Boolean   False      Public Sub BuildAndTestPathsAndFindWords ByVal ThisPath As String           Word is the word correlating to the ThisPath parameter           This path would be a series of letters from a to p          Dim Word As String                The path is iterated through and a word based on the actual          letters in the Boggle grid is assembled          For i As Integer   0 To ThisPath Length - 1             Word    Me BoggleLetters ThisPath Substring i  1           Next           If my hashtable of word prefixes and words doesn t contain this Word          Then this isn t a word and any further extension of ThisPath will not          yield any words either  So exit sub to terminate exploring this path          If Not HashTableOfPrefixesAndWords ContainsKey Word  Then Exit Sub           The value of my hashtable is a boolean representing if the key if a word  true  or          just a prefix  false   If true and at least 3 letters long then yay  word found          If HashTableOfPrefixesAndWords Word  AndAlso Word Length  gt  2 Then Me FoundWords Add Word            If my List of Paths doesn t contain ThisPath then add it           Remember only valid paths will make it this far  Paths not found          in the HashTableOfPrefixesAndWords cause this sub to exit above          If Not Paths Contains ThisPath  Then Paths Add ThisPath            Examine the last letter of ThisPath  We are looking to extend the path          to our neighboring letters if any are still available          LastPositionOfPath   ThisPath Substring ThisPath Length - 1  1            Loop through my list of neighboring letters  representing grid points           For Each Neighbor As String In Me NeigborsOf LastPositionOfPath  ToCharArray                If I find a neighboring grid point that I haven t already used              in ThisPath then extend ThisPath and feed the new path into              this recursive function   see recursive               If Not ThisPath Contains Neighbor  Then Me BuildAndTestPathsAndFindWords ThisPath  amp  Neighbor          Next     End Sub      Protected Sub ButtonBoggle Click ByVal sender As Object  ByVal e As System EventArgs  Handles ButtonBoggle Click           User has entered the 16 letters and clicked the go button            Set up my Generic Dictionary of grid points  I m using letters a to p -          not an x y grid system   The values are neighboring points          NeigborsOf Add  a    bfe           NeigborsOf Add  b    cgfea           NeigborsOf Add  c    dhgfb           NeigborsOf Add  d    hgc           NeigborsOf Add  e    abfji           NeigborsOf Add  f    abcgkjie           NeigborsOf Add  g    bcdhlkjf           NeigborsOf Add  h    cdlkg           NeigborsOf Add  i    efjnm           NeigborsOf Add  j    efgkonmi           NeigborsOf Add  k    fghlponj           NeigborsOf Add  l    ghpok           NeigborsOf Add  m    ijn           NeigborsOf Add  n    ijkom           NeigborsOf Add  o    jklpn           NeigborsOf Add  p    klo             Retrieve letters the user entered          BoggleLetters Add  a   Me TextBox1 Text ToLower Trim            BoggleLetters Add  b   Me TextBox2 Text ToLower Trim            BoggleLetters Add  c   Me TextBox3 Text ToLower Trim            BoggleLetters Add  d   Me TextBox4 Text ToLower Trim            BoggleLetters Add  e   Me TextBox5 Text ToLower Trim            BoggleLetters Add  f   Me TextBox6 Text ToLower Trim            BoggleLetters Add  g   Me TextBox7 Text ToLower Trim            BoggleLetters Add  h   Me TextBox8 Text ToLower Trim            BoggleLetters Add  i   Me TextBox9 Text ToLower Trim            BoggleLetters Add  j   Me TextBox10 Text ToLower Trim            BoggleLetters Add  k   Me TextBox11 Text ToLower Trim            BoggleLetters Add  l   Me TextBox12 Text ToLower Trim            BoggleLetters Add  m   Me TextBox13 Text ToLower Trim            BoggleLetters Add  n   Me TextBox14 Text ToLower Trim            BoggleLetters Add  o   Me TextBox15 Text ToLower Trim            BoggleLetters Add  p   Me TextBox16 Text ToLower Trim              Validate user entered something with a length of 1 for all 16 textboxes          For Each S As String In BoggleLetters Keys             If BoggleLetters S  Length  lt  gt  1 Then                 ErrorFoundWithSubmittedLetters   True                 Exit For             End If         Next           If input is not valid then            If ErrorFoundWithSubmittedLetters Then              Present error message          Else              Else assume we have 16 letters to work with and start finding words              Dim SB As New StringBuilder              Dim Time As String   String Format   0   1   2   3    Date Now Hour ToString    Date Now Minute ToString    Date Now Second ToString    Date Now Millisecond ToString                 Dim NumOfLetters As Integer   0             Dim Word As String                  Dim TempWord As String                  Dim Letter As String                  Dim fr As StreamReader   Nothing             fr   New System IO StreamReader HttpContext Current Request MapPath    boggle dic txt                  First fill my hashtable with word prefixes and words               HashTable PrefixOrWordString  BooleanTrueIfWordFalseIfPrefix              While fr Peek  lt  gt  -1                 Word   fr ReadLine Trim                   TempWord                      For i As Integer   0 To Word Length - 1                     Letter   Word Substring i  1                       This optimization helped quite a bit  Words in the dictionary that begin                      with letters that the user did not enter in the grid shouldn t go in my hashtable                                             I realize most of the solutions went with a Trie  I d never heard of that before                       which is one of the neat things about SO  seeing how others approach challenges                      and learning some best practices                                             However  I didn t code a Trie in my solution  I just have a hashtable with                       all words in the dicitonary file and all possible prefixes for those words                       A Trie might be faster but I m not coding it now  I m getting good times with this                      If i   0 AndAlso Not BoggleLetters ContainsValue Letter  Then Continue While                     TempWord    Letter                     If Not HashTableOfPrefixesAndWords ContainsKey TempWord  Then                         HashTableOfPrefixesAndWords Add TempWord  TempWord   Word                      End If                 Next             End While              SB Append  Number of Word Prefixes and Words in Hashtable     amp  HashTableOfPrefixesAndWords Count ToString                SB Append   lt br   gt                 SB Append  Loading Dictionary     amp  Time  amp    -    amp  String Format   0   1   2   3    Date Now Hour ToString    Date Now Minute ToString    Date Now Second ToString    Date Now Millisecond ToString                 SB Append   lt br   gt                 Time   String Format   0   1   2   3    Date Now Hour ToString    Date Now Minute ToString    Date Now Second ToString    Date Now Millisecond ToString                  This starts a path at each point on the grid an builds a path until               the string of letters correlating to the path is not found in the hashtable              of word prefixes and words              Me BuildAndTestPathsAndFindWords  a               Me BuildAndTestPathsAndFindWords  b               Me BuildAndTestPathsAndFindWords  c               Me BuildAndTestPathsAndFindWords  d               Me BuildAndTestPathsAndFindWords  e               Me BuildAndTestPathsAndFindWords  f               Me BuildAndTestPathsAndFindWords  g               Me BuildAndTestPathsAndFindWords  h               Me BuildAndTestPathsAndFindWords  i               Me BuildAndTestPathsAndFindWords  j               Me BuildAndTestPathsAndFindWords  k               Me BuildAndTestPathsAndFindWords  l               Me BuildAndTestPathsAndFindWords  m               Me BuildAndTestPathsAndFindWords  n               Me BuildAndTestPathsAndFindWords  o               Me BuildAndTestPathsAndFindWords  p                SB Append  Finding Words     amp  Time  amp    -    amp  String Format   0   1   2   3    Date Now Hour ToString    Date Now Minute ToString    Date Now Second ToString    Date Now Millisecond ToString                 SB Append   lt br   gt                 SB Append  Num of words found     amp  FoundWords Count ToString                SB Append   lt br   gt                SB Append   lt br   gt                 FoundWords Sort               SB Append String Join   lt br   gt    FoundWords ToArray                   Output results              Me LiteralBoggleResults Text   SB ToString               Me PanelBoggleResults Visible   True          End If      End Sub  End Class

User · Answer

So I wanted to add another PHP way of solving this  since everyone loves PHP  There s a little bit of refactoring I would like to do  like using a regexpression match against the dictionary file  but right now I m just loading the entire dictionary file into a wordList   I did this using a linked list idea  Each Node has a character value  a location value  and a next pointer   The location value is how I found out if two nodes are connected   1     2     3     4 11    12    13    14 21    22    23    24 31    32    33    34   So using that grid  I know two nodes are connected if the first node s location equals the second nodes location   - 1 for the same row    - 9  10  11 for the row above and below   I use recursion for the main search  It takes a word off the wordList  finds all the possible starting points  and then recursively finds the next possible connection  keeping in mind that it can t go to a location it s already using  which is why I add  notInLoc    Anyway  I know it needs some refactoring  and would love to hear thoughts on how to make it cleaner  but it produces the correct results based on the dictionary file I m using  Depending on the number of vowels and combinations on the board  it takes about 3 to 6 seconds  I know that once I preg match the dictionary results  that will reduce significantly    lt  php     ini set  xdebug var display max depth   20       ini set  xdebug var display max children   1024       ini set  xdebug var display max data   1024        class Node           var  loc           function   construct  value                 this- gt value    value               next   null                       class Boggle           var  root          var  locList   array  1  2  3  4  11  12  13  14  21  22  23  24  31  32  33  34           var  wordList               var  foundWords                function   construct  board                   Takes in a board string and creates all the nodes              node   new Node  board 0                 node- gt loc    this- gt locList 0                this- gt root    node              for   i   1   i  lt  strlen  board    i                           node- gt next   new Node  board  i                         node- gt next- gt loc    this- gt locList  i                        node    node- gt next                               Load in a dictionary file                Use regexp to elimate all the words that could never appear and load the                 rest of the words into wordList              handle   fopen  dict txt    r                if   handle                    while    line   fgets  handle       false                           process the line read                       line   trim  line                       if  strlen  line   gt  2                             this- gt wordList     trim  line                                                           fclose  handle                 else                      error opening the file                  echo  Problem with the file                                      function isConnected  node1   node2               Determines if 2 nodes are connected on the boggle board              return    node1- gt loc     node2- gt loc   1       node1- gt loc     node2- gt loc - 1                      node1- gt loc     node2- gt loc - 9       node1- gt loc     node2- gt loc - 10       node1- gt loc     node2- gt loc - 11                      node1- gt loc     node2- gt loc   9       node1- gt loc     node2- gt loc   10       node1- gt loc     node2- gt loc   11     true   false                      function find  value   notInLoc                        Returns a node with the value that isn t in a location              current    this- gt root              while  current                    if   current- gt value     value  amp  amp   in array  current- gt loc   notInLoc                         return  current                                    if  isset  current- gt next                          current    current- gt next                    else                       break                                              return false                     function findAll  value                   Returns an array of nodes with a specific value              current    this- gt root               foundNodes                   while   current                    if   current- gt value     value                         foundNodes      current                                    if  isset  current- gt next                          current    current- gt next                    else                       break                                              return  empty  foundNodes     false    foundNodes                     function findAllConnectedTo  node   value   notInLoc                        Returns an array of nodes that are connected to a specific node and                 contain a specific value and are not in a certain location              nodeList    this- gt findAll  value                newList                   if   nodeList                    foreach   nodeList as  node2                        if   in array  node2- gt loc   notInLoc   amp  amp   this- gt isConnected  node   node2                              newList      node2                                                                    return  empty  newList     false    newList                       function inner  word   list   i   0   notInLoc                      i                foreach  list as  node                     notInLoc      node- gt loc                  if   list2    this- gt findAllConnectedTo  node   word  i    notInLoc                         if   i     strlen  word  - 1                             return true                        else                           return  this- gt inner  word   list2   i   notInLoc                                                                     return false                     function findWord  word                if   list    this- gt findAll  word 0                      return  this- gt inner  word   list                             return false                     function findAllWords                 foreach  this- gt wordList as  word                    if   this- gt findWord  word                          this- gt foundWords      word                                                     function displayBoard                  current    this- gt root              for   i 0   i  lt  4   i                      echo  current- gt value          current- gt next- gt value          current- gt next- gt next- gt value          current- gt next- gt next- gt next- gt value     lt br   gt                    if   i  lt  3                         current    current- gt next- gt next- gt next- gt next                                                        function randomBoardString             return substr str shuffle str repeat  abcdefghijklmnopqrstuvwxyz   16    0  16               myBoggle   new Boggle randomBoardString          myBoggle- gt displayBoard         x   microtime true        myBoggle- gt findAllWords         y   microtime true       echo   y- x       var dump  myBoggle- gt foundWords          gt

User · Answer

I solved this in c  It takes around 48 ms to run on my machine  with around 98  of the time spent loading the dictionary from disk and creating the trie   The dictionary is  usr share dict american-english which has 62886 words   Source code

User · Answer

Just for fun  I implemented one in bash   It is not super fast  but reasonable    http   dev xkyle com bashboggle

User · Answer

This is the solution I came up with for solving the boggle problem  I guess it is the most  pythonic  way to do things   from itertools import combinations from itertools import izip from math import fabs  def isAllowedStep current step length doubleLength                 for step    length -1 not to be 0   gt  trivial solutions are not allowed     return length  gt  1 and              current   step  lt  doubleLength and current - step  gt  0 and                step    1 or step    -1 or step  lt   length 1 or step  gt   length - 1   def getPairwiseList someList       iterableList   iter someList      return izip iterableList  iterableList   def isCombinationAllowed combination length doubleLength        for  first second  in  getPairwiseList combination              firstCoordinate   first            secondCoordinate   second         if not isAllowedStep firstCoordinate  fabs secondCoordinate-firstCoordinate  length doubleLength               return False     return True  def extractSolution combinations       return     join  x 0  for x in combinationTuple   for combinationTuple in combinations    length   4 text   tuple    join  fxie amlo ewbx astu  split     textIndices   tuple range len text    coordinates   zip text textIndices   validCombinations    combination for combination in combinations coordinates length  if isCombinationAllowed combination length length length   solution   extractSolution validCombinations    This part I kindly advise you not to use for all the possible matches but it would actually provide a possibility to check if the words you have generated actually constitue valid words   import mechanize def checkWord word       url    https   en oxforddictionaries com search filter dictionary amp query   word     br   mechanize Browser       br set handle robots False      response   br open url      text   response read       return  no exact matches   not in text lower    print  valid for valid in solution  10  if checkWord valid

User · Answer

Does your search algorithm continually decrease the word list as your search continues   For instance  in the search above there are only 13 letters that your words can start with  effectively reducing to half as many starting letters    As you add more letter permutations it would further decrease the available word sets decreasing the searching necessary   I d start there

User · Answer

I have implemented a solution in OCaml  It pre-compiles a dictionary as a trie  and uses two-letter sequence frequencies to eliminate edges that could never appear in a word to further speed up processing    It solves your example board in 0 35ms  with an additional 6ms start-up time which is mostly related to loading the trie into memory     The solutions found      swami    emile    limbs    limbo    limes    amble    tubs    stub     swam    semi    seam    awes    buts    bole    boil    west    east     emil    lobs    limb    lime    lima    mesa    mews    mewl    maws     milo    mile    awes    amie    axle    elma    fame    ubs    tux    tub     twa    twa    stu    saw    sea    sew    sea    awe    awl    but    btu     box    bmw    was    wax    oil    lox    lob    leo    lei    lie    mes     mew    mae    maw    max    mil    mix    awe    awl    elm    eli    fax

User · Answer

I suggest making a tree of letters based on words   The tree would be composed of a letter structs  like this   letter  char isWord  boolean   Then you build up the tree  with each depth adding a new letter   In other words  on the first level there d be the alphabet  then from each of those trees  there d be another another 26 entries  and so on  until you ve spelled out all the words   Hang onto this parsed tree  and it ll make all possible answers faster to look up   With this parsed tree  you can very quickly find solutions   Here s the pseudo-code   BEGIN       For each letter          if the struct representing it on the current depth has isWord    true  enter it as an answer          Cycle through all its neighbors  if there is a child of the current node corresponding to the letter  recursively call BEGIN on it    This could be sped up with a bit of dynamic programming   For example  in your sample  the two  A s are both next to an  E  and a  W   which  from the point they hit them on  would be identical   I don t have enough time to really spell out the code for this  but I think you can gather the idea   Also  I m sure you ll find other solutions if you Google for  Boggle solver

User · Answer

My answer works like the others here  but I ll post it because it looks a bit faster than the other Python solutions  from setting up the dictionary faster   I checked this against John Fouhy s solution   After setup  the time to solve is down in the noise   grid    fxie amlo ewbx astu  split   nrows  ncols   len grid   len grid 0      A dictionary word that could be a solution must use only the grid s   letters and have length  gt   3   With a case-insensitive match   import re alphabet      join set    join grid    bogglable   re compile       alphabet      3      re I  match  words   set word rstrip   n   for word in open  words   if bogglable word   prefixes   set word  i  for word in words                for i in range 2  len word  1    def solve        for y  row in enumerate grid           for x  letter in enumerate row               for result in extending letter    x  y                      yield result  def extending prefix  path       if prefix in words          yield  prefix  path      for  nx  ny  in neighbors path -1            if  nx  ny  not in path              prefix1   prefix   grid ny  nx              if prefix1 in prefixes                  for result in extending prefix1  path     nx  ny                          yield result  def neighbors  x  y        for nx in range max 0  x-1   min x 2  ncols            for ny in range max 0  y-1   min y 2  nrows                yield  nx  ny    Sample usage     Print a maximal-length word and its path  print max solve    key lambda  word  path   len word     Edit  Filter out words less than 3 letters long   Edit 2  I was curious why Kent Fredric s Perl solution was faster  it turns out to use regular-expression matching instead of a set of characters  Doing the same in Python about doubles the speed

User · Answer

I solved this too  with Java  My implementation is 269 lines long and pretty easy to use  First you need to create a new instance of the Boggler class and then call the solve function with the grid as a parameter  It takes about 100 ms to load the dictionary of 50 000 words on my computer and it finds the words in about 10-20 ms  The found words are stored in an ArrayList  foundWords   import java io BufferedReader  import java io File  import java io FileInputStream  import java io FileNotFoundException  import java io IOException  import java io InputStreamReader  import java net URISyntaxException  import java net URL  import java util ArrayList  import java util Arrays  import java util Comparator   public class Boggler       private ArrayList lt String gt  words   new ArrayList lt String gt               private ArrayList lt String gt  roundWords   new ArrayList lt String gt          private ArrayList lt Word gt  foundWords   new ArrayList lt Word gt              private char     letterGrid   new char 4  4                          private String letters                                                public Boggler   throws FileNotFoundException  IOException  URISyntaxException           long startTime   System currentTimeMillis             URL path   GUI class getResource  words txt            BufferedReader br   new BufferedReader new InputStreamReader new FileInputStream new File path toURI    getAbsolutePath      iso-8859-1             String line          while  line   br readLine       null                if line length    lt  3    line length    gt  10                    continue                             this words add line                        public ArrayList lt Word gt  getWords             return this foundWords             public void solve String letters            this letters               this foundWords   new ArrayList lt Word gt              for int i   0  i  lt  letters length    i                  if  this letters contains letters substring i  i   1                      this letters    letters substring i  i   1                                    for int i   0  i  lt  4  i                  for int j   0  j  lt  4  j                      this letterGrid i  j    letters charAt i   4   j                                    System out println Arrays deepToString this letterGrid                            this roundWords   new ArrayList lt String gt                   String pattern         this letters                       for int i   0  i  lt  this words size    i                   if this words get i  matches pattern                     this roundWords add this words get i                                     for int i   0  i  lt  this roundWords size    i                  Word word   checkForWord this roundWords get i                 if word    null                    System out println word                   this foundWords add word                                             private Word checkForWord String word            char initial   word charAt 0           ArrayList lt LetterCoord gt  startPoints   new ArrayList lt LetterCoord gt              int x   0            int y   0          for char   row  this letterGrid                x   0               for char letter  row                    if initial    letter                        startPoints add new LetterCoord x  y                                       x                               y                       ArrayList lt LetterCoord gt  letterCoords   null          for int initialTry   0  initialTry  lt  startPoints size    initialTry                  letterCoords   new ArrayList lt LetterCoord gt                      x   startPoints get initialTry  getX                 y   startPoints get initialTry  getY                 LetterCoord initialCoord   new LetterCoord x  y               letterCoords add initialCoord                letterLoop  for int letterIndex   1  letterIndex  lt  word length    letterIndex                      LetterCoord lastCoord   letterCoords get letterCoords size   - 1                     char currentChar   word charAt letterIndex                                            ArrayList lt LetterCoord gt  letterLocations   getNeighbours currentChar  lastCoord getX    lastCoord getY                      if letterLocations    null                        return null                                                for int foundIndex   0  foundIndex  lt  letterLocations size    foundIndex                          if letterIndex    word length   - 1  amp  amp  true    false                            char nextChar   word charAt letterIndex   1                           int lastX   letterCoords get letterCoords size   - 1  getX                            int lastY   letterCoords get letterCoords size   - 1  getY                             ArrayList lt LetterCoord gt  possibleIndex   getNeighbours nextChar  lastX  lastY                           if possibleIndex    null                                if  letterCoords contains letterLocations get foundIndex                                      letterCoords add letterLocations get foundIndex                                                              continue letterLoop                            else                               return null                                                  else                           if  letterCoords contains letterLocations get foundIndex                                  letterCoords add letterLocations get foundIndex                                 continue letterLoop                                                                                               if letterCoords    null                    if letterCoords size      word length                          Word w   new Word word                       w addList letterCoords                       return w                    else                       return null                                                     if letterCoords    null                Word foundWord   new Word word               foundWord addList letterCoords                return foundWord                     return null             public ArrayList lt LetterCoord gt  getNeighbours char letterToSearch  int x  int y            ArrayList lt LetterCoord gt  neighbours   new ArrayList lt LetterCoord gt              for int  y   y - 1   y  lt   y   1   y                  for int  x   x - 1   x  lt   x   1   x                      if  x  lt  0     y  lt  0      x    x  amp  amp   y    y      y  gt  3     x  gt  3                        continue                                     if this letterGrid  y   x     letterToSearch  amp  amp   neighbours contains new LetterCoord  x   y                          neighbours add new LetterCoord  x   y                                                       if neighbours isEmpty                  return null            else               return neighbours                     class Word       private String word          private ArrayList lt LetterCoord gt  letterCoords   new ArrayList lt LetterCoord gt          public Word String word            this word   word             public boolean addCoords int x  int y            LetterCoord lc   new LetterCoord x  y            if  this letterCoords contains lc                 this letterCoords add lc                return true                     return false             public void addList ArrayList lt LetterCoord gt  letterCoords            this letterCoords   letterCoords               Override     public String toString             String outputString   this word                for int i   0  i  lt  letterCoords size    i                  outputString          letterCoords get i  getX            letterCoords get i  getY                              return outputString             public String getWord             return this word             public ArrayList lt LetterCoord gt  getList             return this letterCoords           class LetterCoord extends ArrayList       private int x                private int y                 public LetterCoord int x  int y            this x   x          this y   y             public int getX             return this x             public int getY             return this y              Override     public boolean equals Object o            if   o instanceof LetterCoord                 return false                     LetterCoord lc    LetterCoord  o           if this x    lc getX    amp  amp                  this y    lc getY                  return true                     return false              Override     public int hashCode             int hash   7          hash   29   hash   this x          hash   24   hash   this y          return hash

User · Answer

I think you will probably spend most of your time trying to match words that can t possibly be built by your letter grid  So  the first thing I would do is try to speed up that step and that should get you most of the way there   For this  I would re-express the grid as a table of possible  moves  that you index by the letter-transition you are looking at   Start by assigning each letter a number from your entire alphabet  A 0  B 1  C 2      and so forth     Let s take this example   h b c d e e g h l l k l m o f p   And for now  lets use the alphabet of the letters we have  usually you d probably want to use the same whole alphabet every time     b   c   d   e   f   g   h   k   l   m    o    p --- --- --- --- --- --- --- --- --- --- ---- ----  0   1   2   3   4   5   6   7   8   9   10   11   Then you make a 2D boolean array that tells whether you have a certain letter transition available           0  1  2  3  4  5  6  7  8  9 10 11   lt - from letter         b  c  d  e  f  g  h  k  l  m  o  p ----- --------------------------------------  0 b       T     T     T  T       1 c    T     T  T     T  T  2 d       T           T  T  3 e    T  T     T     T  T  T  T  4 f                         T  T     T  T  5 g    T  T  T  T        T  T  T  6 h    T  T  T  T     T     T  T  7 k             T  T  T  T     T     T  T  8 l             T  T  T  T  T  T  T  T  T  9 m                            T     T 10 o                T        T  T  T 11 p                T        T  T     to letter   Now go through your word list and convert the words to transitions   hello  6  3  8  8  10   6 - gt  3  3 - gt  8  8 - gt  8  8 - gt  10   Then check if these transitions are allowed by looking them up in your table    6   3    T  3   8    T  8   8    T  8  10    T   If they are all allowed  there s a chance that this word might be found   For example the word  helmet  can be ruled out on the 4th transition  m to e  helMEt   since that entry in your table is false   And the word hamster can be ruled out  since the first  h to a  transition is not allowed  doesn t even exist in your table    Now  for the probably very few remaining words that you didn t eliminate  try to actually find them in the grid the way you re doing it now or as suggested in some of the other answers here  This is to avoid false positives that result from jumps between identical letters in your grid  For example the word  help  is allowed by the table  but not by the grid   Some further performance improvement tips on this idea    Instead of using a 2D array  use a 1D array and simply compute the index of the second letter yourself  So  instead of a 12x12 array like above  make a 1D array of length 144  If you then always use the same alphabet  i e  a 26x26   676x1 array for the standard english alphabet   even if not all letters show up in your grid  you can pre-compute the indices into this 1D array that you need to test to match your dictionary words  For example  the indices for  hello  in the example above would be  hello  6  3  8  8  10   42  from 6   3x12   99  104  128 - gt   hello  will be stored as 42  99  104  128 in the dictionary  Extend the idea to a 3D table  expressed as a 1D array   i e  all allowed 3-letter combinations  That way you can eliminate even more words immediately and you reduce the number of array lookups for each word by 1  For  hello   you only need 3 array lookups  hel  ell  llo  It will be very quick to build this table  by the way  as there are only 400 possible 3-letter-moves in your grid  Pre-compute the indices of the moves in your grid that you need to include in your table  For the example above  you need to set the following entries to  True     0 0   0 1  - gt  here  h  b    6  0   0 0   1 0  - gt  here  h  e    6  3   0 0   1 1  - gt  here  h  e    6  3   0 1   0 0  - gt  here  b  h    0  6   0 1   0 2  - gt  here  b  c    0  1       Also represent your game grid in a 1-D array with 16 entries and have the table pre-computed in 3  contain the indices into this array    I m sure if you use this approach you can get your code to run insanely fast  if you have the dictionary pre-computed and already loaded into memory   BTW  Another nice thing to do  if you are building a game  is to run these sort of things immediately in the background  Start generating and solving the first game while the user is still looking at the title screen on your app and getting his finger into position to press  Play   Then generate and solve the next game as the user plays the previous one  That should give you a lot of time to run your code    I like this problem  so I ll probably be tempted to implement my proposal in Java sometime in the next days to see how it would actually perform    I ll post the code here once I do    UPDATE   Ok  I had some time today and implemented this idea in Java   class DictionaryEntry     public int   letters    public int   triplets     class BoggleSolver         Constants   final int ALPHABET SIZE   5      up to 2 5   32 letters   final int BOARD SIZE      4      4x4 board   final int   moves    -BOARD SIZE-1  -BOARD SIZE  -BOARD SIZE 1                                     -1                           1                          BOARD SIZE-1   BOARD SIZE   BOARD SIZE 1          Technically constant  calculated here for flexibility  but should be fixed    DictionaryEntry   dictionary     Processed word list   int maxWordLength   0    int   boardTripletIndices     List of all 3-letter moves in board coordinates    DictionaryEntry   buildDictionary String fileName  throws IOException       BufferedReader fileReader   new BufferedReader new FileReader fileName        String word   fileReader readLine        ArrayList lt DictionaryEntry gt  result   new ArrayList lt DictionaryEntry gt         while  word  null          if  word length   gt  3            word   word toUpperCase            if  word length   gt maxWordLength  maxWordLength   word length            DictionaryEntry entry   new DictionaryEntry            entry letters    new int word length               entry triplets   new int word length  -2           int i 0          for  char letter  word toCharArray                entry letters i     byte  letter - 65     Convert ASCII to 0  25           if  i gt  2              entry triplets i-2       entry letters i-2    lt  lt  ALPHABET SIZE                                         entry letters i-1    lt  lt  ALPHABET SIZE                                         entry letters i             i                      result add entry                 word   fileReader readLine              return result toArray new DictionaryEntry result size             boolean isWrap int a  int b       Checks if move a- gt b wraps board edge  like 3- gt 4      return Math abs a BOARD SIZE-b BOARD SIZE  gt 1         int   buildTripletIndices         ArrayList lt Integer gt  result   new ArrayList lt Integer gt         for  int a 0  a lt BOARD SIZE BOARD SIZE  a          for  int bm  moves            int b a bm          if   b gt  0   amp  amp   b lt board length   amp  amp   isWrap a  b             for  int cm  moves                int c b cm              if   c gt  0   amp  amp   c lt board length   amp  amp   c  a   amp  amp   isWrap b  c                   result add a                 result add b                 result add c                                         int   result2   new int result size         int i 0      for  Integer r  result  result2 i      r      return result2             Variables that depend on the actual game layout   int   board   new int BOARD SIZE BOARD SIZE      Letters in board   boolean   possibleTriplets   new boolean 1  lt  lt   ALPHABET SIZE 3       DictionaryEntry   candidateWords    int candidateCount     int   usedBoardPositions     DictionaryEntry   foundWords    int foundCount     void initializeBoard String   letters        for  int row 0  row lt BOARD SIZE  row          for  int col 0  col lt BOARD SIZE  col            board row BOARD SIZE   col     byte  letters row  charAt col  - 65         void setPossibleTriplets         Arrays fill possibleTriplets  false      Reset list     int i 0      while  i lt boardTripletIndices length          int triplet      board boardTripletIndices i       lt  lt  ALPHABET SIZE                           board boardTripletIndices i       lt  lt  ALPHABET SIZE                           board boardTripletIndices i            possibleTriplets triplet    true                void checkWordTriplets         candidateCount   0      for  DictionaryEntry entry  dictionary          boolean ok   true        int len   entry triplets length        for  int t 0   t lt len   amp  amp  ok  t            ok   possibleTriplets entry triplets t          if  ok  candidateWords candidateCount      entry               void checkWords        Can probably be optimized a lot     foundCount   0      for  int i 0  i lt candidateCount  i            DictionaryEntry candidate   candidateWords i         for  int j 0  j lt board length  j            if  board j   candidate letters 0                usedBoardPositions 0    j            if  checkNextLetters candidate  1  j                 foundWords foundCount      candidate              break                                     boolean checkNextLetters DictionaryEntry candidate  int letter  int pos        if  letter  candidate letters length  return true      int match   candidate letters letter       for  int move  moves          int next pos move        if   next gt  0   amp  amp   next lt board length   amp  amp   board next   match   amp  amp   isWrap pos  next             boolean ok   true          for  int i 0   i lt letter   amp  amp  ok  i              ok   usedBoardPositions i   next          if  ok              usedBoardPositions letter    next            if  checkNextLetters candidate  letter 1  next   return true                                 return false             Just some helper functions   String formatTime long start  long end  long repetitions        long time    end-start  repetitions      return time 1000000          time 100000    10         time 10000    10    ms          String getWord DictionaryEntry entry        char   result   new char entry letters length       int i 0      for  int letter  entry letters        result i       char   letter 97       return new String result          void run   throws IOException       long start   System nanoTime            The following can be pre-computed and should be replaced by constants     dictionary   buildDictionary  C  TWL06 txt        boardTripletIndices   buildTripletIndices        long precomputed   System nanoTime             The following only needs to run once at the beginning of the program     candidateWords       new DictionaryEntry dictionary length      WAAAY too generous     foundWords           new DictionaryEntry dictionary length      WAAAY too generous     usedBoardPositions   new int maxWordLength       long initialized   System nanoTime          for  int n 1  n lt  100  n               The following needs to run again for every new board       initializeBoard new String     DGHI                                        KLPS                                        YEUT                                        EORN           setPossibleTriplets          checkWordTriplets          checkWords              long solved   System nanoTime             Print out result and statistics     System out println  Precomputation finished in     formatTime start  precomputed  1            System out println    Words in the dictionary    dictionary length       System out println    Longest word               maxWordLength   letters        System out println    Number of triplet-moves    boardTripletIndices length 3       System out println         System out println  Initialization finished in     formatTime precomputed  initialized  1        System out println         System out println  Board solved in   formatTime initialized  solved  100            System out println    Number of candidates    candidateCount       System out println    Number of actual words    foundCount       System out println         System out println  Words found         int w 0      System out print            for  int i 0  i lt foundCount  i            System out print getWord foundWords i           w          if  w  10            w 0          System out println    System out print                else         if  i lt foundCount-1  System out print                  System out println           public static void main String   args  throws IOException       new BoggleSolver   run            Here are some results   For the grid from the picture posted in the original question  DGHI       Precomputation finished in 239 59ms    Words in the dictionary  178590   Longest word             15 letters   Number of triplet-moves  408  Initialization finished in 0 22ms  Board solved in 3 70ms    Number of candidates  230   Number of actual words  163   Words found    eek  eel  eely  eld  elhi  elk  ern  erupt  erupts  euro   eye  eyer  ghi  ghis  glee  gley  glue  gluer  gluey  glut   gluts  hip  hiply  hips  his  hist  kelp  kelps  kep  kepi   kepis  keps  kept  kern  key  kye  lee  lek  lept  leu   ley  lunt  lunts  lure  lush  lust  lustre  lye  nus  nut   nuts  ore  ort  orts  ouph  ouphs  our  oust  out  outre   outs  oyer  pee  per  pert  phi  phis  pis  pish  plus   plush  ply  plyer  psi  pst  pul  pule  puler  pun  punt   punts  pur  pure  puree  purely  pus  push  put  puts  ree   rely  rep  reply  reps  roe  roue  roup  roups  roust  rout   routs  rue  rule  ruly  run  runt  runts  rupee  rush  rust   rut  ruts  ship  shlep  sip  sipe  spue  spun  spur  spurn   spurt  strep  stroy  stun  stupe  sue  suer  sulk  sulker  sulky   sun  sup  supe  super  sure  surely  tree  trek  trey  troupe   troy  true  truly  tule  tun  tup  tups  turn  tush  ups   urn  uts  yeld  yelk  yelp  yelps  yep  yeps  yore  you   your  yourn  yous   For the letters posted as the example in the original question  FXIE      Precomputation finished in 239 68ms    Words in the dictionary  178590   Longest word             15 letters   Number of triplet-moves  408  Initialization finished in 0 21ms  Board solved in 3 69ms    Number of candidates  87   Number of actual words  76  Words found    amble  ambo  ami  amie  asea  awa  awe  awes  awl  axil   axile  axle  boil  bole  box  but  buts  east  elm  emboli   fame  fames  fax  lei  lie  lima  limb  limbo  limbs  lime   limes  lob  lobs  lox  mae  maes  maw  maws  max  maxi   mesa  mew  mewl  mews  mil  mile  milo  mix  oil  ole   sae  saw  sea  seam  semi  sew  stub  swam  swami  tub   tubs  tux  twa  twae  twaes  twas  uts  wae  waes  wamble   wame  wames  was  wast  wax  west   For the following 5x5-grid   R P R I T A H H L N I E T E P Z R Y S G O G W E Y   it gives this   Precomputation finished in 240 39ms    Words in the dictionary  178590   Longest word             15 letters   Number of triplet-moves  768  Initialization finished in 0 23ms  Board solved in 3 85ms    Number of candidates  331   Number of actual words  240  Words found    aero  aery  ahi  air  airt  airth  airts  airy  ear  egest   elhi  elint  erg  ergo  ester  eth  ether  eye  eyen  eyer   eyes  eyre  eyrie  gel  gelt  gelts  gen  gent  gentil  gest   geste  get  gets  gey  gor  gore  gory  grey  greyest  greys   gyre  gyri  gyro  hae  haet  haets  hair  hairy  hap  harp   heap  hear  heh  heir  help  helps  hen  hent  hep  her   hero  hes  hest  het  hetero  heth  hets  hey  hie  hilt   hilts  hin  hint  hire  hit  inlet  inlets  ire  leg  leges   legs  lehr  lent  les  lest  let  lethe  lets  ley  leys   lin  line  lines  liney  lint  lit  neg  negs  nest  nester   net  nether  nets  nil  nit  ogre  ore  orgy  ort  orts   pah  pair  par  peg  pegs  peh  pelt  pelter  peltry  pelts   pen  pent  pes  pest  pester  pesty  pet  peter  pets  phi   philter  philtre  phiz  pht  print  pst  rah  rai  rap  raphe   raphes  reap  rear  rei  ret  rete  rets  rhaphe  rhaphes  rhea   ria  rile  riles  riley  rin  rye  ryes  seg  sel  sen   sent  senti  set  sew  spelt  spelter  spent  splent  spline  splint   split  stent  step  stey  stria  striae  sty  stye  tea  tear   teg  tegs  tel  ten  tent  thae  the  their  then  these   thesp  they  thin  thine  thir  thirl  til  tile  tiles  tilt   tilter  tilth  tilts  tin  tine  tines  tirl  trey  treys  trog   try  tye  tyer  tyes  tyre  tyro  west  wester  wry  wryest   wye  wyes  wyte  wytes  yea  yeah  year  yeh  yelp  yelps   yen  yep  yeps  yes  yester  yet  yew  yews  zero  zori   For this I used the TWL06 Tournament Scrabble Word List  since the link in the original question no longer works  This file is 1 85MB  so it s a little bit shorter  And the buildDictionary function throws out all words with less than 3 letters   Here are a couple of observations about the performance of this    It s about 10 times slower than the reported performance of Victor Nicollet s OCaml implementation  Whether this is caused by the different algorithm  the shorter dictionary he used  the fact that his code is compiled and mine runs in a Java virtual machine  or the performance of our computers  mine is an Intel Q6600   2 4MHz running WinXP   I don t know  But it s much faster than the results for the other implementations quoted at the end of the original question  So  whether this algorithm is superior to the trie dictionary or not  I don t know at this point  The table method used in checkWordTriplets   yields a very good approximation to the actual answers  Only 1 in 3-5 words passed by it will fail the checkWords   test  See number of candidates vs  number of actual words above   Something you can t see above  The checkWordTriplets   function takes about 3 65ms and is therefore fully dominant in the search process  The checkWords   function takes up pretty much the remaining 0 05-0 20 ms  The execution time of the checkWordTriplets   function depends linearly on the dictionary size and is virtually independent of board size  The execution time of checkWords   depends on the board size and the number of words not ruled out by checkWordTriplets    The checkWords   implementation above is the dumbest first version I came up with  It is basically not optimized at all  But compared to checkWordTriplets   it is irrelevant for the total performance of the application  so I didn t worry about it  But  if the board size gets bigger  this function will get slower and slower and will eventually start to matter  Then  it would need to be optimized as well  One nice thing about this code is its flexibility    You can easily change the board size  Update line 10 and the String array passed to initializeBoard    It can support larger different alphabets and can handle things like treating  Qu  as one letter without any performance overhead  To do this  one would need to update line 9 and the couple of places where characters are converted to numbers  currently simply by subtracting 65 from the ASCII value     Ok  but I think by now this post is waaaay long enough  I can definitely answer any questions you might have  but let s move that to the comments

User · Answer

I spent 3 months working on a solution to the 10 best point dense 5x5 Boggle boards problem   The problem is now solved and laid out with full disclosure on 5 web pages   Please contact me with questions   The board analysis algorithm uses an explicit stack to pseudo-recursively traverse the board squares through a Directed Acyclic Word Graph with direct child information  and a time stamp tracking mechanism   This may very well be the world s most advanced lexicon data structure   The scheme evaluates some 10 000 very good boards per second on a quad core   9500  points   Parent Web Page   DeepSearch c - http   www pathcom com  vadco deep html  Component Web Pages   Optimal Scoreboard - http   www pathcom com  vadco binary html  Advanced Lexicon Structure - http   www pathcom com  vadco adtdawg html  Board Analysis Algorithm - http   www pathcom com  vadco guns html  Parallel Batch Processing - http   www pathcom com  vadco parallel html  - This comprehensive body of work will only interest a person who demands the very best

User · Answer

Here is my java implementation  https   github com zouzhile interview blob master src com interview algorithms tree BoggleSolver java  Trie build took 0 hours  0 minutes  1 seconds  532 milliseconds Word searching took 0 hours  0 minutes  0 seconds  92 milliseconds  eel eeler eely eer eke eker eld eleut elk ell  elle epee epihippus ere erept err error erupt eurus eye  eyer eyey hip hipe hiper hippish hipple hippus his hish  hiss hist hler hsi ihi iphis isis issue issuer ist  isurus kee keek keeker keel keeler keep keeper keld kele  kelek kelep kelk kell kelly kelp kelper kep kepi kept  ker kerel kern keup keuper key kyl kyle lee leek  leeky leep leer lek leo leper leptus lepus ler leu  ley lleu lue lull luller lulu lunn lunt lunule luo  lupe lupis lupulus lupus lur lure lurer lush lushly lust  lustrous lut lye nul null nun nupe nurture nurturer nut  oer ore ort ouphish our oust out outpeep outpeer outpipe  outpull outpush output outre outrun outrush outspell outspue outspurn outspurt  outstrut outstunt outsulk outturn outusure oyer pee peek peel peele  peeler peeoy peep peeper peepeye peer pele peleus pell peller  pelu pep peplus pepper pepperer pepsis per pern pert pertussis  peru perule perun peul phi pip pipe piper pipi pipistrel  pipistrelle pipistrellus pipper pish piss pist plup plus plush ply  plyer psi pst puerer pul pule puler pulk pull puller  pulley pullus pulp pulper pulu puly pun punt pup puppis  pur pure puree purely purer purr purre purree purrel purrer  puru purupuru pus push puss pustule put putt puture ree  reek reeker reeky reel reeler reeper rel rely reoutput rep  repel repeller repipe reply repp reps reree rereel rerun reuel  roe roer roey roue rouelle roun roup rouper roust rout  roy rue ruelle ruer rule ruler rull ruller run runt  rupee rupert rupture ruru rus rush russ rust rustre rut  shi shih ship shipper shish shlu sip sipe siper sipper  sis sish sisi siss sissu sist sistrurus speel speer spelk  spell speller splurt spun spur spurn spurrer spurt sput ssi  ssu stre stree streek streel streeler streep streke streperous strepsis  strey stroup stroy stroyer strue strunt strut stu stue stull  stuller stun stunt stupe stupeous stupp sturnus sturt stuss stut  sue suer suerre suld sulk sulker sulky sull sully sulu  sun sunn sunt sunup sup supe super superoutput supper supple  supplely supply sur sure surely surrey sus susi susu susurr  susurrous susurrus sutu suture suu tree treey trek trekker trey  troupe trouper trout troy true truer trull truller truly trun  trush truss trust tshi tst tsun tsutsutsi tue tule tulle  tulu tun tunu tup tupek tupi tur turn turnup turr  turus tush tussis tussur tut tuts tutu tutulus ule ull  uller ulu ululu unreel unrule unruly unrun unrust untrue untruly  untruss untrust unturn unurn upper upperer uppish uppishly uppull uppush  upspurt upsun upsup uptree uptruss upturn ure urn uro uru  urus urushi ush ust usun usure usurer utu yee yeel  yeld yelk yell yeller yelp yelper yeo yep yer yere  yern yoe yor yore you youl youp your yourn yoy    Note  I used the dictionary and character matrix at the beginning of this thread  The code was run on my MacBookPro  below is some information about the machine    Model Name    MacBook Pro   Model Identifier  MacBookPro8 1   Processor Name    Intel Core i5   Processor Speed   2 3 GHz   Number Of Processors  1   Total Number Of Cores     2   L2 Cache  per core    256 KB   L3 Cache  3 MB   Memory    4 GB   Boot ROM Version  MBP81 0047 B0E   SMC Version  system   1 68f96

User · Answer

As soon as I saw the problem statement  I thought  Trie   But seeing as several other posters made use of that approach  I looked for another approach just to be different  Alas  the Trie approach performs better  I ran Kent s Perl solution on my machine and it took 0 31 seconds to run  after adapting it to use my dictionary file  My own perl implementation required 0 54 seconds to run    This was my approach    Create a transition hash to model the legal transitions  Iterate through all 16 3 possible three letter combinations    In the loop  exclude illegal transitions and repeat visits to the same square  Form all the legal 3-letter sequences and store them in a hash   Then loop through all words in the dictionary    Exclude words that are too long or short Slide a 3-letter window across each word and see if it is among the 3-letter combos from step 2  Exclude words that fail  This eliminates most non-matches  If still not eliminated  use a recursive algorithm to see if the word can be formed by making paths through the puzzle   This part is slow  but called infrequently    Print out the words I found   I tried 3-letter and 4-letter sequences  but 4-letter sequences slowed the program down    In my code  I use  usr share dict words for my dictionary  It comes standard on MAC OS X and many Unix systems  You can use another file if you want  To crack a different puzzle  just change the variable  puzzle  This would be easy to adapt for larger matrices  You would just need to change the  transitions hash and  legalTransitions hash    The strength of this solution is that the code is short  and the data structures simple   Here is the Perl code  which uses too many global variables  I know       usr bin perl use Time  HiRes  qw  time     sub readFile     sub findAllPrefixes     sub isWordTraceable     sub findWordsInPuzzle      my  startTime   time     Puzzle to solve  my  puzzle          F  X  I  E      A  M  L  O      E  W  B  X      A  S  T  U     my  minimumWordLength   3  my  maximumPrefixLength   3    I tried four and it slowed down     Slurp the word list  my  wordlistFile     usr share dict words    my  words   split   n   uc readFile  wordlistFile     print  Words loaded from word list      scalar  words     n    print  Word file load time       time -  startTime      n   my  postLoad   time     Define the legal transitions from one letter position to another     Positions are numbered 0-15        0  1  2  3       4  5  6  7       8  9 10 11      12 13 14 15 my  transitions         -1   gt   0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15       0   gt   1 4 5        1   gt   0 2 4 5 6       2   gt   1 3 5 6 7       3   gt   2 6 7       4   gt   0 1 5 8 9       5   gt   0 1 2 4 6 8 9 10       6   gt   1 2 3 5 7 9 10 11       7   gt   2 3 6 10 11       8   gt   4 5 9 12 13       9   gt   4 5 6 8 10 12 13 14       10   gt   5 6 7 9 11 13 14 15       11   gt   6 7 10 14 15       12   gt   8 9 13       13   gt   8 9 10 12 14       14   gt   9 10 11 13 15       15   gt   10 11 14        Convert the transition matrix into a hash for easy access  my  legalTransitions       foreach my  start  keys  transitions        my  legalRef    transitions  start       foreach my  stop    legalRef            my  index     start   1     scalar  puzzle      stop   1            legalTransitions  index    1           my  prefixesInPuzzle   findAllPrefixes  maximumPrefixLength    print  Find prefixes time       time -  postLoad      n   my  postPrefix   time   my  wordsFoundInPuzzle   findWordsInPuzzle  words    print  Find words in puzzle time       time -  postPrefix      n    print  Unique prefixes found       scalar keys  prefixesInPuzzle      n   print  Words found       scalar  wordsFoundInPuzzle         n        join   n        wordsFoundInPuzzle      n    print  Total Elapsed time       time -  startTime      n                                                 sub readFile          my   filename            my  contents      if  -e  filename              This is magic  it opens and reads a file into a scalar in one line of code             See http   www perl com pub a 2003 11 21 slurp html          contents   do   local   ARGV          filename    lt  gt                 else            contents                 return  contents       Is it legal to move from the first position to the second  They must be adjacent  sub isLegalTransition           my   pos1  pos2            my  index     pos1   1     scalar  puzzle      pos2   1       return  legalTransitions  index        Find all prefixes where  minimumWordLength  lt   length  lt    maxPrefixLength        maxPrefixLength     Maximum length of prefix we will store  Three gives best performance   sub findAllPrefixes          my   maxPrefixLength            my  prefixes           my  puzzleSize   scalar  puzzle         Every possible N-letter combination of the letters in the puzzle        can be represented as an integer  though many of those combinations       involve illegal transitions  duplicated letters  etc        Iterate through all those possibilities and eliminate the illegal ones      my  maxIndex    puzzleSize     maxPrefixLength       for  my  i   0   i  lt   maxIndex   i              my  path          my  remainder    i          my  prevPosition   -1          my  prefix               my  usedPositions               for  my  prefixLength   1   prefixLength  lt    maxPrefixLength   prefixLength                  my  position    remainder    puzzleSize                 Is this a valid step                 a  Is the transition legal  to an adjacent square               if    isLegalTransition  prevPosition   position                     last                                b  Have we repeated a square              if   usedPositions  position                     last                            else                    usedPositions  position    1                               Record this prefix if length  gt    minimumWordLength               prefix     puzzle  position               if   prefixLength  gt    minimumWordLength                     prefixes  prefix    1                             push  path   position               remainder -   position               remainder     puzzleSize               prevPosition    position              end inner for         end outer for     return  prefixes       Loop through all words in dictionary  looking for ones that are in the puzzle  sub findWordsInPuzzle          my  allWords           my  wordsFound           my  puzzleSize   scalar  puzzle  WORD  foreach my  word   allWords            my  wordLength   length  word           if   wordLength  gt   puzzleSize     wordLength  lt   minimumWordLength                  Reject word as too short or too long                    elsif   wordLength  lt    maximumPrefixLength                   Word should be in the prefix hash              if   prefixesInPuzzle  word                     push  wordsFound   word                                  else                 Scan through the word using a window of length  maximumPrefixLength  looking for any strings not in our prefix list                If any are found that are not in the list  this word is not possible                If no non-matches are found  we have more work to do              my  limit    wordLength -  maximumPrefixLength   1              for  my  startIndex   0   startIndex  lt   limit   startIndex                       if     prefixesInPuzzle substr  word   startIndex   maximumPrefixLength                          next WORD                                              if  isWordTraceable  word                       Additional test necessary  see if we can form this word by following legal transitions                 push  wordsFound   word                                     return  wordsFound       Is it possible to trace out the word using only legal transitions  sub isWordTraceable          my  word   shift      return traverse  split      word     -1      Start at special square -1  which may transition to any square in the puzzle       Recursively look for a path through the puzzle that matches the word  sub traverse           my   lettersRef   pathRef            my  index   scalar   pathRef - 1      my  position    pathRef- gt   index       my  letter    lettersRef- gt   index       my  branchesRef     transitions  position   BRANCH  foreach my  branch    branchesRef                if   puzzle  branch  eq  letter                      Have we used this position yet                  foreach my  usedBranch    pathRef                        if   usedBranch     branch                            next BRANCH                                                          if  scalar   lettersRef     index   1                        return 1    End of word and success                                    push   pathRef   branch                  if  traverse  lettersRef   pathRef                         return 1    Recursive success                                    else                       pop   pathRef                                                return 0    No path found  Failed

User · Answer

I wrote my solver in C    I implemented a custom tree structure  I m not sure it can be considered a trie but it s similar  Each node has 26 branches  1 for each letter of the alphabet  I traverse the branches of the boggle board in parallel with the branches of my dictionary  If the branch does not exist in the dictionary  I stop searching it on the Boggle board  I convert all the letters on the board to ints  So  A    0  Since it s just arrays  lookup is always O 1   Each node stores if it completes a word and how many words exist in its children  The tree is pruned as words are found to reduce repeatedly searching for the same words  I believe pruning is also O 1    CPU  Pentium SU2700 1 3GHz RAM  3gb    Loads dictionary of 178 590 words in  lt  1 second  Solves 100x100 Boggle  boggle txt  in 4 seconds   44 000 words found  Solving a 4x4 Boggle is too fast to provide a meaningful benchmark      Fast Boggle Solver GitHub Repo

User · Answer

A Node JS JavaScript solution  Computes all 100 unique words in less than a second which includes reading dictionary file  MBA 2012    Output    FAM   TUX   TUB   FAE   ELI   ELM   ELB   TWA   TWA   SAW   AMI   SWA   SWA   AME   SEA   SEW   AES   AWL   AWE   SEA   AWA   MIX   MIL   AST   ASE   MAX   MAE   MAW   MEW   AWE   MES   AWL   LIE   LIM   AWA   AES   BUT   BLO   WAS   WAE   WEA   LEI   LEO   LOB   LOX   WEM   OIL   OLM   WEA   WAE   WAX   WAF   MILO   EAST   WAME   TWAS   TWAE   EMIL   WEAM   OIME   AXIL   WEST   TWAE   LIMB   WASE   WAST   BLEO   STUB   BOIL   BOLE   LIME   SAWT   LIMA   MESA   MEWL   AXLE   FAME   ASEM   MILE   AMIL   SEAX   SEAM   SEMI   SWAM   AMBO   AMLI   AXILE   AMBLE   SWAMI   AWEST   AWEST   LIMAX   LIMES   LIMBU   LIMBO   EMBOX   SEMBLE   EMBOLE   WAMBLE   FAMBLE    Code   var fs   require  fs    var Node   function value  row  col        this value   value     this row   row     this col   col    var Path   function         this nodes         Path prototype push   function node        this nodes push node      return this    Path prototype contains   function node        for  var i   0  ii   this nodes length  i  lt  ii  i              if  this nodes i      node                return true                      return false    Path prototype clone   function         var path   new Path       path nodes   this nodes slice 0      return path    Path prototype to word   function         var word           for  var i   0  ii   this nodes length  i  lt  ii    i            word    this nodes i  value            return word    var Board   function nodes  dict           Expects n x m array      this nodes   nodes     this words          this row count   nodes length     this col count   nodes 0  length     this dict   dict    Board from raw   function board  dict        var ROW COUNT   board length         COL COUNT   board 0  length      var nodes              Replace board with Nodes     for  var i   0  ii   ROW COUNT  i  lt  ii    i            nodes push             for  var j   0  jj   COL COUNT  j  lt  jj    j                nodes i  push new Node board i  j   i  j                        return new Board nodes  dict     Board prototype toString   function         return JSON stringify this nodes     Board prototype update potential words   function dict        for  var i   0  ii   this row count  i  lt  ii    i            for  var j   0  jj   this col count  j  lt  jj    j                var node   this nodes i  j                  path   new Path                path push node               this dfs search path                     Board prototype on board   function row  col        return 0  lt   row  amp  amp  row  lt  this row count  amp  amp  0  lt   col  amp  amp  col  lt  this col count    Board prototype get unsearched neighbours   function path        var last node   path nodes path nodes length - 1       var offsets              -1  -1    -1   0    -1   1            0  -1               0   1            1  -1     1   0     1   1             var neighbours           for  var i   0  ii   offsets length  i  lt  ii    i            var offset   offsets i          if  this on board last node row   offset 0   last node col   offset 1                   var potential node   this nodes last node row   offset 0   last node col   offset 1               if   path contains potential node                        Create a new path if on board and we haven t visited this node yet                  neighbours push potential node                                     return neighbours    Board prototype dfs search   function path        var path word   path to word        if  this dict contains exact path word   amp  amp  path word length  gt   3            this words push path word             var neighbours   this get unsearched neighbours path       for  var i   0  ii   neighbours length  i  lt  ii    i            var neighbour   neighbours i          var new path   path clone           new path push neighbour           if  this dict contains prefix new path to word                   this dfs search new path                     var Dict   function         this dict array           var dict data   fs readFileSync    web2    utf8       var dict array   dict data split   n        for  var i   0  ii   dict array length  i  lt  ii    i            dict array i    dict array i  toUpperCase              this dict array   dict array sort      Dict prototype contains prefix   function prefix           Binary search     return this search prefix prefix  0  this dict array length     Dict prototype contains exact   function exact           Binary search     return this search exact exact  0  this dict array length     Dict prototype search prefix   function prefix  start  end        if  start  gt   end               If no more place to search  return no matter what          return this dict array start  indexOf prefix   gt  -1            var middle   Math floor  start   end  2       if  this dict array middle  indexOf prefix   gt  -1               If we prefix exists  return true          return true       else              Recurse         if  prefix  lt   this dict array middle                 return this search prefix prefix  start  middle - 1            else               return this search prefix prefix  middle   1  end                     Dict prototype search exact   function exact  start  end        if  start  gt   end               If no more place to search  return no matter what          return this dict array start      exact            var middle   Math floor  start   end  2       if  this dict array middle      exact               If we prefix exists  return true          return true       else              Recurse         if  exact  lt   this dict array middle                 return this search exact exact  start  middle - 1            else               return this search exact exact  middle   1  end                     var board           F    X    I    E         A    M    L    O         E    W    B    X         A    S    T    U      var dict   new Dict    var b   Board from raw board  dict  b update potential words   console log JSON stringify b words sort function a  b        return a length - b length

User · Answer

This solution also gives the direction to search in the given board  Algo   1  Uses trie to save all the word in the english to fasten the search 2  The uses DFS to search the words in Boggle   Output   Found  pic  directions from  4 0  p  go      Found  pick  directions from  4 0  p  go        Found  pickman  directions from  4 0  p  go              Found  picket  directions from  4 0  p  go            Found  picked  directions from  4 0  p  go            Found  pickle  directions from  4 0  p  go              Code   from collections import defaultdict from nltk corpus import words from nltk corpus import stopwords from nltk tokenize import word tokenize  english words   words words      If you wan to remove stop words   stop words   set stopwords words  english      english words    w for w in english words if w not in stop words   boggle           c    n    t    s    s          d    a    t    i    n          o    o    m    e    l          s    i    k    n    d          p    i    c    l    e        Instead of X and Y co-ordinates   better to use Row and column lenc   len boggle 0   lenr   len boggle     Initialize trie datastructure trie node     valid   False   next          lets get the delta to find all the nighbors neighbors delta          -1 -1             -1  0             -1  1             0  -1             0   1             1  -1             1   0             1   1            def gen trie word  node          udpates the trie datastructure using the given word        if not word          return      if word 0  not in node          node word 0       valid   len word     1   next              recursively build trie     gen trie word 1    node word 0      def build trie words  trie          Builds trie data structure from the list of words given        for word in words          gen trie word  trie      return trie   def get neighbors r  c          Returns the neighbors for a given co-ordinates        n          for neigh in neighbors delta          new r   r   neigh 0          new c   c   neigh 1           if  new r  gt   lenr  or  new c  gt   lenc  or  new r  lt  0  or  new c  lt  0               continue         n append  new r  new c  neigh 2        return n   def dfs r  c  visited  trie  now word  direction          Scan the graph using DFS        if  r  c  in visited          return      letter   boggle r  c      visited append  r  c        if letter in trie          now word    letter          if trie letter   valid                print  Found          format now word  direction            neighbors   get neighbors r  c          for n in neighbors              dfs n 0   n 1   visited      trie letter   now word  direction         n 2     def main trie node          Initiate the search for words in boggle        trie node   build trie english words  trie node         print the board     print  Given board       for i in range lenr  print  boggle i       print    n        for r in range lenr           for c in range lenc               letter   boggle r  c              dfs r  c      trie node       directions from             go   format r  c  letter     if   name         main         main trie node

User · Answer

How about simple sorting and using the binary search in the dictionary   Returns whole list in 0 35 sec and can be further optimized  by for instance removing words with unused letters etc     from bisect import bisect left  f   open  dict txt   D extend  line strip   for line in f readlines     D   sorted D   def neibs M x y       n   len M      for i in xrange -1 2           for j in xrange -1 2               if  i    0 and j    0  or  x   i  lt  0 or x   i  gt   n or y   j  lt  0 or y   j  gt   n                   continue             yield  x   i  y   j   def findWords M D x y prefix       prefix   prefix   M x  y         find word in dict by binary search     found   bisect left D prefix         if found then yield     if D found     prefix           yield prefix        if what we found is not even a prefix then return        there is no point in going further      if len D found    lt  len prefix  or D found   len prefix      prefix          return        recourse     for neib in neibs M x y           for word in findWords M D neib 0   neib 1   prefix               yield word  def solve M D         check each starting point     for x in xrange 0 len M            for y in xrange 0 len M                for word in findWords M D x y                      yield word  grid    fxie amlo ewbx astu  split   print  x for x in solve grid D

User · Answer

I d have to give more thought to a complete solution  but as a handy optimisation  I wonder whether it might be worth pre-computing a table of frequencies of digrams and trigrams  2- and 3-letter combinations  based on all the words from your dictionary  and use this to prioritise your search  I d go with the starting letters of words  So if your dictionary contained the words  India    Water    Extreme   and  Extraordinary   then your pre-computed table might be    IN   1  WA   1  EX   2   Then search for these digrams in the order of commonality  first EX  then WA IN

User · Answer

I have solved this in C   using a DFA algorithm  You can check out my code at  https   github com attilabicsko wordshuffler   In addition to finding words in a matrix  my algorithm saves the actual paths for the words  so for designing a word finder game  you can check wether there is a word on an actual path

User · Answer

Surprisingly  no one attempted a PHP version of this   This is a working PHP version of John Fouhy s Python solution   Although I took some pointers from everyone else s answers  this is mostly copied from John     boggle    fxie            amlo            ewbx            astu     alphabet   str split str replace array   n          r        strtolower  boggle      rows   array map  trim   explode   n    boggle     dictionary   file  C  dict txt     prefixes   array     gt       words   array     regex          implode      alphabet       3    S   foreach  dictionary as  k  gt  value         value   trim strtolower  value         length   strlen  value       if preg match  regex   value             for  x   0   x  lt   length   x                   letter   substr  value  0   x 1               if  letter     value                     words  value    1                else                    prefixes  letter    1                                    graph   array     chardict   array     positions   array     c   count  rows   for  i   0   i  lt   c   i           l   strlen  rows  i        for  j   0   j  lt   l   j               chardict  i      j     rows  i   j            children   array             pos   array -1 0 1           foreach  pos as  z                 xCoord    z    i              if  xCoord  lt  0     xCoord  gt   count  rows                     continue                             len   strlen  rows 0                foreach  pos as  w                     yCoord    j    w                  if   yCoord  lt  0     yCoord  gt    len       z    0  amp  amp   w    0                         continue                                     children     array  xCoord   yCoord                                    graph  None       array  i   j            graph  i      j     children           function to word  chardict   prefix         word   array        foreach  prefix as  v             word      chardict  v 0       v 1              return implode      word      function find words  graph   chardict   position   prefix   prefixes   amp  results   words         word   to word  chardict   prefix       if  isset  prefixes  word    return false       if isset  words  word               results      word             foreach  graph  position  as  child            if  in array  child   prefix                  newprefix    prefix               newprefix      child              find words  graph   chardict   child 0       child 1    newprefix   prefixes   results   words                       solution   array    find words  graph   chardict   None   array     prefixes   solution   print r  solution     Here is a live link if you want to try it out  Although it takes  2s in my local machine  it takes  5s on my webserver  In either case  it is not very fast   Still  though  it is quite hideous so I can imagine the time can be reduced significantly  Any pointers on how to accomplish that would be appreciated  PHP s lack of tuples made the coordinates weird to work with and my inability to comprehend just what the hell is going on didn t help at all   EDIT  A few fixes make it take less than 1s locally

User · Answer

I solved this perfectly and very fast  I put it into an android app  View the video at the play store link to see it in action    Word Cheats is an app that  cracks  any matrix style word game  This app was built to to help me cheat at word scrambler  It can be used for word searches  ruzzle  words  word finder  word crack  boggle  and more   It can be seen here https   play google com store apps details id com harris wordcracker  View the app in action in the video https   www youtube com watch v DL2974WmNAI

User · Answer

Hilarious  I nearly posted the same question a few days ago due to the same damn game  I did not however because just searched google for boggle solver python and got all the answers I could want

User · Answer

Given a Boggle board with N rows and M columns  let s assume the following    N M is substantially greater than the number of possible words N M is substantially greater than the longest possible word   Under these assumptions  the complexity of this solution is O N M    I think comparing running times for this one example board in many ways misses the point but  for the sake of completeness  this solution completes in  lt 0 2s on my modern MacBook Pro   This solution will find all possible paths for each word in the corpus      usr bin env ruby   Example usage    boggle-solver --board  fxie amlo ewbx astu   autoload  Matrix   matrix  autoload  OptionParser   optparse   DEFAULT CORPUS PATH     usr share dict words  freeze    Functions  def filter corpus matrix  corpus  min word length    board char counts   Hash new 0    matrix each    c  board char counts c     1      max word length   matrix row count   matrix column count   boggleable regex        board char counts keys reduce         min word length    max word length       corpus select   w  w match boggleable regex   select do  w      word char counts   Hash new 0      w each char    c  word char counts c     1       word char counts all     c  count  board char counts c   gt   count     end end  def neighbors point  matrix    i  j   point     i-1  0  max     i 1  matrix row count-1  min  inject     do  r  new i        j-1  0  max     j 1  matrix column count-1  min  inject r  do  r  new j        neighbor    new i  new j        neighbor eql  point    r   r  lt  lt  neighbor     end   end end  def expand path path  word  matrix    return  path  if path length    word length    next char   word path length    viable neighbors   neighbors path -1   matrix  select do  point       path include  point   amp  amp  matrix element  point  eql  next char    end    viable neighbors inject     do  result  point      result   expand path path dup  lt  lt  point  word  matrix    end end  def find paths word  matrix    result        matrix each with index do  c  i  j      result    expand path   i  j    word  matrix  if c eql  word 0     end   result end  def solve matrix  corpus  min word length  3    boggleable corpus   filter corpus matrix  corpus  min word length    boggleable corpus inject     do  result  w      paths   find paths w  matrix      result w    paths unless paths empty      result   end end    Script  options     corpus path  DEFAULT CORPUS PATH   option parser   OptionParser new do  opts    opts banner    Usage  boggle-solver --board  lt value gt   --corpus  lt value gt       opts on  --board BOARD   String   The board  e g   fxi aml ewb ast     do  b      options  board    b   end    opts on  --corpus CORPUS PATH   String   Corpus file path   do  c      options  corpus path    c   end    opts on tail  -h    --help    Shows usage   do     STDOUT puts opts     exit   end end option parser parse   unless options  board    STDERR puts option parser   exit false end  unless File file  options  corpus path    STDERR puts  No corpus exists -   options  corpus path      exit false end  rows   options  board  downcase scan   S    map   row  row scan         raw corpus   File readlines options  corpus path   corpus   raw corpus map   w  w downcase rstrip   uniq sort  solution   solve Matrix rows rows   corpus  solution each pair do  w  paths    STDOUT puts w   paths each do  path      STDOUT puts   t    path map   point  point inspect   join         end end STDOUT puts  TOTAL    solution count

User · Answer

package ProblemSolving   import java util HashSet  import java util Set          Given a 2-dimensional array of characters and a    dictionary in which a word can be searched in O 1  time     Need to print all the words from array which are present    in dictionary  Word can be formed in any direction but    has to end at any edge of array      Need not worry much about the dictionary      public class DictionaryWord       private static char     matrix   new char                    a    f    h    u    n                  e    t    a    i    r                  a    e    g    g    o                  t    r    m    l    p              private static int dim x   matrix length      private static int dim y   matrix matrix length -1  length      private static Set lt String gt  wordSet   new HashSet lt String gt          public static void main String   args              dictionary         wordSet add  after            wordSet add  hate            wordSet add  hair            wordSet add  air            wordSet add  eat            wordSet add  tea             for  int x   0  x  lt  dim x  x                  for  int y   0  y  lt  dim y  y                      checkAndPrint matrix x  y                         int     visitedMap   new int dim x  dim y                   visitedMap x  y    1                  recursion matrix x  y        visitedMap  x  y                                      private static void checkAndPrint String word            if  wordSet contains word                 System out println word                        private static void recursion String word  int     visitedMap  int x  int y            for  int i   Math max x - 1  0   i  lt  Math min x   2  dim x   i                  for  int j   Math max y - 1  0   j  lt  Math min y   2  dim y   j                      if  visitedMap i  j     1                        continue                    else                       int     newVisitedMap   new int dim x  dim y                       for  int p   0  p  lt  dim x  p                              for  int q   0  q  lt  dim y  q                                 newVisitedMap p  q    visitedMap p  q                                                                       newVisitedMap i  j    1                      checkAndPrint word   matrix i  j                        recursion word   matrix i  j   newVisitedMap  i  j

User · Answer

For a dictionary speedup  there is one general transformation process you can do to greatly reduce the dictionary comparisons ahead of time    Given that the above grid contains only 16 characters  some of them duplicate  you can greatly reduce the number of total keys in your dictionary by simply filtering out entries that have unattainable characters    I thought this was the obvious optimization but seeing nobody did it I m mentioning it    It reduced me from a dictionary of 200 000 keys to only 2 000 keys simply during the input pass  This at the very least reduces memory overhead  and that s sure to map to a speed increase somewhere as memory isn t infinitely fast    Perl Implementation  My implementation is a bit top-heavy because I placed importance on being able to know the exact path of every extracted string  not just the validity therein    I also have a few adaptions in there that would theoretically permit a grid with holes in it to function  and grids with different sized lines   assuming you get the input right and it lines up somehow      The early-filter is by far the most significant bottleneck in my application  as suspected earlier  commenting out that line bloats it from 1 5s to 7 5s    Upon execution it appears to think all the single digits are on their own valid words   but I m pretty sure thats due to how the dictionary file works    Its a bit bloated  but at least I reuse Tree  Trie from cpan  Some of it was inspired partially by the existing implementations  some of it I had in mind already    Constructive Criticism and ways it could be improved welcome    me notes he never searched CPAN for a boggle solver  but this was more fun to work out     updated for new criteria     usr bin perl   use strict  use warnings          this package manages a given path through the grid      Its an array of matrix-nodes in-order with     Convenience functions for pretty-printing the paths     and for extending paths as new paths       Usage      my  p   Prefix- gt new path  gt    startnode         my  c    p- gt child   extensionNode        print  c- gt current word      package Prefix    use Moose     has path   gt          isa       gt   ArrayRef MatrixNode          is        gt   rw         default   gt  sub                has current word   gt          isa          gt   Str         is           gt   rw         lazy build   gt  1            Create a clone of this object     with a longer path       o- gt child   successive-node-on-graph       sub child         my  self      shift        my  newNode   shift        my  f         Prefix- gt new             Have to do this manually or other recorded paths get modified       push     f- gt  path         self- gt  path      newNode        return  f           Traverses  o- gt path left-to-right to get the string it represents     sub  build current word         my  self   shift        return join q    map     - gt  value        self- gt  path              Returns  the rightmost node on this path    sub tail         my  self   shift        return  self- gt  path - gt  -1            pretty-format  o- gt path    sub pp path         my  self   shift        my  path           map           - gt  x position            - gt  y position                      self- gt  path           return       join        path                   pretty-format  o   sub pp         my  self   shift        return  self- gt current word       gt       self- gt pp path           PACKAGE  - gt meta- gt make immutable            Basic package for tracking node data     without having to look on the grid      I could have just used an array or a hash  but that got ugly     Once the matrix is up and running it doesn t really care so much about rows columns    Its just a sea of points and each point has adjacent points    Relative positioning is only really useful to map it back to userspace    package MatrixNode    use Moose     has x position   gt    isa   gt   Int   is   gt   rw   required   gt  1      has y position   gt    isa   gt   Int   is   gt   rw   required   gt  1      has value        gt    isa   gt   Str   is   gt   rw   required   gt  1      has siblings     gt          isa       gt   ArrayRef MatrixNode          is        gt   rw         default   gt  sub                Its not implicitly uni-directional joins  It would be more effient in therory   to make the link go both ways at the same time  but thats too hard to program around    and besides  this isn t slow enough to bother caring about     sub add sibling         my  self      shift        my  sibling   shift        push     self- gt siblings     sibling           Convenience method to derive a path starting at this node    sub to path         my  self   shift        return Prefix- gt new  path   gt    self             PACKAGE  - gt meta- gt make immutable           package Matrix    use Moose     has rows   gt          isa       gt   ArrayRef         is        gt   rw         default   gt  sub                 has regex   gt          isa          gt   Regexp         is           gt   rw         lazy build   gt  1          has cells   gt          isa          gt   ArrayRef         is           gt   rw         lazy build   gt  1          sub add row         my  self   shift        push     self- gt rows                   Most of these functions from here down are just builder functions      or utilities to help build things      Some just broken out to make it easier for me to process      All thats really useful is add row     The rest will generally be computed  stored  and ready to go     from - gt cells by the time either - gt cells or - gt regex are called       traverse all cells and make a regex that covers them    sub  build regex         my  self    shift        my  chars   q          for my  cell       self- gt cells                  chars     cell- gt value                   chars       chars          return qr  chars i           convert a plain cell   ie   x  y    0       to an intelligent cell ie   x  y    object  x  y       we only really keep them in this format temporarily     so we can go through and tie in neighbouring information      after the neigbouring is done  the grid should be considered inoperative     sub  convert         my  self   shift        my  x      shift        my  y      shift        my  v       self- gt  read   x   y          my  n      MatrixNode- gt new            x position   gt   x            y position   gt   y            value        gt   v                  self- gt  write   x   y   n          return  n         go through the rows collums presently available and freeze them into objects     sub  build cells         my  self   shift        my  out              my  rows       self- gt  rows           for my  x   0      rows               next unless defined  self- gt  rows - gt   x             my  col       self- gt  rows - gt   x               for my  y   0      col                   next unless defined  self- gt  rows - gt   x - gt   y                 push  out   self- gt  convert   x   y                              for my  c   out              for my  n    self- gt  neighbours   c- gt x position   c- gt y position                      c- gt add sibling   self- gt  rows - gt    n- gt  0   - gt    n- gt  1                                 return   out           given x y   return array of points that refer to valid neighbours    sub  neighbours         my  self   shift        my  x      shift        my  y      shift        my  out              for my  sx   -1  0  1               next if  sx    x  lt  0            next if not defined  self- gt  rows - gt    sx    x              for my  sy   -1  0  1                   next if  sx    0  amp  amp   sy    0                next if  sy    y  lt  0                next if not defined  self- gt  rows - gt    sx    x  - gt    sy    y                  push  out     sx    x   sy    y                              return  out         sub  has row         my  self   shift        my  x      shift        return defined  self- gt  rows - gt   x          sub  has cell         my  self   shift        my  x      shift        my  y      shift        return defined  self- gt  rows - gt   x - gt   y          sub  read         my  self   shift        my  x      shift        my  y      shift        return  self- gt  rows - gt   x - gt   y          sub  write         my  self   shift        my  x      shift        my  y      shift        my  v      shift         self- gt  rows - gt   x - gt   y     v        return  v           PACKAGE  - gt meta- gt make immutable     use Tree  Trie   sub readDict     my  fn   shift    my  re   shift    my  d    Tree  Trie- gt new         Dictionary Loading   open my  fh    lt     fn    while   my  line    lt  fh gt            chomp  line       Commenting the next line makes it go from 1 5 seconds to 7 5 seconds  EPIC        next if  line     re       Early Filter        d- gt add  uc  line           return  d     sub traverseGraph     my  d       shift    my  m       shift    my  min     shift    my  max     shift    my  words            Inject all grid nodes into the processing queue     my  queue       grep    d- gt lookup    - gt current word         map      - gt to path       m- gt cells       while   queue          my  item   shift  queue           put the dictionary into  exact match  mode          d- gt deepsearch  exact           my  cword    item- gt current word        my  l       length  cword          if    l  gt    min  amp  amp   d- gt lookup  cword                push  words               item       push current path into  words  if it exactly matches                next if  l  gt   max           put the dictionary into  is-a-prefix  mode         d- gt deepsearch  boolean         siblingloop  foreach my  sibling       item- gt tail- gt siblings                 foreach my  visited       item- gt  path                      next siblingloop if  sibling     visited                           given path y   iterate for all its end points           my  subpath    item- gt child  sibling                create a new path for each end-point           if    d- gt lookup   subpath- gt current word                       if the new path is a prefix  add it to the bottom of the queue                push  queue   subpath                            return   words     sub setup predetermined      my  m   shift     my  gameNo   shift    if   gameNo    0           m- gt add row qw  F X I E            m- gt add row qw  A M L O            m- gt add row qw  E W B X            m- gt add row qw  A S T U           return  m        if   gameNo    1           m- gt add row qw  D G H I            m- gt add row qw  K L P S            m- gt add row qw  Y E U T            m- gt add row qw  E O R N           return  m        sub setup random      my  m   shift     my  seed   shift    srand  seed    my  letters    A      Z       for  1    4           my  r             for  1    4              push  r    letters int rand 25                    m- gt add row   r             Here is where the real work starts   my  m   Matrix- gt new    setup predetermined   m  0     setup random   m  5     my  d   readDict   dict txt    m- gt regex    my  c   scalar     m- gt cells         get the max  as per spec  print join    n   map     - gt pp        traverseGraph   d   m  3   c          Arch execution info for comparison   model name        Intel R  Core TM 2 Duo CPU     T9300    2 50GHz cache size        6144 KB Memory usage summary  heap total  77057577  heap peak  11446200  stack peak  26448        total calls   total memory   failed calls  malloc      947212       68763684              0 realloc       11191        1045641              0   nomove 9063  dec 4731  free 0   calloc      121001        7248252              0    free      973159       65854762  Histogram for block sizes    0-15         392633  36                                                      16-31          43530   4         32-47          50048   4          48-63          70701   6             64-79          18831   1      80-95          19271   1      96-111        238398  22                                 112-127          3007   lt 1   128-143        236727  21                                   More Mumblings on that Regex Optimization  The regex optimization I use is useless for multi-solve dictionaries  and for multi-solve you ll want a full dictionary  not a pre-trimmed one    However  that said  for one-off solves  its really fast    Perl regex are in C         Here is some varying code additions     sub readDict nofilter     my  fn   shift    my  re   shift    my  d    Tree  Trie- gt new         Dictionary Loading   open my  fh    lt     fn    while   my  line    lt  fh gt            chomp  line          d- gt add  uc  line           return  d     sub benchmark io      use Benchmark qw  cmpthese  hireswallclock         generate a random 16 character string       to simulate there being an input grid     my  regexen   sub          my  letters    A      Z           my  lo             for  1  16               push  lo                       my  c    join      lo         c       c          return qr  c i         cmpthese  200            filtered   gt  sub              readDict  dict txt    regexen- gt                       unfiltered   gt  sub             readDict nofilter  dict txt                                  s iter unfiltered   filtered unfiltered   8 16         --       -94  filtered    0 464      1658          --   ps  8 16   200   27 minutes

User · Answer

First  read how one of the C  language designers solved a related problem   http   blogs msdn com ericlippert archive 2009 02 04 a-nasality-talisman-for-the-sultana-analyst aspx   Like him  you can start with a dictionary and the canonacalize words by creating a dictionary from an array of letters sorted alphabetically to a list of words that can be spelled from those letters    Next  start creating the possible words from the board and looking them up  I suspect that will get you pretty far  but there are certainly more tricks that might speed things up

User · Answer

I know I m super late but I made one of these a while ago in PHP - just for fun too     http   www lostsockdesign com au sandbox boggle index php letters fxieamloewbxastu Found 75 words  133 pts  in 0 90108 seconds  F         X  I              E                A                                      M                              L                            O                                E                    W                            B                          X A                  S                                                  T                 U      Gives some indication of what the program is actually doing - each letter is where it starts looking through the patterns while each     shows a path that it has tried to take  The more     there are the further it has searched   Let me know if you want the code    it is a horrible mix of PHP and HTML that was never meant to see the light of day so I dare not post it here  P

[algorithm] How to find list of possible words from a letter matrix [Boggle Solver]

gineer.bogglesolver.Main

gineer.bogglesolver.Solver

gineer.bogglesolver.trie.Node

gineer.bogglesolver.trie.Trie

gineer.bogglesolver.util.Constants

gineer.bogglesolver.util.Util

Examples related to algorithm

Examples related to puzzle

Examples related to boggle