All right, so now I've got a bitmap for tracking the path I've taken on the board, and I've got a trie that can determine whether or not a sequence of letters is a word (or the prefix of a word) from a specified dictionary.
Let's solve Boggle™.
A Boggle board is a 4x4 grid where each cell is filled with one of sixteen dice. Each die has a letter. Our objective is to scan the board finding words without ever using the same die twice for a singe word. The typical strategy is to start at a letter and scan its neighbors for patterns that might register in our brains as "a word." We'll use the same technique in our algorithm:
1. Start with a letter
2. Scan one neighbor, creating a two-letter word
3. If that word is a whole word, add it to the solutions list
4. If that word is a prefix of a word in the dictionary
1. Pick a neighbor that we have not visited this scan
2. If there is one, make a three-letter word, and recurse to 3, and so on.
5. Terminate when the "word" is not a prefix of any word or there are no valid neighbors to visit
So we need a structure to contain the word we've scanned, and the Ledger. Let's call it Scanned. The only special thing we need for Scanned is that for every step, it needs to clone the Ledger; that is, we get a new copy of Scanned for each neighboring letter, and recurse down that path with that assembled word. When the search terminates (due to exhaustion of the search space or the failure of the prefix), we will then use the copy of Scanned at this point in the stack to create a new search with the next neighbor, and so forth. This is a standard recursive strategy.
The result looks like this:
<code class="sourceCode rust"><span class="kw">pub</span> <span class="kw">fn</span> solve(&<span class="kw">mut</span> board) -> <span class="dt">Vec</span><<span class="dt">String</span>> <span class="op">{</span>
<span class="kw">let</span> solutions = <span class="dt">Vec</span><string>
<span class="kw">for</span> x <span class="kw">in</span> <span class="dv">0.</span>.mx <span class="op">{</span>
<span class="kw">for</span> y <span class="kw">in</span> <span class="dv">0.</span>.my <span class="op">{</span>
<span class="kw">let</span> <span class="kw">mut</span> possibles = Scanned::new(<span class="st">""</span>.to_string(), <span class="dt">Vec</span>::new());
solveforpos(board, x, y, &<span class="kw">mut</span> possibles, &<span class="kw">mut</span> solutions);
<span class="op">}</span>
<span class="op">}</span>
solutions.sort();
solutions.dedup();
solutions.to_vec()
<span class="op">}</span></code>
Step 2. is solveforpos(), where we implement the recursive strategy. But for one technicality, we could have implemented this as a single function, but for one little detail: The letter 'Q'. There are special rules about Q, and we have to support them, as the kids say, "because English."
<code class="sourceCode rust"><span class="kw">pub</span>(<span class="kw">in</span> <span class="kw">crate</span>) <span class="kw">fn</span> solveforpos(
board: &Board, (x, y): (<span class="dt">isize</span>, <span class="dt">isize</span>),
curr: &<span class="kw">mut</span> Scanned, solutions: &<span class="kw">mut</span> <span class="dt">Vec</span><<span class="dt">String</span>>)
) <span class="op">{</span>
<span class="kw">let</span> c = board.board<span class="op">[</span>x <span class="kw">as</span> <span class="dt">usize</span><span class="op">][</span>y <span class="kw">as</span> <span class="dt">usize</span><span class="op">]</span>;
innersolveforpos(c, board, (x, y), curr, solutions, <span class="cn">false</span>);
<span class="kw">if</span> c == <span class="ch">'q'</span> <span class="op">{</span>
innersolveforpos(<span class="ch">'u'</span>, board, (x, y), curr, solutions, <span class="cn">true</span>);
<span class="op">}</span>
<span class="op">}</span></code>
The innersolveforpos() function checks for word validity, prefix validity, and position validity. Not shown here (but you can find it in the source), the Scanned object actually has the responsibility for adding the letter if the position is valid, and returning a new, longer "maybe-word" (remember, we have to support backtracking in our recursion) and a new, updated path Ledger. So that's where we pass the "skip position check" flag, which in turn lets us put both "Q" (so we catch words like 'sheqel' and 'burqa') and "Qu" letters into our candidate string.
Look above, and you'll see that we add 'qu' blindly whenever we encounter 'q'. This is important. We have to let that happen because we need to continue even if "qe" and "qa" aren't in the candidate list. "Quota" is a real word.
Once we've added the letter(s) and determined that the string we have is the prefix of a word found in the dictionary, we then scan the neighbors and recurse, skipping the current cube. The Ledger makes sure that we don't re-check a letter for a given single search, but by cloning the letter and the candidate we also ensure that the backtracking is done correctly.
<code class="sourceCode rust"><span class="kw">fn</span> innersolveforpos(c: <span class="dt">char</span>, board: &Board, (x, y): (<span class="dt">isize</span>, <span class="dt">isize</span>),
curr: &<span class="kw">mut</span> Scanned, solutions: &<span class="kw">mut</span> <span class="dt">Vec</span><<span class="dt">String</span>>, skip_pos_check: <span class="dt">bool</span>
) <span class="op">{</span>
<span class="kw">match</span> curr.add(c, (x, y), skip_pos_check) <span class="op">{</span>
<span class="cn">None</span> => <span class="kw">return</span>,
<span class="cn">Some</span>(<span class="kw">mut</span> newcurr) => <span class="op">{</span>
<span class="kw">if</span> newcurr.<span class="dv">0.</span>len() > <span class="dv">2</span> && board.words.find(&<span class="kw">mut</span> newcurr.<span class="dv">0.</span>chars()) <span class="op">{</span>
solutions.push(newcurr.<span class="dv">0.</span>to_string());
<span class="op">}</span>
<span class="kw">if</span> !board.words.pref(&<span class="kw">mut</span> newcurr.<span class="dv">0.</span>chars()) <span class="op">{</span>
<span class="kw">return</span>;
<span class="op">}</span>
<span class="kw">for</span> i <span class="kw">in</span> -<span class="dv">1.</span>.=<span class="dv">1</span> <span class="op">{</span>
<span class="kw">for</span> j <span class="kw">in</span> -<span class="dv">1.</span>.=<span class="dv">1</span> <span class="op">{</span>
<span class="kw">if</span> !(i == <span class="dv">0</span> && j == <span class="dv">0</span>) <span class="op">{</span>
<span class="co">// Skip the current block!</span>
<span class="kw">let</span> (nx, ny): (<span class="dt">isize</span>, <span class="dt">isize</span>) = (x <span class="kw">as</span> <span class="dt">isize</span> + i, y <span class="kw">as</span> <span class="dt">isize</span> + j);
<span class="kw">if</span> nx >= <span class="dv">0</span> && nx < board.mx && ny >= <span class="dv">0</span> && ny < board.my <span class="op">{</span>
solveforpos(board, (nx, ny), &<span class="kw">mut</span> newcurr, solutions)
<span class="op">}</span>
<span class="op">}</span>
<span class="op">}</span>
<span class="op">}</span>
<span class="op">}</span>
<span class="op">}</span>
<span class="op">}</span></code>
And that's pretty much how you solve Boggle. According to one source, the total number of Boggle boards out there in (nxm)! (that's the factorial symbol there), or for 4x4 board, 16!, or it would take 20,922,789,888,000 visits to do absolutely every search of the board. Except for one thing: the English language is not random! It's messy, but not random. The fact that many letter combinations cannot actually lead to a real word found in the candidate dictionary means that the vast majority of searches terminate early.
On my laptop, a 4x4 board with all 'e's and a dictionary of 'eee' through 'eeeeeeeeeeeeeeee' takes 5 minutes and 45 seconds to complete. But in practice, the average runtime of a boggle board with this algorithm is barely 1.5 milliseconds.
Which is not too damn bad at all.
Can we go faster? Yes we can.