It's really simple to write a quick algorithm. I whipped up the program below in about 15 minutes. It's doing the preprocessing of the dictionary for valid prefixes each time - it would be better if you do the preprocessing for prefixes (and valid words) once, using a tied hash and a dbmfile.

Anyway, here's the code: 

#!/usr/bin/perl
    
use strict;
use warnings 'all';
        
my $dict = "/usr/share/dict/words";
        
my %prefix;
my %valid;
my %found;
my $board;
     
sub preprocess;
sub init_board;
sub find_words;

preprocess $dict;
init_board;
 
foreach my $x (0 .. @$board - 1) {
    foreach my $y (0 .. @{$board -> [$x]}) {
        find_words $x, $y, "", [];
    }
}
    
                  
                 
sub preprocess {
    my $file = shift;
    open my $fh => $file or die "Failed to open $file: $!\n";
    local $_;
  LINE:
    while (<$fh>) {
        chomp;
        $_ = lc;
        next if /[^a-z]/;
        $valid {$_} = 1;
        while (length) {
            next LINE if $prefix {$_} ++;
            chop;
        }  
    }
}

     
sub init_board {
    local $_;  
    push @$board => [lc =~ /[a-z]/g] while <DATA>;
}


sub find_words {
    my ($x, $y, $word, $seen) = @_;
    
    return unless $x >= 0 && $y >= 0 &&
                  exists $board -> [$x] && exists $board -> [$x] [$y] 
+&&
                 !$seen -> [$x] [$y];
    
    $word .= $board -> [$x] [$y];
                 
    return unless $prefix {$word};
    
    print "$word\n" if $valid {$word} && !$found {$word} ++; 
    
    $seen -> [$x] [$y] = 1;
        
    foreach my $dx (-1 .. 1) {
        foreach my $dy (-1 .. 1) {
            find_words $x + $dx, $y + $dy, $word, $seen if $dx || $dy;
        }
    }
}
           
     
__DATA__
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y

[download]
Running this gives: 
bag
chide
fag
gab
hi
hid
hide
him
hint
in
mid
no
to
ton
tons
up
It finds the words in just over a second and a half. And a small test shows it will work on non rectangular boards as well. And it's real easy to make it work on a torus.

Abigail

In reply to Re: Depth First Search and Boggle by Abigail-II
in thread Depth First Search and Boggle by smgfc

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.