1. Start at the first number from the input list.
2. Create two lists: list of visited numbers, and list of the matrix positions to visit.
3. Mark the current number as visited at the current position. If you visited all the input numbers, return true.
4. Check all the neighbouring positions, non-visited ones present in the input list should go to the list of positions to visit.
5. Visit the first position from the list, go to #3.
6. If the list is empty, try starting with the next input number (this is needed, as numbers could be repeated, e.g. 2 in your sample). Go to #2.
7. You tried all the input numbers, but you can't reach all the rest from any of them. Return false.

Which translates easily to Perl:

#! /usr/bin/perl
use warnings;
use strict;

my @matrix = ( [ 1,  2,  3,  4],
               [ 5,  6,  7,  8],
               [ 9, 10, 11, 12],
               [13, 14,  3, 16],
               [ 2, 18, 19, 20],
             );

sub nearby {
    my @input = @_;
    my %numbers;
    undef @numbers{@input};

    for my $y (0 .. $#matrix) {
        for my $x (0 .. $#{ $matrix[$y] }) {
            next unless exists $numbers{ $matrix[$y][$x] };

            my @next = ([$x, $y]);
            my %visited;
            while (@next) {
                my ($r, $s) = @{ shift @next };
                undef $visited{ $matrix[$s][$r] }{"$r $s"};
                return 1 if keys %visited == keys %numbers;

                push @next, grep $_->[0] >= 0 && $_->[1] >= 0
                            && $_->[0] <= $#{ $matrix[$s] } && $_->[1]
+ <= $#matrix
                            && exists $numbers{ $matrix[ $_->[1] ][ $_
+->[0] ] }
                            && ! exists $visited{ $matrix[ $_->[1] ][ 
+$_->[0] ] }{"@$_"},
                        [$r - 1, $s - 1],
                        [$r,     $s - 1],
                        [$r + 1, $s - 1],
                        [$r + 1, $s    ],
                        [$r + 1, $s + 1],
                        [$r,     $s + 1],
                        [$r - 1, $s + 1],
                        [$r - 1, $s    ];
                # warn map "<@$_>", @next;
            }
        }
    }
    return
}

use Test::More;

ok(nearby(2, 7, 12, 16));
ok(nearby(2, 4, 7, 12));
ok(! nearby(1, 6, 8, 12));
ok(! nearby(1, 5, 14, 15));

# Unspecified?
ok(nearby(2, 13, 9, 5, 7));
ok(! nearby(2, 13, 7));
ok(nearby(6, 3, 8, 12, 18));

@matrix = ( [ 1,  1,  1,  1, 2],
            [ 1,  0,  0,  0, 0],
            [ 1,  0,  1,  1, 3],
            [ 1,  0,  1,  0, 0],
            [ 1,  0,  1,  1, 1],
            [ 1,  0,  0,  0, 1],
            [ 1,  1,  1,  1, 1],
          );
ok(nearby(1, 2, 3));

done_testing();
[download]

Update: It's unclear how to handle duplicate numbers. The code returns true for the last case, but did you really want to use 1 several times? Please, clarify your specification.

Update 2: added positions to visited numbers.