/*********************************************************** tsp_sat.pi from Constraint Solving and Planning with Picat, Springer by Neng-Fa Zhou, Hakan Kjellerstrand, and Jonathan Fruhman ***********************************************************/ import sat. main => M = {{0,6,1,5,0,0}, % cost matrix {6,0,5,0,3,0}, {1,5,0,5,6,4}, {5,0,5,0,0,2}, {0,3,6,0,0,6}, {0,0,4,2,6,0}}, tsp(M). tsp(M) => N = length(M), NextArr = new_array(N,N), NextArr :: 0..1, foreach (I in 1..N, J in 1..N) if M[I,J] == 0 then NextArr[I,J] = 0 end end, % each vertex is followed by exactly one vertex in a tour foreach (I in 1..N) sum([NextArr[I,J] : J in 1..N]) #= 1 end, % each vertex is preceded by exactly one vertex in a tour foreach (J in 1..N) sum([NextArr[I,J] : I in 1..N]) #= 1 end, % no sub-tours Order = new_array(N), Order :: 1..N, Order[1] = 1, % visit vertex 1 first foreach (I in 1..N) NextArr[I,1] #=> Order[I] #= N, foreach (J in 2..N) NextArr[I,J] #=> Order[J] #= Order[I]+1 end end, CostArr = new_array(N), foreach (I in 1..N) CostArr[I] :: min([M[I,J] : J in 1..N, M[I,J] !== 0]) .. max([M[I,J] : J in 1..N, M[I,J] !== 0]), foreach (J in 1..N) NextArr[I,J] #=> CostArr[I] #= M[I,J] end end, TotalCost #= sum([CostArr[I] : I in 1..N]), solve(\$[min(TotalCost),report(println(cost=TotalCost))], NextArr), foreach (I in 1..N, J in 1..N) if NextArr[I,J]==1 then printf("%w -> %w\n",I,J) end end.