#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

my ($rand, $minus);

sub maybe_visited {
    my ($visited, $x, $y) = @_;
    ++$visited->{"$x:$y"} if $x >= 0 && $y >= 0
                          && $x <= 3 && $y <= 3
                          && $x == int $x
                          && $y == int $y;
    return ($visited->{"$x:$y"} // 0) < 2
}


sub gcd {
    my ($x, $y) = @_;
    ($x, $y) = ($y, $x) if $y < $x;
    ($x, $y) = ($y % $x, $x) while $x;
    return $y
}

sub check {
    my @chain = @_;
    my %visited;
    for my $i (1 .. $#chain) {
        my ($from, $to) = @chain[ $i - 1, $i ];
        return if "@$from" eq "@$to";

        my $x = abs($from->[0] - $to->[0]);
        my $y = abs($from->[1] - $to->[1]);

        my $g = gcd($x, $y);
        my $step_x = $x / $g;
        $step_x *= -1 if $from->[0] > $to->[0];
        my $step_y = $y / $g;
        $step_y *= -1 if $from->[1] > $to->[1];
        my ($X, $Y) = @$from;
        while ($X != $to->[0] || $Y != $to->[1]) {
            maybe_visited(\%visited, $X, $Y) or return;
            $X += $step_x;
            $Y += $step_y;
        }
    }
    maybe_visited(\%visited, @{ $chain[-1] }) or return;
    say scalar keys %visited, ': ',
        join ', ', map "[$_->[0], $_->[1]]", @chain
        if keys %visited > 14;
    return 16 == keys %visited
}

sub generate {
    my @g = map [ int(rand($rand) - $minus),
                  int(rand($rand) - $minus) ],
                1 .. 7;
    for (1 .. 1 + int rand 3) {
        $g[int rand @g][0] = (-1, 4, 5)[int rand 3];
    }
    return @g
}


my ($from, $to) = (0, 3);
$rand = $to - $from + 2;
$minus = 1 - $from;

1 until check(my @chain = generate());
[download]

The solution:

[3, 2], [1, 0], [5, 0], [-1, 3], [3, 3], [0, 0], [0, 2]
[download]