0
$\begingroup$

I saw the entry Solving word search puzzles and I wonder if it is possible to:

  1. Search for words that exist not only in diagonals but that turn like a snake (left, right, up, down)?

  2. Search for all the possible words in the matrix that exist in a known dictionary?

I am trying to understand the solutions given there, I always wish there were more explanations in the solutions for those of us that are not really savvy.

$\endgroup$
  • $\begingroup$ Perhaps I'm just not clever enough, but I think the combinatorics of what you propose are likely to be intractable. If I'm right about that, the solution would have to take an AI approach, which would make it too broad a topic for this site. $\endgroup$ – m_goldberg Jun 8 '17 at 13:56
  • 1
    $\begingroup$ Have you seen How can I use Mathematica's graph functions to cheat at Boggle? $\endgroup$ – Mr.Wizard Jun 8 '17 at 14:10
  • $\begingroup$ Thank you. Yes, i saw The Boggle post and that is the one I referred to. I understand the answer about using AI. What about the second question? Checking whether words in a (small) dictionary can be hidden in the graph? Suppose the small dictionary is a list with words (mathematica, chair, ... <<50>> table). $\endgroup$ – JSP Jun 8 '17 at 14:51
  • $\begingroup$ Here is an outline of a possible solution: 1) Make a grid graph of the word matrix. 2) Find all simple paths. 3) Make a prefix tree of the paths. 4) Using the paths prefix tree try to match prefixes in a given dictionary, and 4.1) when a non-matching prefix is found drop the corresponding tree branch. 5) Proceed with 4) until only dictionary-valid root-to-leaf paths are in the tree. $\endgroup$ – Anton Antonov Jun 8 '17 at 15:21
  • $\begingroup$ #Anton Antonov I have made a grid graph of the matrix but I do not know how to find a simple path. I have read in the Help about Path but I cannot imagine that you are suggesting that I should draw by hand all the small arrows between all adjacent cells!? Of course not, but would you please give me a pointer on how to start fetching all the simple paths. Thank you. $\endgroup$ – JSP Jun 8 '17 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.