?- use_module(library(random)).

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

% tspRand(Count, TourBest, DistBest, TourFinal, DistFinal):
% This uses a random search to find a good tour.
% Scrambles tour Count times, and returns the best one.
% Pretty dumb.

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

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).