# Requires the Heap::Fibonacci module from www.perl.com/CPAN/modules/by-module/Heap

# $final_position = branch_and_bound( $start_position )
sub branch_and_bound {
    my $position;

    use Heap::Fibonacci;

    my $positions = Heap::Fibonacci->new;

    $positions->add( shift );

    while ( $position = $positions->extract_minimum ) ) {
        return $position if $position->is_answer;

        # That wasn't the answer.
        # So, try each position that can be reached from here.
        $position->prepare_moves;
        my $move;
        while ( $move = $position->next_move ) {
            $positions->add( $position->make_move($move) );
        }
    }
    # No answer found.
    return undef;
}