Databases
StackOverflow2013
Postsdbo
POHow to find list of possible words from a letter matrix [Boggle Solver]
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to find list of possible words from a letter matrix [Boggle Solver]
    primarykey
    data
    text
    <p>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:</p> <pre><code>F X I E A M L O E W B X A S T U </code></pre> <p>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, <strong>except for any previously used letters</strong>. So in the grid above, for example, I could come up with the words <code>LOB</code>, <code>TUX</code>, <code>SEA</code>, <code>FAME</code>, 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).</p> <p><a href="http://www.boggled.org/sample.gif" rel="noreferrer">Sample Boggle http://www.boggled.org/sample.gif</a></p> <p>I am, unfortunately, not very good with algorithms or their efficiencies and so forth. My first attempt uses a dictionary <a href="http://www.freebsd.org/cgi/cvsweb.cgi/src/share/dict/web2?rev=1.12;content-type=text%2Fplain" rel="noreferrer">such as this one</a> (~2.3MB) and does a linear search trying to match combinations with dictionary entries. This takes a <em>very</em> long time to find the possible words, and since you only get 2 minutes per round, it is simply not adequate.</p> <p>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.</p> <p><strong>CURRENT SOLUTIONS</strong>:</p> <ul> <li>Adam Rosenfield, Python, ~20s </li> <li>John Fouhy, Python, ~3s </li> <li>Kent Fredric, Perl, ~1s </li> <li>Darius Bacon, Python, ~1s </li> <li>rvarcher, VB.NET <a href="http://www.myvrad.com/boggle/default.aspx" rel="noreferrer">(live link)</a>, ~1s</li> <li>Paolo Bergantino, PHP <a href="http://www.rootspot.com/stackoverflow/boggle.php" rel="noreferrer">(live link)</a>, ~5s (~2s locally)</li> </ul> <p><strong>BOUNTY</strong>:</p> <p>I am adding a bounty to this question as my way of saying thanks to all the people who pitched in with their programs. Unfortunately I can only give the accepted answer to one of you, so I'll measure who has the fastest boggle solver 7 days from now and award the winner the bounty.</p> <p>Bounty awarded. Thanks to everyone that participated.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USGuy Coder
    1. USPaolo Bergantino
    plurals
    1. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow to find list of possible words from a letter matrix [Boggle Solver]
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHow to find list of possible words from a letter matrix [Boggle Solver]
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHow to find list of possible words from a letter matrix [Boggle Solver]
      1. This table or related slice is empty.
      1. VTUpMod
    1. COA simple solution is the class BoggleFinder http://aima.cs.berkeley.edu/python/search.html
      singulars
      1. POHow to find list of possible words from a letter matrix [Boggle Solver]
      1. USjfs
    2. COWell that's not very fun is it? :)
      singulars
      1. POHow to find list of possible words from a letter matrix [Boggle Solver]
      1. USPaolo Bergantino
    3. COfeature request MOAR PUZZLES
      singulars
      1. POHow to find list of possible words from a letter matrix [Boggle Solver]
      1. USKent Fredric
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload