#!/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