And here is my solution that walks a trie and the boggle board in parallel. You need to have a dictionary file which is a just list of words, one per line. Then you run the code like:

# To get a random 4x4 board and solve it:
boggle < dictionary
# To get a random board of a different size:
boggle 5 < dictionary
# To use a specific board:
boggle gaut prmr dola esic < dictionary
[download]

An example run on the above sample board finds 229 words plus 20 repeats using the 172823 words in my copy of the enable1 word list.

#!/usr/bin/perl -w
use strict;

$|= 1;

my $width= 4;
my @board;
if(  1 == @ARGV  ) {
    $width= shift @ARGV;
}
if(  @ARGV  ) {
    $width= @ARGV;
    die "Invalid board (@ARGV).\n"
        if  @ARGV != grep /^[a-z]{$width}$/, @ARGV;
    @board= (
        '!', ('!') x $width,
        map( {; '!', /./g } @ARGV ),
        '!', ('!') x $width, '!',
    );
}

my %trie;
my %freq;
my $nWords= 0;
my $nLets= 0;
while( <STDIN> ) {
    chomp;
    $nWords++;
    my $pos= \%trie;
    for my $let ( /./g ) {
        $freq{$let}++;
        $nLets++;
        $pos= $pos->{$let} ||= {};
    }
    undef $pos->{'.'};
}
print "$nWords words added to %trie.\n";

if(  ! @board  ) {
    @board= (
        '!', ('!') x $width,
        map( {; '!', map( randLet(), 1..$width ) } 1..$width ),
        '!', ('!') x $width, '!',
    );
}
my @dir= (  -$width-2, -$width-1, -$width, -1,
            +1, +$width, +$width+1, +$width+2 );
for( 1..$width ) {
    print join ' ', '', @board[ $_*($width+1)+1 .. ($_+1)*($width+1)-1
+ ], $/;
}

my %found;
my $repeats= 0;
for my $start (  grep '!' ne $board[$_], 0..$#board  ) {
    my @used;
    my @pos= $start;
    my @idx;
    my $word= '';
    my @tree= \%trie;
    while( @pos ) {
        my $let= $board[$pos[-1]];
        my $tree= $tree[-1]{$let};
        if(  ! $tree  ) {
            pop @pos;
        } else {
            $used[$pos[-1]]= 1;
            push @tree, $tree;
            push @idx, 0+@dir;
            $word .= $let;
            if(  exists $tree[-1]{'.'}  ) {
                if(  ! $found{$word}++  ) {
                    print 0+keys(%found), " $word\n";
                } else {
                    $repeats++;
                }
            }
        }
        while(  @pos  ) {
            if(  ! $idx[-1]  ) {
                chop $word;
                $used[$pos[-1]]= 0;
                pop @pos;
                pop @idx;
                pop @tree;
            } else {
                my $pos= $pos[-1] + $dir[--$idx[-1]];
                if(  ! $used[$pos]  ) {
                    push @pos, $pos;
                    last;
                }
            }
        }
    }
}
print "plus $repeats repeats\n";

sub randLet
{
    my $cnt= int rand $nLets;
    for( keys %freq ) {
        $cnt -= $freq{$_};
        return $_   if  $cnt < 0;
    }
    die "Impossible";
}
[download]

Update: Removed off-by-one error in counts displayed for found words.

---

---

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! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

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:
	&		&
	<		&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.