%% Traveling Salesman Problem, 08/24/2012.
%% All cities connected to every other city, in both directions.
%% Find minimal Hamiltontian path length. Yes, we know this is an np complete problem.
%% tsp2.m is only file required (this one).

				% Environment, including .configure
%% stack limit
%% http://linuxtoosx.blogspot.com/2010/10/stack-overflow-increasing-stack-limit.html

%% See mercury bug fixes, and configuration of mercury for mac in
%% 09/10/2012 emails from julian fischer.
%% http://bugs.mercury.csse.unimelb.edu.au/view.php?id=263

%% User guide for mercury grades: file:///Users/lpimmes/Downloads/mercury-compiler-11.01/doc/mercury_user_guide.html

%% 11.07.2 installed with none.gc.stseg which is required for --grade none.gc.stseg
%% According to mercury documentation (via Julian's email today, 09/10/2012), then stack space
%% is managed dynamically by mercury.
%% cd mercury-compiler-11.07.2/
%% ./configure --with-cc="gcc -m64" --enable-libgrades=hlc.gc,none.gc,none.gc.stseg,java,erlang
%% ...

				% RUN
%% ~ 515>cd $MERCURYPROGRAMS
%% mercuryPrograms 513>cd algor91503/
%% algor91503 512>cd tsp2

%% tsp2 489>ulimit -H -s
%% 65532
%% Cannot set to a higher value.

%% tsp2 489>which mmc
%% /usr/local/mercury-11.07.2/bin/mmc
%% tsp2 489>mmc  --grade none.gc.stseg --fully-strict -E -v -O 0 --use-subdirs tsp2

				% 10! = 3628800
				% 430 m ~= 7 hours, most of the time spent swapping in and out of memory, as timer shows.
%% tsp2 487>time ./tsp2
%% #Permutations: 3628800, Generator length: 10 using [2 3 4 5 6 7 8 9 10 11 ],
%% minimum distance 23: 1_8(2) 8_6(2) 6_5(3) 5_4(1) 4_3(3) 3_9(2) 9_7(1) 7_11(1) 11_2(3) 2_10(3) 10_1(2)

%% real	430m26.708s
%% user	7m36.750s
%% sys	12m29.934s

				% 9! = 362880
%% tsp2 489>./tsp2
%% #Permutations: 362880, Generator length: 9 using [2 3 4 5 6 7 8 9 10 ],
%% minimum distance 23: 1_8(2) 8_6(2) 6_5(3) 5_4(1) 4_3(3) 3_9(2) 9_7(1) 7_2(4) 2_10(3) 10_1(2)

% % real	0m32.049s
% % user	0m30.823s
% % sys	0m1.051s

				% 8! = 40320
%% tsp2 489>./tsp2
%% #Permutations: 40320, Generator length: 8 using [2 3 4 5 6 7 8 9 ],
%% minimum distance 24: 1_5(4) 5_4(1) 4_3(3) 3_9(2) 9_7(1) 7_2(4) 2_6(5) 6_8(2) 8_1(2)


				% 7/! = 5040
%% tsp2 505>./tsp2
%% #Permutations: 5040, Generator length: 7 using [2 3 4 5 6 7 8 ],
%% minimum distance 23: 1_3(5) 3_4(3) 4_5(1) 5_7(1) 7_2(4) 2_6(5) 6_8(2) 8_1(2)
%% tsp2 505>

				% 6! = 720
% tsp2 488>./tsp2
% #Permutations: 720, Generator length: 6 using [2 3 4 5 6 7 ],
% minimum distance 26: 1_3(5) 3_4(3) 4_5(1) 5_7(1) 7_2(4) 2_6(5) 6_1(7)
% tsp2 489>

% Author: Luke P Immes
% Shrewsbury, MA
% USA
% 508 579 2683 (cell)
% lpimmes@townisp.com

%% The complexity issue is generating all solutions from which minimum distance can be obtained.
%% See tsp (same directory as this one) for other approachs which were not needed.

% tsp2 501>pwd
% /Users/lpimmes/Documents/lpimmesOnly/mercuryPrograms/algor91503/tsp2

% tsp2 494>uname -a
% Darwin luke-immess-imac-2.local 11.4.0 Darwin Kernel Version 11.4.0: Mon Apr  9 19:32:15 PDT 2012; root:xnu-1699.26.8~1/RELEASE_X86_64 x86_64

% tsp2 495>mmc -version
% mercury_compile: invalid grade `ion'
% Mercury Compiler, version 11.07.1, configured for x86_64-apple-darwin11.3.0
% Copyright (C) 1993-2012 The University of Melbourne
% Usage: mmc [<options>] <arguments>
% Use `mmc --help' for more information.

% tsp2 496>gcc -version
% i686-apple-darwin9-gcc-4.2.1: no input files
% tsp2 497>

%% OK working, but still using solutions/2, and O(n!) for input size n, see minHamiltPath/2.
%% p(n, r) = n! / (n - r)!    where, in our case n = r, e.g. 6 things permuted 6 ways.
%%            = n! / 0! = n! / 1 = n!

	
%% tsp2 499>pwd
%% /Users/lpimmes/Documents/lpimmesOnly/mercuryPrograms/algor91503/tsp2

%% COMPILE
%% tsp2 495>tsp2.bash

:- module tsp2.			% This file name for now.
:- interface.
:- import_module io.

:- pred main(io, io).	    % main/2 used in interface, so include it!
:- mode main(di, uo) is cc_multi. % committed choice multideterminism- choose first goal that succeeds.
:- implementation.
:- import_module list, string, int, char, bool, solutions. % mercury itself

				% Every city connected to every other city, and in both directions.
				% Just add a new line for each section to increase generator length.
				% Currently our generator will handle 6, or 6! = 720 permutations.
:- pred dist(int, int, int).
:- mode dist(in, in, out) is multi.
% dist(city1, city2, 10)
dist(1, 2, 10). 
dist(1, 3, 5).
dist(1, 4, 9).
dist(1, 5, 4).
dist(1, 6, 7).
dist(1, 7, 6).
dist(1, 8, 2).
dist(1, 9, 5).
dist(1, 10, 2).
dist(1, 11, 4).

dist(2, 3, 6).
dist(2, 4, 9).
dist(2, 5, 8).
dist(2, 6, 5).
dist(2, 7, 4).
dist(2, 8, 9).
dist(2, 9, 8).
dist(2, 10, 3).
dist(2, 11, 3).

dist(3, 4, 3).
dist(3, 5, 2).
dist(3, 6, 6).
dist(3, 7, 5).
dist(3, 8, 5).
dist(3, 9, 2).
dist(3, 10, 4).
dist(3, 11, 5).

dist(4, 5, 1).
dist(4, 6, 7).
dist(4, 7, 2).
dist(4, 8, 8).
dist(4, 9, 7).
dist(4, 10, 5).
dist(4, 11, 3).

dist(5, 6, 3).
dist(5, 7, 1).
dist(5, 8, 7).
dist(5, 9, 9).
dist(5, 10, 6).
dist(5, 11, 3).

dist(6, 7, 8).
dist(6, 8, 2).
dist(6, 9, 3).
dist(6, 10, 7).
dist(6, 11, 8).

dist(7, 8, 7).
dist(7, 9, 1).
dist(7, 10, 8).
dist(7, 11, 1).

dist(8, 9, 6).
dist(8, 10, 9).
dist(8, 11, 2).

dist(9, 10, 10).
dist(9, 11, 2).

dist(10, 11, 9).

dist(A, B, D) :-
	% don't forget symmetry
	dist(B, A, D).

main(In, Out) :-
	%command_line_arguments(WrdsTags, In, Out9),

	(if
	 %% working, but uses solutions/2
	 % Generator is sorted, no duplicates, no gaps, beginning at 2, sorted.
	 % This works, and fairly quickly, but still O(n!) where n is input length here.
	 Generator = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11], % No 1 in front, will put on front and back.
	minLenHamiltPath(Generator, MinHamtPath)
	 
	then
	format("%s\n", [s(MinHamtPath)], In, Out)
	
	 else
	 format("Failed to find minimum Hamiltonian path using given generator.\n", [], In, Out)
	).

% tsp2 489>./tsp2
% #Permutations: 720, Generator length: 6 using [2 3 4 5 6 7 ],
% minimum distance 26: 1_3(5) 3_4(3) 4_5(1) 5_7(1) 7_2(4) 2_6(5) 6_1(7)
% tsp2 489>

:- pred minLenHamiltPath(list(int), string).
:- mode minLenHamiltPath(in, out) is nondet.
minLenHamiltPath(LstGenerator, TotalDistStr) :-
	% LstGenerator is sorted, no duplicates, no gaps, beginning at 2
	solutions(list.perm(LstGenerator), HamiltPaths), % takes n! time, where n means length LstGenerator.
	getMinDist(10000, HamiltPaths, "", DistStr), % initial max is some # we don't expect to exceed
	length(HamiltPaths, LenP), 
	length(LstGenerator, LenG), lstNumDsp(LstGenerator, LsDsp),
	format("#Permutations: %i, Generator length: %i using %s,\nminimum distance %s",
	       [i(LenP), i(LenG), s(LsDsp), s(DistStr)], TotalDistStr).

:- pred getMinDist(int, list(list(int)), string, string).
:- mode getMinDist(in, in, in, out) is nondet.
getMinDist(_, [], Accum, Accum).
getMinDist(Max, [Perm | Perms], Accum, Result) :-
	getDist(Perm, Dist, DistStr),
	(
	 Dist < Max,
	 getMinDist(Dist, Perms, DistStr, Result)
	;
	 getMinDist(Max, Perms, Accum, Result)
	).

:- pred getDist(list(int), int, string).
:- mode getDist(in, out, out) is nondet.
getDist(LstNum, Dist, DistStr) :-
	append(LstNum, [1], L2),
	getDist(1, L2,    0, Dist,     "", DistPath),
	format("%i:%s", [i(Dist), s(DistPath)], DistStr).

:- pred getDist(int, list(int),  int, int,  string, string).
:- mode getDist(in, in,   in, out,   in, out) is nondet.
getDist(_, [],              AccN, AccN,         Accum, Accum).
getDist(D1, [D2 | Ds], AccN, ResultN,     Accum, Result) :-
	dist(D1, D2, D),
	format(" %i_%i(%i)", [i(D1), i(D2), i(D)], Acc),
	getDist(D2, Ds,
		AccN + D, ResultN,
		Accum ++ Acc, Result).

:- pred lstNumDsp(list(int), string).
:- mode lstNumDsp(in, out) is semidet.
lstNumDsp(Lst, R) :-
	lstNumDsp(Lst, "", Result),
	R = "[" ++ Result ++ "]".

:- pred lstNumDsp(list(int), string, string).
:- mode lstNumDsp(in, in, out) is semidet.
lstNumDsp([], Accum, Accum).
lstNumDsp([L | Lst], Accum, Result) :-
	format("%i", [i(L)], A),
	lstNumDsp(Lst, Accum ++ A ++ " ", Result).


				% from tsp
				% tsp 495>./tsp
% Number cities: 6, number subpaths: 120, 
% Distance: 30, 1_2(10) 2_3(6) 3_4(3) 4_5(1) 5_6(3) 6_1(7)
% Distance: 33, 1_2(10) 2_3(6) 3_4(3) 4_6(7) 6_5(3) 5_1(4)
% Distance: 33, 1_2(10) 2_3(6) 3_5(2) 5_4(1) 4_6(7) 6_1(7)
% Distance: 37, 1_2(10) 2_3(6) 3_5(2) 5_6(3) 6_4(7) 4_1(9)
% Distance: 34, 1_2(10) 2_3(6) 3_6(6) 6_4(7) 4_5(1) 5_1(4)
% Distance: 35, 1_2(10) 2_3(6) 3_6(6) 6_5(3) 5_4(1) 4_1(9)
% Distance: 34, 1_2(10) 2_4(9) 4_3(3) 3_5(2) 5_6(3) 6_1(7)
% Distance: 35, 1_2(10) 2_4(9) 4_3(3) 3_6(6) 6_5(3) 5_1(4)
% Distance: 35, 1_2(10) 2_4(9) 4_5(1) 5_3(2) 3_6(6) 6_1(7)
% Distance: 34, 1_2(10) 2_4(9) 4_5(1) 5_6(3) 6_3(6) 3_1(5)
% Distance: 38, 1_2(10) 2_4(9) 4_6(7) 6_3(6) 3_5(2) 5_1(4)
% Distance: 36, 1_2(10) 2_4(9) 4_6(7) 6_5(3) 5_3(2) 3_1(5)
% Distance: 37, 1_2(10) 2_5(8) 5_3(2) 3_4(3) 4_6(7) 6_1(7)
% Distance: 42, 1_2(10) 2_5(8) 5_3(2) 3_6(6) 6_4(7) 4_1(9)
% Distance: 35, 1_2(10) 2_5(8) 5_4(1) 4_3(3) 3_6(6) 6_1(7)
% Distance: 37, 1_2(10) 2_5(8) 5_4(1) 4_6(7) 6_3(6) 3_1(5)
% Distance: 39, 1_2(10) 2_5(8) 5_6(3) 6_3(6) 3_4(3) 4_1(9)
% Distance: 36, 1_2(10) 2_5(8) 5_6(3) 6_4(7) 4_3(3) 3_1(5)
% Distance: 29, 1_2(10) 2_6(5) 6_3(6) 3_4(3) 4_5(1) 5_1(4)
% Distance: 33, 1_2(10) 2_6(5) 6_3(6) 3_5(2) 5_4(1) 4_1(9)
% Distance: 31, 1_2(10) 2_6(5) 6_4(7) 4_3(3) 3_5(2) 5_1(4)
% Distance: 30, 1_2(10) 2_6(5) 6_4(7) 4_5(1) 5_3(2) 3_1(5)
% Distance: 32, 1_2(10) 2_6(5) 6_5(3) 5_3(2) 3_4(3) 4_1(9)
% Distance: 27, 1_2(10) 2_6(5) 6_5(3) 5_4(1) 4_3(3) 3_1(5)
% Distance: 31, 1_3(5) 3_2(6) 2_4(9) 4_5(1) 5_6(3) 6_1(7)
% Distance: 34, 1_3(5) 3_2(6) 2_4(9) 4_6(7) 6_5(3) 5_1(4)
% Distance: 34, 1_3(5) 3_2(6) 2_5(8) 5_4(1) 4_6(7) 6_1(7)
% Distance: 38, 1_3(5) 3_2(6) 2_5(8) 5_6(3) 6_4(7) 4_1(9)
% Distance: 28, 1_3(5) 3_2(6) 2_6(5) 6_4(7) 4_5(1) 5_1(4)
% Distance: 29, 1_3(5) 3_2(6) 2_6(5) 6_5(3) 5_4(1) 4_1(9)
% Distance: 35, 1_3(5) 3_4(3) 4_2(9) 2_5(8) 5_6(3) 6_1(7)
% Distance: 29, 1_3(5) 3_4(3) 4_2(9) 2_6(5) 6_5(3) 5_1(4)
% Distance: 29, 1_3(5) 3_4(3) 4_5(1) 5_2(8) 2_6(5) 6_1(7)
% Distance: 27, 1_3(5) 3_4(3) 4_5(1) 5_6(3) 6_2(5) 2_1(10)
% Distance: 32, 1_3(5) 3_4(3) 4_6(7) 6_2(5) 2_5(8) 5_1(4)
% Distance: 36, 1_3(5) 3_4(3) 4_6(7) 6_5(3) 5_2(8) 2_1(10)
% Distance: 38, 1_3(5) 3_5(2) 5_2(8) 2_4(9) 4_6(7) 6_1(7)
% Distance: 36, 1_3(5) 3_5(2) 5_2(8) 2_6(5) 6_4(7) 4_1(9)
% Distance: 29, 1_3(5) 3_5(2) 5_4(1) 4_2(9) 2_6(5) 6_1(7)
% Distance: 30, 1_3(5) 3_5(2) 5_4(1) 4_6(7) 6_2(5) 2_1(10)
% Distance: 33, 1_3(5) 3_5(2) 5_6(3) 6_2(5) 2_4(9) 4_1(9)
% Distance: 36, 1_3(5) 3_5(2) 5_6(3) 6_4(7) 4_2(9) 2_1(10)
% Distance: 30, 1_3(5) 3_6(6) 6_2(5) 2_4(9) 4_5(1) 5_1(4)
% Distance: 34, 1_3(5) 3_6(6) 6_2(5) 2_5(8) 5_4(1) 4_1(9)
% Distance: 39, 1_3(5) 3_6(6) 6_4(7) 4_2(9) 2_5(8) 5_1(4)
% Distance: 37, 1_3(5) 3_6(6) 6_4(7) 4_5(1) 5_2(8) 2_1(10)
% Distance: 40, 1_3(5) 3_6(6) 6_5(3) 5_2(8) 2_4(9) 4_1(9)
% Distance: 34, 1_3(5) 3_6(6) 6_5(3) 5_4(1) 4_2(9) 2_1(10)
% Distance: 36, 1_4(9) 4_2(9) 2_3(6) 3_5(2) 5_6(3) 6_1(7)
% Distance: 37, 1_4(9) 4_2(9) 2_3(6) 3_6(6) 6_5(3) 5_1(4)
% Distance: 41, 1_4(9) 4_2(9) 2_5(8) 5_3(2) 3_6(6) 6_1(7)
% Distance: 40, 1_4(9) 4_2(9) 2_5(8) 5_6(3) 6_3(6) 3_1(5)
% Distance: 35, 1_4(9) 4_2(9) 2_6(5) 6_3(6) 3_5(2) 5_1(4)
% Distance: 33, 1_4(9) 4_2(9) 2_6(5) 6_5(3) 5_3(2) 3_1(5)
% Distance: 36, 1_4(9) 4_3(3) 3_2(6) 2_5(8) 5_6(3) 6_1(7)
% Distance: 30, 1_4(9) 4_3(3) 3_2(6) 2_6(5) 6_5(3) 5_1(4)
% Distance: 34, 1_4(9) 4_3(3) 3_5(2) 5_2(8) 2_6(5) 6_1(7)
% Distance: 32, 1_4(9) 4_3(3) 3_5(2) 5_6(3) 6_2(5) 2_1(10)
% Distance: 35, 1_4(9) 4_3(3) 3_6(6) 6_2(5) 2_5(8) 5_1(4)
% Distance: 39, 1_4(9) 4_3(3) 3_6(6) 6_5(3) 5_2(8) 2_1(10)
% Distance: 37, 1_4(9) 4_5(1) 5_2(8) 2_3(6) 3_6(6) 6_1(7)
% Distance: 34, 1_4(9) 4_5(1) 5_2(8) 2_6(5) 6_3(6) 3_1(5)
% Distance: 30, 1_4(9) 4_5(1) 5_3(2) 3_2(6) 2_6(5) 6_1(7)
% Distance: 33, 1_4(9) 4_5(1) 5_3(2) 3_6(6) 6_2(5) 2_1(10)
% Distance: 29, 1_4(9) 4_5(1) 5_6(3) 6_2(5) 2_3(6) 3_1(5)
% Distance: 35, 1_4(9) 4_5(1) 5_6(3) 6_3(6) 3_2(6) 2_1(10)
% Distance: 33, 1_4(9) 4_6(7) 6_2(5) 2_3(6) 3_5(2) 5_1(4)
% Distance: 36, 1_4(9) 4_6(7) 6_2(5) 2_5(8) 5_3(2) 3_1(5)
% Distance: 40, 1_4(9) 4_6(7) 6_3(6) 3_2(6) 2_5(8) 5_1(4)
% Distance: 42, 1_4(9) 4_6(7) 6_3(6) 3_5(2) 5_2(8) 2_1(10)
% Distance: 38, 1_4(9) 4_6(7) 6_5(3) 5_2(8) 2_3(6) 3_1(5)
% Distance: 37, 1_4(9) 4_6(7) 6_5(3) 5_3(2) 3_2(6) 2_1(10)
% Distance: 35, 1_5(4) 5_2(8) 2_3(6) 3_4(3) 4_6(7) 6_1(7)
% Distance: 40, 1_5(4) 5_2(8) 2_3(6) 3_6(6) 6_4(7) 4_1(9)
% Distance: 37, 1_5(4) 5_2(8) 2_4(9) 4_3(3) 3_6(6) 6_1(7)
% Distance: 39, 1_5(4) 5_2(8) 2_4(9) 4_6(7) 6_3(6) 3_1(5)
% Distance: 35, 1_5(4) 5_2(8) 2_6(5) 6_3(6) 3_4(3) 4_1(9)
% Distance: 32, 1_5(4) 5_2(8) 2_6(5) 6_4(7) 4_3(3) 3_1(5)
% Distance: 35, 1_5(4) 5_3(2) 3_2(6) 2_4(9) 4_6(7) 6_1(7)
% Distance: 33, 1_5(4) 5_3(2) 3_2(6) 2_6(5) 6_4(7) 4_1(9)
% Distance: 30, 1_5(4) 5_3(2) 3_4(3) 4_2(9) 2_6(5) 6_1(7)
% Distance: 31, 1_5(4) 5_3(2) 3_4(3) 4_6(7) 6_2(5) 2_1(10)
% Distance: 35, 1_5(4) 5_3(2) 3_6(6) 6_2(5) 2_4(9) 4_1(9)
% Distance: 38, 1_5(4) 5_3(2) 3_6(6) 6_4(7) 4_2(9) 2_1(10)
% Distance: 33, 1_5(4) 5_4(1) 4_2(9) 2_3(6) 3_6(6) 6_1(7)
% Distance: 30, 1_5(4) 5_4(1) 4_2(9) 2_6(5) 6_3(6) 3_1(5)
% Distance: 26, 1_5(4) 5_4(1) 4_3(3) 3_2(6) 2_6(5) 6_1(7)
% Distance: 29, 1_5(4) 5_4(1) 4_3(3) 3_6(6) 6_2(5) 2_1(10)
% Distance: 28, 1_5(4) 5_4(1) 4_6(7) 6_2(5) 2_3(6) 3_1(5)
% Distance: 34, 1_5(4) 5_4(1) 4_6(7) 6_3(6) 3_2(6) 2_1(10)
% Distance: 30, 1_5(4) 5_6(3) 6_2(5) 2_3(6) 3_4(3) 4_1(9)
% Distance: 29, 1_5(4) 5_6(3) 6_2(5) 2_4(9) 4_3(3) 3_1(5)
% Distance: 37, 1_5(4) 5_6(3) 6_3(6) 3_2(6) 2_4(9) 4_1(9)
% Distance: 35, 1_5(4) 5_6(3) 6_3(6) 3_4(3) 4_2(9) 2_1(10)
% Distance: 34, 1_5(4) 5_6(3) 6_4(7) 4_2(9) 2_3(6) 3_1(5)
% Distance: 33, 1_5(4) 5_6(3) 6_4(7) 4_3(3) 3_2(6) 2_1(10)
% Distance: 26, 1_6(7) 6_2(5) 2_3(6) 3_4(3) 4_5(1) 5_1(4)
% Distance: 30, 1_6(7) 6_2(5) 2_3(6) 3_5(2) 5_4(1) 4_1(9)
% Distance: 30, 1_6(7) 6_2(5) 2_4(9) 4_3(3) 3_5(2) 5_1(4)
% Distance: 29, 1_6(7) 6_2(5) 2_4(9) 4_5(1) 5_3(2) 3_1(5)
% Distance: 34, 1_6(7) 6_2(5) 2_5(8) 5_3(2) 3_4(3) 4_1(9)
% Distance: 29, 1_6(7) 6_2(5) 2_5(8) 5_4(1) 4_3(3) 3_1(5)
% Distance: 33, 1_6(7) 6_3(6) 3_2(6) 2_4(9) 4_5(1) 5_1(4)
% Distance: 37, 1_6(7) 6_3(6) 3_2(6) 2_5(8) 5_4(1) 4_1(9)
% Distance: 37, 1_6(7) 6_3(6) 3_4(3) 4_2(9) 2_5(8) 5_1(4)
% Distance: 35, 1_6(7) 6_3(6) 3_4(3) 4_5(1) 5_2(8) 2_1(10)
% Distance: 41, 1_6(7) 6_3(6) 3_5(2) 5_2(8) 2_4(9) 4_1(9)
% Distance: 35, 1_6(7) 6_3(6) 3_5(2) 5_4(1) 4_2(9) 2_1(10)
% Distance: 35, 1_6(7) 6_4(7) 4_2(9) 2_3(6) 3_5(2) 5_1(4)
% Distance: 38, 1_6(7) 6_4(7) 4_2(9) 2_5(8) 5_3(2) 3_1(5)
% Distance: 35, 1_6(7) 6_4(7) 4_3(3) 3_2(6) 2_5(8) 5_1(4)
% Distance: 37, 1_6(7) 6_4(7) 4_3(3) 3_5(2) 5_2(8) 2_1(10)
% Distance: 34, 1_6(7) 6_4(7) 4_5(1) 5_2(8) 2_3(6) 3_1(5)
% Distance: 33, 1_6(7) 6_4(7) 4_5(1) 5_3(2) 3_2(6) 2_1(10)
% Distance: 36, 1_6(7) 6_5(3) 5_2(8) 2_3(6) 3_4(3) 4_1(9)
% Distance: 35, 1_6(7) 6_5(3) 5_2(8) 2_4(9) 4_3(3) 3_1(5)
% Distance: 36, 1_6(7) 6_5(3) 5_3(2) 3_2(6) 2_4(9) 4_1(9)
% Distance: 34, 1_6(7) 6_5(3) 5_3(2) 3_4(3) 4_2(9) 2_1(10)
% Distance: 31, 1_6(7) 6_5(3) 5_4(1) 4_2(9) 2_3(6) 3_1(5)
% Distance: 30, 1_6(7) 6_5(3) 5_4(1) 4_3(3) 3_2(6) 2_1(10)
% tsp 495>