function [ tsp_distance, tsp_trip ] = tsp_brute ( distance )

%*****************************************************************************80
%
%% TSP_BRUTE solves the Traveling Salesman Problem.
%
%  Input, DISTANCE(N,N), the distance matrix.
%
%  Output, TSP_DISTANCE, the minimum roundtrip distance.
%
%  Output, TSP_TRIP(N), the sequence of cities on the round trip.
%
  [ n, ~ ] = size ( distance );
  i = 1;

  while ( true )

    if ( i == 1 )
      this_trip = 1 : n;
    else
      this_trip = nextperm ( this_trip );
      if ( isempty ( this_trip ) )
        break;
      end
    end

    this_distance = trip_distance ( distance, this_trip );

    if ( i == 1 || this_distance < tsp_distance )
      tsp_distance = this_distance;
      tsp_trip = this_trip;
    end

    this_trip = nextperm ( this_trip );

    i = i + 1;

  end

  return
end
