% File : tsp.pl % Author : Neng-Fa ZHOU % Date : 1994 % Purpose: Doubly spanning tree heuristic algorithm for TSP go:- cputime(S), go(67), cputime(E), T is E-S, write(T), write(' milliseconds'). go(N):- % number of vertices in a map edges(Es), sort_edges(Es,SortedEs), cputime(Start), bt(edge(1..N,1..N),false), bt(open(1..N),true), mst(N,SortedEs,Tree,0,Cost), % write('cost='),write(Cost),nl, % write(Tree),nl, tsp(N,SortedEs,BestTour,Length), cputime(End), T is End-Start, write(BestTour),nl, write('length = '),write(Length),nl, write('execution time : '), write(T),nl. tsp(N,Es,BestTour,Length):- Limit=99999, global_set(best_tour,0,([],Limit)), eulerian(N,1,1,Tour,0,Length), write('length='),write(Length),nl, write(Tour),nl, % write(global_set(best_tour,0,(Tour,Length))),nl, global_set(best_tour,0,(Tour,Length)), fail. tsp(N,Es,BestTour,Length):- global_get(best_tour,0,(BestTour,Length)). mst(N,Es,Tree,C0,C):- N=<1 : C=C0,Tree=[]. mst(N,[edge(X,Y,W)|Es],Tree,C0,C):- true ? reachable(X,Y,Y),!, mst(N,Es,Tree,C0,C). mst(N,[edge(X,Y,W)|Es],Tree,C0,C):- true : Tree:=[edge(X,Y,W)|Tree1], bt_set_true(edge(X,Y)), bt_set_true(edge(Y,X)), N1 is N-1, C1 is C0+W, mst(N1,Es,Tree1,C1,C). reachable(X,X,_):-!. reachable(X,Y,Z):- bt_select(edge(Y,U)), Z\==U, reachable(X,U,Y). sort_edges([X|Xs],Ys):- true : X=edge(_,_,W), partition(Xs,W,Littles,Bigs), sort_edges(Littles,Ls), sort_edges(Bigs,Bs), '$append'(Ls,[X|Bs],Ys). sort_edges([],Ys):-true : Ys=[]. partition([X|Xs],W,Ls,Bs):- edge(_,_,W1)<=X, W1=1 : Tour:=[edge(X,Y)|Tour1], next_edge(X,Y), weight(X,Y,W), Length1 is Length0+W, global_get(best_tour,0,(_,Limit)), Length167 : Es=[]. edges(N,Es):- neighbors(N,Ls), reform_edges(N,Ls,Es,Es1), N1 is N+1, edges(N1,Es1). reform_edges(X,[],Es,EsRest):- true : Es=EsRest. reform_edges(X,[(Y,W)|L],Es,EsRest):- true : Es:=[edge(X,Y,W)|Es1], reform_edges(X,L,Es1,EsRest). :-mode neighbors(+,-). neighbors(1,[(2,72),(3,51),(4,222),(5,52),(6,182),(7,99),(8,83),(9,186),(10,72),(11,30),(12,76),(13,118),(14,46),(15,13),(16,85),(17,96),(18,120),(19,155),(20,47),(21,32),(22,173),(23,27),(24,27),(25,107),(26,124),(27,184),(28,101),(29,68),(30,159),(31,56),(32,64),(33,128),(34,57),(35,252),(36,160),(37,182),(38,139),(39,42),(40,62),(41,92),(42,194),(43,54),(44,98),(45,40),(46,103),(47,75),(48,78),(49,44),(50,46),(51,170),(52,196),(53,30),(54,93),(55,165),(56,193),(57,96),(58,61),(59,75),(60,113),(61,80),(62,81),(63,93),(64,158),(65,112),(66,233),(67,136)]). neighbors(2,[(3,43),(4,217),(5,92),(6,163),(7,116),(8,143),(9,161),(10,141),(11,42),(12,89),(13,140),(14,118),(15,61),(16,16),(17,166),(18,95),(19,110),(20,112),(21,72),(22,122),(23,83),(24,92),(25,38),(26,77),(27,146),(28,164),(29,140),(30,136),(31,16),(32,104),(33,77),(34,26),(35,227),(36,88),(37,130),(38,114),(39,30),(40,96),(41,67),(42,169),(43,74),(44,153),(45,112),(46,115),(47,99),(48,141),(49,106),(50,80),(51,153),(52,151),(53,63),(54,41),(55,111),(56,128),(57,108),(58,124),(59,35),(60,58),(61,145),(62,121),(63,44),(64,106),(65,168),(66,208),(67,80)]). neighbors(3,[(4,229),(5,97),(6,199),(7,121),(8,115),(9,203),(10,101),(11,47),(12,94),(13,145),(14,71),(15,38),(16,59),(17,121),(18,137),(19,172),(20,74),(21,77),(22,165),(23,78),(24,54),(25,78),(26,108),(27,201),(28,126),(29,93),(30,176),(31,47),(32,109),(33,129),(34,17),(35,269),(36,118),(37,173),(38,156),(39,24),(40,101),(41,109),(42,217),(43,79),(44,126),(45,82),(46,120),(47,114),(48,103),(49,94),(50,85),(51,186),(52,212),(53,21),(54,84),(55,154),(56,179),(57,103),(58,86),(59,66),(60,104),(61,107),(62,126),(63,42),(64,159),(65,148),(66,245),(67,127)]). neighbors(4,[(5,219),(6,40),(7,156),(8,285),(9,63),(10,299),(11,192),(12,174),(13,150),(14,283),(15,221),(16,187),(17,296),(18,110),(19,99),(20,269),(21,226),(22,144),(23,235),(24,249),(25,165),(26,128),(27,57),(28,309),(29,272),(30,69),(31,201),(32,231),(33,126),(34,229),(35,26),(36,184),(37,115),(38,83),(39,224),(40,210),(41,130),(42,36),(43,180),(44,295),(45,260),(46,139),(47,208),(48,295),(49,238),(50,195),(51,61),(52,94),(53,241),(54,170),(55,134),(56,126),(57,184),(58,283),(59,170),(60,145),(61,315),(62,245),(63,227),(64,152),(65,312),(66,28),(67,144)]). neighbors(5,[(6,179),(7,57),(8,123),(9,159),(10,100),(11,50),(12,61),(13,81),(14,60),(15,65),(16,105),(17,100),(18,117),(19,161),(20,96),(21,20),(22,200),(23,25),(24,70),(25,130),(26,121),(27,181),(28,92),(29,63),(30,156),(31,76),(32,12),(33,155),(34,89),(35,246),(36,177),(37,192),(38,136),(39,74),(40,25),(41,89),(42,192),(43,47),(44,113),(45,42),(46,81),(47,38),(48,76),(49,30),(50,25),(51,167),(52,232),(53,82),(54,113),(55,201),(56,213),(57,59),(58,75),(59,95),(60,133),(61,96),(62,29),(63,129),(64,185),(65,116),(66,211),(67,158)]). neighbors(6,[(7,130),(8,265),(9,65),(10,251),(11,152),(12,135),(13,139),(14,243),(15,181),(16,147),(17,256),(18,92),(19,59),(20,229),(21,178),(22,104),(23,195),(24,202),(25,195),(26,88),(27,17),(28,270),(29,242),(30,29),(31,149),(32,191),(33,86),(34,189),(35,70),(36,144),(37,75),(38,43),(39,193),(40,183),(41,90),(42,28),(43,133),(44,275),(45,221),(46,121),(47,194),(48,256),(49,220),(50,177),(51,34),(52,54),(53,201),(54,130),(55,79),(56,66),(57,163),(58,243),(59,130),(60,105),(61,281),(62,227),(63,187),(64,94),(65,272),(66,68),(67,104)]). neighbors(7,[(8,168),(9,91),(10,154),(11,74),(12,27),(13,24),(14,114),(15,107),(16,117),(17,145),(18,53),(19,103),(20,141),(21,62),(22,166),(23,82),(24,121),(25,120),(26,103),(27,132),(28,132),(29,103),(30,107),(31,100),(32,66),(33,136),(34,113),(35,191),(36,182),(37,152),(38,87),(39,96),(40,32),(41,71),(42,120),(43,42),(44,160),(45,96),(46,24),(47,27),(48,123),(49,84),(50,48),(51,121),(52,149),(53,124),(54,121),(55,144),(56,135),(57,18),(58,129),(59,95),(60,140),(61,150),(62,76),(63,159),(64,166),(65,163),(66,154),(67,154)]). neighbors(8,[(9,269),(10,14),(11,113),(12,165),(13,206),(14,54),(15,92),(16,168),(17,47),(18,203),(19,243),(20,39),(21,120),(22,261),(23,97),(24,51),(25,193),(26,207),(27,267),(28,70),(29,57),(30,242),(31,139),(32,102),(33,211),(34,132),(35,335),(36,235),(37,258),(38,222),(39,113),(40,136),(41,175),(42,249),(43,145),(44,21),(45,72),(46,183),(47,149),(48,47),(49,90),(50,127),(51,253),(52,296),(53,95),(54,176),(55,253),(56,281),(57,175),(58,44),(59,148),(60,196),(61,34),(62,84),(63,157),(64,244),(65,47),(66,317),(67,219)]). neighbors(9,[(10,255),(11,156),(12,104),(13,87),(14,232),(15,185),(16,162),(17,247),(18,66),(19,81),(20,233),(21,182),(22,169),(23,184),(24,213),(25,169),(26,114),(27,89),(28,239),(29,228),(30,72),(31,145),(32,168),(33,129),(34,195),(35,89),(36,187),(37,128),(38,65),(39,180),(40,134),(41,94),(42,37),(43,119),(44,279),(45,190),(46,78),(47,147),(48,225),(49,186),(50,151),(51,47),(52,119),(53,205),(54,154),(55,134),(56,151),(57,120),(58,247),(59,140),(60,148),(61,252),(62,201),(63,204),(64,140),(65,263),(66,52),(67,137)]). neighbors(10,[(11,99),(12,151),(13,192),(14,40),(15,78),(16,154),(17,41),(18,189),(19,229),(20,25),(21,106),(22,247),(23,83),(24,52),(25,179),(26,193),(27,253),(28,56),(29,43),(30,218),(31,125),(32,88),(33,197),(34,118),(35,321),(36,220),(37,244),(38,208),(39,109),(40,122),(41,161),(42,263),(43,136),(44,24),(45,58),(46,172),(47,135),(48,33),(49,76),(50,127),(51,239),(52,282),(53,81),(54,162),(55,239),(56,267),(57,161),(58,30),(59,144),(60,182),(61,20),(62,70),(63,143),(64,230),(65,50),(66,303),(67,205)]). neighbors(11,[(12,47),(13,98),(14,76),(15,29),(16,56),(17,134),(18,80),(19,170),(20,77),(21,80),(22,143),(23,41),(24,85),(25,77),(26,97),(27,164),(28,126),(29,97),(30,129),(31,26),(32,62),(33,88),(34,89),(35,222),(36,127),(37,145),(38,109),(39,24),(40,54),(41,62),(42,165),(43,82),(44,123),(45,66),(46,73),(47,67),(48,113),(49,64),(50,88),(51,140),(52,165),(53,49),(54,83),(55,126),(56,150),(57,66),(58,31),(59,45),(60,83),(61,110),(62,79),(63,79),(64,128),(65,142),(66,203),(67,106)]). neighbors(12,[(13,51),(14,108),(15,76),(16,80),(17,143),(18,55),(19,107),(20,124),(21,44),(22,139),(23,61),(24,104),(25,93),(26,76),(27,136),(28,135),(29,107),(30,111),(31,79),(32,70),(33,109),(34,86),(35,204),(36,152),(37,156),(38,91),(39,71),(40,36),(41,44),(42,129),(43,15),(44,158),(45,86),(46,26),(47,49),(48,121),(49,73),(50,30),(51,122),(52,171),(53,93),(54,76),(55,137),(56,152),(57,19),(58,133),(59,58),(60,96),(61,154),(62,80),(63,122),(64,139),(65,167),(66,156),(67,127)]). neighbors(13,[(14,138),(15,131),(16,131),(17,169),(18,62),(19,102),(20,165),(21,86),(22,176),(23,106),(24,145),(25,146),(26,106),(27,141),(28,156),(29,127),(30,116),(31,124),(32,90),(33,144),(34,137),(35,176),(36,188),(37,159),(38,96),(39,122),(40,56),(41,79),(42,124),(43,66),(44,184),(45,120),(46,33),(47,69),(48,147),(49,106),(50,72),(51,120),(52,178),(53,147),(54,127),(55,153),(56,144),(57,42),(58,153),(59,109),(60,145),(61,174),(62,100),(63,174),(64,174),(65,187),(66,139),(67,162)]). neighbors(14,[(15,48),(16,131),(17,50),(18,166),(19,196),(20,37),(21,60),(22,219),(23,43),(24,17),(25,153),(26,163),(27,245),(28,55),(29,22),(30,220),(31,102),(32,48),(33,174),(34,94),(35,313),(36,203),(37,221),(38,200),(39,88),(40,82),(41,138),(42,256),(43,93),(44,65),(45,18),(46,138),(47,95),(48,32),(49,30),(50,74),(51,231),(52,242),(53,50),(54,139),(55,211),(56,239),(57,121),(58,15),(59,121),(60,159),(61,36),(62,61),(63,113),(64,204),(65,66),(66,284),(67,182)]). neighbors(15,[(16,77),(17,96),(18,119),(19,168),(20,51),(21,45),(22,172),(23,40),(24,31),(25,99),(26,123),(27,183),(28,103),(29,70),(30,158),(31,55),(32,77),(33,127),(34,46),(35,251),(36,149),(37,174),(38,138),(39,31),(40,75),(41,91),(42,193),(43,61),(44,92),(45,53),(46,102),(47,88),(48,80),(49,63),(50,59),(51,169),(52,220),(53,17),(54,92),(55,164),(56,192),(57,95),(58,63),(59,74),(60,112),(61,84),(62,94),(63,80),(64,157),(65,114),(66,232),(67,135)]). neighbors(16,[(17,179),(18,96),(19,97),(20,132),(21,85),(22,106),(23,99),(24,110),(25,22),(26,67),(27,130),(28,180),(29,156),(30,126),(31,29),(32,117),(33,61),(34,42),(35,217),(36,72),(37,114),(38,115),(39,46),(40,109),(41,68),(42,175),(43,87),(44,169),(45,128),(46,116),(47,122),(48,157),(49,119),(50,93),(51,147),(52,128),(53,79),(54,25),(55,95),(56,112),(57,99),(58,140),(59,22),(60,42),(61,161),(62,134),(63,42),(64,90),(65,197),(66,211),(67,64)]). neighbors(17,[(18,198),(19,231),(20,66),(21,110),(22,269),(23,93),(24,67),(25,206),(26,198),(27,258),(28,23),(29,42),(30,233),(31,162),(32,86),(33,222),(34,138),(35,322),(36,256),(37,299),(38,213),(39,129),(40,113),(41,166),(42,262),(43,143),(44,26),(45,69),(46,169),(47,126),(48,22),(49,70),(50,113),(51,265),(52,314),(53,100),(54,187),(55,261),(56,289),(57,147),(58,35),(59,180),(60,209),(61,21),(62,69),(63,163),(64,254),(65,16),(66,299),(67,230)]). neighbors(18,[(19,50),(20,167),(21,116),(22,114),(23,116),(24,147),(25,95),(26,46),(27,79),(28,190),(29,162),(30,54),(31,79),(32,129),(33,79),(34,121),(35,136),(36,136),(37,97),(38,34),(39,102),(40,91),(41,28),(42,74),(43,70),(44,213),(45,140),(46,29),(47,98),(48,176),(49,128),(50,85),(51,58),(52,96),(53,139),(54,88),(55,91),(56,82),(57,74),(58,181),(59,74),(60,83),(61,209),(62,135),(63,138),(64,109),(65,214),(66,113),(67,97)]). neighbors(19,[(20,202),(21,153),(22,74),(23,168),(24,182),(25,92),(26,33),(27,51),(28,242),(29,214),(30,26),(31,94),(32,175),(33,48),(34,132),(35,125),(36,120),(37,60),(38,16),(39,117),(40,143),(41,63),(42,72),(43,106),(44,243),(45,190),(46,79),(47,154),(48,228),(49,178),(50,130),(51,47),(52,75),(53,150),(54,75),(55,41),(56,43),(57,124),(58,216),(59,75),(60,67),(61,241),(62,192),(63,142),(64,59),(65,247),(66,111),(67,66)]). neighbors(20,[(21,79),(22,220),(23,73),(24,20),(25,152),(26,171),(27,231),(28,71),(29,59),(30,206),(31,103),(32,87),(33,175),(34,94),(35,299),(36,193),(37,222),(38,186),(39,82),(40,109),(41,139),(42,242),(43,109),(44,49),(45,48),(46,156),(47,112),(48,48),(49,60),(50,93),(51,215),(52,241),(53,56),(54,140),(55,212),(56,240),(57,158),(58,31),(59,131),(60,160),(61,45),(62,98),(63,119),(64,203),(65,71),(66,280),(67,183)]). neighbors(21,[(22,173),(23,17),(24,59),(25,107),(26,120),(27,180),(28,102),(29,73),(30,155),(31,56),(32,32),(33,128),(34,69),(35,248),(36,157),(37,186),(38,135),(39,54),(40,30),(41,88),(42,190),(43,33),(44,125),(45,42),(46,70),(47,43),(48,89),(49,40),(50,14),(51,157),(52,203),(53,62),(54,93),(55,189),(56,184),(57,64),(58,75),(59,75),(60,113),(61,106),(62,49),(63,109),(64,171),(65,126),(66,229),(67,136)]). neighbors(22,[(23,184),(24,200),(25,84),(26,68),(27,87),(28,269),(29,246),(30,112),(31,117),(32,212),(33,45),(34,148),(35,141),(36,103),(37,29),(38,92),(39,140),(40,175),(41,100),(42,132),(43,153),(44,266),(45,204),(46,143),(47,182),(48,256),(49,209),(50,169),(51,120),(52,50),(53,173),(54,80),(55,33),(56,44),(57,158),(58,234),(59,96),(60,64),(61,253),(62,219),(63,148),(64,15),(65,285),(66,172),(67,47)]). neighbors(23,[(24,41),(25,118),(26,137),(27,197),(28,85),(29,56),(30,172),(31,67),(32,37),(33,139),(34,84),(35,265),(36,168),(37,203),(38,152),(39,65),(40,50),(41,105),(42,184),(43,50),(44,108),(45,28),(46,106),(47,57),(48,72),(49,23),(50,31),(51,174),(52,220),(53,57),(54,104),(55,206),(56,201),(57,81),(58,58),(59,86),(60,124),(61,89),(62,54),(63,124),(64,169),(65,109),(66,236),(67,147)]). neighbors(24,[(25,132),(26,144),(27,211),(28,68),(29,39),(30,184),(31,81),(32,58),(33,153),(34,71),(35,277),(36,172),(37,200),(38,159),(39,66),(40,95),(41,119),(42,220),(43,89),(44,69),(45,28),(46,128),(47,117),(48,49),(49,40),(50,73),(51,195),(52,221),(53,33),(54,120),(55,192),(56,220),(57,126),(58,32),(59,105),(60,140),(61,53),(62,71),(63,96),(64,183),(65,83),(66,258),(67,163)]). neighbors(25,[(26,57),(27,108),(28,202),(29,173),(30,113),(31,54),(32,142),(33,39),(34,64),(35,195),(36,41),(37,86),(38,103),(39,68),(40,129),(41,67),(42,159),(43,109),(44,203),(45,150),(46,115),(47,147),(48,185),(49,141),(50,115),(51,134),(52,107),(53,99),(54,17),(55,67),(56,91),(57,112),(58,162),(59,35),(60,20),(61,183),(62,156),(63,65),(64,69),(65,219),(66,196),(67,42)]). neighbors(26,[(27,84),(28,211),(29,183),(30,59),(31,61),(32,133),(33,33),(34,109),(35,158),(36,87),(37,91),(38,49),(39,84),(40,112),(41,32),(42,105),(43,75),(44,217),(45,125),(46,75),(47,125),(48,197),(49,147),(50,97),(51,80),(52,108),(53,117),(54,42),(55,61),(56,76),(57,95),(58,185),(59,42),(60,37),(61,197),(62,156),(63,109),(64,63),(65,214),(66,144),(67,51)]). neighbors(27,[(28,280),(29,243),(30,25),(31,145),(32,193),(33,69),(34,172),(35,87),(36,127),(37,58),(38,45),(39,176),(40,172),(41,92),(42,45),(43,135),(44,277),(45,222),(46,108),(47,177),(48,249),(49,207),(50,176),(51,42),(52,37),(53,203),(54,108),(55,62),(56,49),(57,153),(58,245),(59,126),(60,88),(61,264),(62,214),(63,190),(64,77),(65,274),(66,84),(67,87)]). neighbors(28,[(29,29),(30,246),(31,152),(32,80),(33,224),(34,149),(35,339),(36,253),(37,291),(38,224),(39,134),(40,114),(41,170),(42,258),(43,127),(44,49),(45,61),(46,156),(47,113),(48,23),(49,62),(50,105),(51,258),(52,306),(53,105),(54,189),(55,291),(56,278),(57,141),(58,40),(59,171),(60,209),(61,31),(62,56),(63,168),(64,254),(65,31),(66,291),(67,232)]). neighbors(29,[(30,218),(31,122),(32,51),(33,195),(34,116),(35,298),(36,223),(37,274),(38,198),(39,101),(40,71),(41,151),(42,238),(43,98),(44,57),(45,32),(46,133),(47,84),(48,20),(49,33),(50,76),(51,229),(52,278),(53,72),(54,160),(55,262),(56,249),(57,105),(58,21),(59,142),(60,180),(61,33),(62,27),(63,135),(64,225),(65,60),(66,275),(67,203)]). neighbors(30,[(31,120),(32,168),(33,74),(34,162),(35,99),(36,132),(37,61),(38,20),(39,143),(40,145),(41,67),(42,50),(43,110),(44,252),(45,178),(46,83),(47,158),(48,232),(49,182),(50,139),(51,25),(52,62),(53,178),(54,101),(55,62),(56,51),(57,128),(58,220),(59,101),(60,93),(61,263),(62,189),(63,168),(64,80),(65,249),(66,89),(67,92)]). neighbors(31,[(32,88),(33,72),(34,42),(35,186),(36,101),(37,119),(38,98),(39,23),(40,80),(41,51),(42,153),(43,54),(44,149),(45,92),(46,99),(47,93),(48,139),(49,90),(50,64),(51,137),(52,165),(53,56),(54,37),(55,107),(56,137),(57,92),(58,117),(59,19),(60,57),(61,136),(62,105),(63,60),(64,102),(65,168),(66,192),(67,80)]). neighbors(32,[(33,167),(34,101),(35,271),(36,189),(37,224),(38,148),(39,86),(40,37),(41,101),(42,204),(43,59),(44,101),(45,30),(46,90),(47,47),(48,64),(49,18),(50,37),(51,179),(52,231),(53,94),(54,125),(55,216),(56,222),(57,68),(58,63),(59,107),(60,145),(61,84),(62,17),(63,141),(64,197),(65,104),(66,220),(67,168)]). neighbors(33,[(34,103),(35,156),(36,58),(37,47),(38,64),(39,107),(40,145),(41,65),(42,120),(43,106),(44,221),(45,164),(46,111),(47,158),(48,211),(49,164),(50,130),(51,95),(52,68),(53,157),(54,35),(55,35),(56,52),(57,128),(58,189),(59,53),(60,19),(61,208),(62,189),(63,103),(64,30),(65,240),(66,159),(67,18)]). neighbors(34,[(35,259),(36,116),(37,156),(38,148),(39,15),(40,93),(41,89),(42,217),(43,71),(44,143),(45,97),(46,112),(47,108),(48,113),(49,103),(50,77),(51,175),(52,177),(53,38),(54,67),(55,137),(56,162),(57,105),(58,96),(59,61),(60,84),(61,124),(62,118),(63,40),(64,147),(65,154),(66,242),(67,106)]). neighbors(35,[(36,214),(37,112),(38,113),(39,246),(40,227),(41,160),(42,62),(43,203),(44,345),(45,290),(46,165),(47,236),(48,325),(49,264),(50,234),(51,87),(52,91),(53,267),(54,195),(55,131),(56,123),(57,223),(58,313),(59,206),(60,175),(61,341),(62,271),(63,259),(64,149),(65,338),(66,51),(67,170)]). neighbors(36,[(37,105),(38,122),(39,118),(40,181),(41,106),(42,178),(43,159),(44,256),(45,197),(46,156),(47,194),(48,240),(49,191),(50,165),(51,153),(52,133),(53,151),(54,58),(55,86),(56,110),(57,153),(58,212),(59,94),(60,50),(61,233),(62,206),(63,76),(64,82),(65,259),(66,217),(67,47)]). neighbors(37,[(38,63),(39,149),(40,203),(41,123),(42,103),(43,158),(44,268),(45,211),(46,126),(47,200),(48,258),(49,225),(50,168),(51,100),(52,21),(53,175),(54,82),(55,19),(56,15),(57,171),(58,236),(59,107),(60,66),(61,266),(62,236),(63,158),(64,37),(65,305),(66,145),(67,55)]). neighbors(38,[(39,121),(40,125),(41,47),(42,56),(43,90),(44,249),(45,158),(46,63),(47,132),(48,212),(49,162),(50,119),(51,31),(52,62),(53,158),(54,91),(55,57),(56,46),(57,108),(58,200),(59,93),(60,83),(61,245),(62,169),(63,157),(64,75),(65,229),(66,95),(67,82)]). neighbors(39,[(40,78),(41,74),(42,176),(43,56),(44,123),(45,62),(46,97),(47,93),(48,111),(49,92),(50,62),(51,160),(52,170),(53,33),(54,60),(55,130),(56,160),(57,90),(58,94),(59,42),(60,88),(61,115),(62,103),(63,55),(64,125),(65,154),(66,231),(67,110)]). neighbors(40,[(41,80),(42,165),(43,38),(44,128),(45,64),(46,56),(47,13),(48,91),(49,52),(50,16),(51,149),(52,207),(53,92),(54,112),(55,182),(56,186),(57,34),(58,97),(59,94),(60,149),(61,118),(62,44),(63,140),(64,175),(65,131),(66,186),(67,163)]). neighbors(41,[(42,102),(43,43),(44,185),(45,118),(46,46),(47,77),(48,165),(49,117),(50,65),(51,86),(52,129),(53,111),(54,50),(55,93),(56,106),(57,63),(58,153),(59,46),(60,69),(61,178),(62,124),(63,110),(64,95),(65,182),(66,141),(67,83)]). neighbors(42,[(43,144),(44,259),(45,214),(46,103),(47,172),(48,250),(49,202),(50,159),(51,25),(52,82),(53,213),(54,147),(55,122),(56,94),(57,148),(58,250),(59,147),(60,139),(61,283),(62,211),(63,214),(64,130),(65,288),(66,39),(67,132)]). neighbors(43,[(44,159),(45,75),(46,41),(47,51),(48,122),(49,65),(50,22),(51,138),(52,172),(53,78),(54,83),(55,143),(56,136),(57,34),(58,110),(59,65),(60,112),(61,135),(62,76),(63,111),(64,138),(65,159),(66,183),(67,137)]). neighbors(44,[(45,83),(46,193),(47,141),(48,37),(49,85),(50,139),(51,263),(52,289),(53,105),(54,186),(55,271),(56,299),(57,162),(58,50),(59,168),(60,206),(61,24),(62,84),(63,168),(64,251),(65,26),(66,262),(67,229)]). neighbors(45,[(46,111),(47,77),(48,47),(49,12),(50,56),(51,208),(52,247),(53,61),(54,133),(55,231),(56,226),(57,103),(58,33),(59,111),(60,153),(61,60),(62,43),(63,137),(64,194),(65,85),(66,242),(67,172)]). neighbors(46,[(47,51),(48,147),(49,106),(50,56),(51,87),(52,125),(53,119),(54,96),(55,120),(56,111),(57,42),(58,159),(59,94),(60,112),(61,174),(62,106),(63,158),(64,141),(65,187),(66,130),(67,126)]). neighbors(47,[(48,104),(49,65),(50,29),(51,156),(52,220),(53,105),(54,125),(55,195),(56,201),(57,77),(58,110),(59,107),(60,146),(61,131),(62,57),(63,153),(64,172),(65,144),(66,199),(67,176)]). neighbors(48,[(49,48),(50,91),(51,234),(52,294),(53,82),(54,171),(55,268),(56,273),(57,139),(58,17),(59,156),(60,196),(61,13),(62,47),(63,145),(64,241),(65,38),(66,286),(67,212)]). neighbors(49,[(50,43),(51,186),(52,242),(53,90),(54,129),(55,229),(56,210),(57,86),(58,45),(59,109),(60,147),(61,66),(62,31),(63,147),(64,194),(65,86),(66,238),(67,140)]). neighbors(50,[(51,143),(52,194),(53,86),(54,101),(55,176),(56,173),(57,40),(58,88),(59,83),(60,121),(61,109),(62,54),(63,117),(64,160),(65,129),(66,186),(67,144)]). neighbors(51,[(52,79),(53,189),(54,122),(55,87),(56,76),(57,132),(58,231),(59,122),(60,114),(61,276),(62,202),(63,189),(64,105),(65,272),(66,64),(67,112)]). neighbors(52,[(53,203),(54,126),(55,40),(56,32),(57,170),(58,257),(59,144),(60,94),(61,276),(62,253),(63,172),(64,58),(65,336),(66,121),(67,86)]). neighbors(53,[(54,93),(55,163),(56,193),(57,102),(58,65),(59,75),(60,113),(61,86),(62,104),(63,63),(64,158),(65,116),(66,252),(67,136)]). neighbors(54,[(55,63),(56,87),(57,95),(58,154),(59,18),(60,20),(61,175),(62,158),(63,67),(64,65),(65,205),(66,186),(67,43)]). neighbors(55,[(56,24),(57,165),(58,217),(59,81),(60,47),(61,247),(62,226),(63,137),(64,18),(65,277),(66,162),(67,46)]). neighbors(56,[(57,171),(58,241),(59,116),(60,71),(61,275),(62,232),(63,163),(64,42),(65,305),(66,153),(67,70)]). neighbors(57,[(58,131),(59,77),(60,132),(61,152),(62,78),(63,141),(64,158),(65,163),(66,172),(67,146)]). neighbors(58,[(59,136),(60,174),(61,21),(62,48),(63,128),(64,219),(65,51),(66,294),(67,195)]). neighbors(59,[(60,36),(61,157),(62,124),(63,64),(64,83),(65,187),(66,192),(67,61)]). neighbors(60,[(61,195),(62,178),(63,84),(64,49),(65,225),(66,178),(67,23)]). neighbors(61,[(62,60),(63,149),(64,238),(65,37),(66,304),(67,216)]). neighbors(62,[(63,158),(64,214),(65,87),(66,248),(67,207)]). neighbors(63,[(64,135),(65,179),(66,251),(67,106)]). neighbors(64,[(65,270),(66,315),(67,29)]). neighbors(65,[(66,327),(67,172)]). neighbors(66,[(67,151)]). neighbors(67,[]). /*aalst : 1 aarschot : 2 antwerpen : 3 arlon : 4 ath : 5 bastogne : 6 beaumont : 7 blankenberge : 8 bouillon : 9 brugge : 10 brussel : 11 charleroi : 12 chimay : 13 deinze : 14 dendermonde : 15 diest : 16 diksmuide : 17 dinant : 18 durbuy : 19 eeklo : 20 enghien : 21 eupen : 22 geraardsbergen : 23 gent : 24 hasselt : 25 huy : 26 houffalize : 27 ieper : 28 kortrijk : 29 laroche : 30 leuven : 31 leuze : 32 liege : 33 lier : 34 luxemburg : 35 maaseik : 36 malmedy : 37 marche : 38 mechelen : 39 mons : 40 namur : 41 neufchateau : 42 nivelles : 43 oostende : 44 oudenaarde : 45 philippeville : 46 quevy : 47 roeselare : 48 ronse : 49 soignies : 50 sthubert : 51 stvith : 52 stniklaas : 53 sttruiden : 54 spa : 55 stavelot : 56 thuin : 57 tielt : 58 tienen : 59 tongeren : 60 torhout : 61 tournai : 62 turnhout : 63 verviers : 64 veurne : 65 virton : 66 vise : 67 */