q2.pl

use v5.30.0;
use warnings;
use List::Util qw/uniqint shuffle/;

my @segments = ();

for (0..3, 4..7) {
    push @segments, [$_, $_+4, $_+8];
}
for (0,4,8,12, 1,5,9,13) {
    push @segments, [$_, $_+1, $_+2];
}
push @segments, (
    [1,6,11],
    [0,5,10], [5,10,15],
    [4,9,14],
    [2,5,8],
    [3,6,9],[6,9,12],
    [7,10,13]
);

my @r_seg = map {[reverse $_->@*]} @segments;
push @segments, @r_seg;

my @holes = (5);
my @balls = (0..4, 6..15);

sub find_possible_nxt_states {
    my @holes = $_[0]->@*;
    my @balls = $_[1]->@*;
    die "holes and balls ERROR" unless 16 == uniqint (@holes, @balls);
    my @nxt_states;
    
    for my $seg (@segments) {
        if  ((grep {$seg->[0] == $_} @holes)
            && (grep {$seg->[2] == $_} @balls)
            && (grep {$seg->[1] == $_} @balls)
        ) {
            push @nxt_states, step([@holes], [@balls], $seg);
        }
    }

    return [@nxt_states];
    # [
    #    { balls => [], holes => [] },
    #    { balls => [], holes => [] },
    # ]
}

sub step {
    my @holes = $_[0]->@*;
    my @balls = $_[1]->@*;
    my $segment = $_[2];
    push @holes, $segment->[2], $segment->[1];
    @holes = grep {$_ != $segment->[0]} @holes;
    @balls = grep {$_ != $segment->[1] && $_ != $segment->[2]} @balls;
    push @balls, $segment->[0];
    return { balls => [@balls], holes => [@holes], segment => $segment };
}



sub game_tree_traversal {
    my @holes = $_[0]->@*;
    my @balls = $_[1]->@*;
    my @pasts = $_[2]->@*;
    my @nxt_states = find_possible_nxt_states([@holes], [@balls])->@*;
    say $balls[0] 
        if scalar @balls == 1 && $balls[0] == 7;
    do {use Data::Printer; p @pasts; exit;}
        if scalar @balls == 1 && $balls[0] == 7;
    if (scalar @nxt_states == 0) {
        return; 
    }
    for my $nxt_state (shuffle @nxt_states) {
        my @possible_future = @pasts;
        push @possible_future, $nxt_state->{segment};
        game_tree_traversal(
            $nxt_state->{holes}, $nxt_state->{balls}, 
            [@possible_future]
        );
    }
}

game_tree_traversal([@holes], [@balls], []);

=pod
Solve a solution:
real	0m0.625s
user	0m0.621s
sys	0m0.004s

With randomization:
range from 1 sec to 0.038 sec