?- use_module(library(random)).

tsp(N, Soln, Dist) :-
	N > 1,
	allcities(T),
	random_permutation(T, T2),
	calcDist(T2, D),
	N2 is N-1,
	tspHillclimb(N2, T2, D, Soln, Dist),
	!.

% tspHillclimb(Count, TourBest, DistBest, TourFinal, DistFinal):
% This uses a hill climbing search to find a good tour.
% Swaps 2 cities, and if permutation is best so far, go to it!

tspHillclimb(N, Tour, Dist, Tour, Dist) :-
	N =< 0.
tspHillclimb(N, TourBest, DistBest, Tour, Dist) :-
	random_swap(TourBest, NewTour),
	calcDist(NewTour, D),
	N2 is N-1,
	(D < DistBest ->
		tspHillclimb(N2, NewTour, D, Tour, Dist)
		;
		tspHillclimb(N2, TourBest, DistBest, Tour, Dist)).

% random_swap(L, L2):
% swaps 2 random elements in L, resulting in L2.

random_swap(L, S) :-
	random_select(A, L, L1),
	random_member(B, L1),
	append(X1, [A|X2], L),   % find A in list
	(append(Y1, [B|Y2], X1) -> % is B to the left of A?
		append(Y1, [A|Y2], W1), % yes.. swap them.
		append(W1, [B|X2], S)
		;
		append(T1, [B|T2], X2), % no... swap them.
		append(T1, [A|T2], U1),
		append(X1, [B|U1], S)),
	!.
	

calcDist(Tour, Dist) :-
	calcDist2(Tour, Dist2),
	reverse(Tour, [Last|_]),
	Tour = [First|_],
	calcDist2([First, Last], DistLast),
	Dist is Dist2+DistLast,
	!.
	
		

calcDist2([], 0).
calcDist2([_], 0).
calcDist2([A,B|R], Dist) :-
	city(A, Xa, Ya),
	city(B, Xb, Yb),
	calcDist2([B|R], Dist2),
	Dist is Dist2+ sqrt((Xa-Xb)*(Xa-Xb)+(Ya-Yb)*(Ya-Yb)),
	!.
	
reverse(List, Reversed) :-
	rev2(List, [ ], Reversed),
	!.

rev2([ ], Rev, Rev).
rev2([A|T], L, Rev) :- 
	rev2(T, [A|L], Rev).

% map of 4-by-4 grid of cities...

allcities([aa,ab,ac,ad,ba,bb,bc,bd,ca,cb,cc,cd,da,db,dc,dd]).

city(aa, 1, 1).
city(ab, 1, 2).
city(ac, 1, 3).
city(ad, 1, 4).
city(ba, 2, 1).
city(bb, 2, 2).
city(bc, 2, 3).
city(bd, 2, 4).
city(ca, 3, 1).
city(cb, 3, 2).
city(cc, 3, 3).
city(cd, 3, 4).
city(da, 4, 1).
city(db, 4, 2).
city(dc, 4, 3).
city(dd, 4, 4).