A city has 36 locations on a 6x6 grid of roads.
combinatorics/grid.tour New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
A city has 36 locations on a 6x6 grid of roads. The cost of each road between adjoining locations is marked below. Visit every location at least once, starting and finishing anywhere and following the roads, at minimum total cost. (Revisiting a location is allowed, and may help.) O-4-O-4-O-5-O-3-O-6-O | | | | | | 5 1 2 8 4 5 | | | | | | O-6-O-5-O-6-O-6-O-6-O | | | | | | 1 9 1 7 4 2 | | | | | | O-9-O-3-O-8-O-7-O-8-O | | | | | | 5 7 8 6 6 9 | | | | | | O-7-O-7-O-3-O-1-O-2-O | | | | | | 9 7 9 2 5 7 | | | | | | O-4-O-4-O-1-O-2-O-7-O | | | | | | 3 2 7 1 1 1 | | | | | | O-9-O-5-O-6-O-9-O-2-O Label the locations: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 A simple (certainly not least cost) route is A B C D E F L K J I H G M N O P Q R X W V U T S Y Z 0 1 2 3 9 8 7 6 5 4 which costs 180.
Show solution
[ Editor: the poser, Michael N Goldshteyn (etcmng@iitmax.iit.edu), reported that the best route he had found cost 143, and that a computer program he wrote found a route of 148. Readers then improved on this. Routes are written in the location labels of the problem. ] 4YZ5601712893XWVUTSMGABHNOICDEKJPQRLF = 135 -- Dave Ring (dwr2560@zeus.tamu.edu) 4yz5671012893xwvutnoijpqklrlfedcbhbagms = 134 -- Remco Bouckaert (remco@cs.ruu.nl) How about this route ? 4yz5671012893xwvutsmgabhnoicdeflrlkqpj = 134 Its cost is same as the above, but its length is shorter. -- Takayuki Nakao (nakao@is.s.u-tokyo.ac.jp) 4YZ5671012893XWVUVPJKQRLFEDCIONTSMGABH = 133 -- David Arsenault (davea@eye.com) [ Editor: the 133 route checks: 3+4+2+5+6+1+1+1+2+1+2+1+7+2+1+3+3+6+7 +6+4+8+2+5+6+3+5+2+1+3+7+7+5+1+5+4+1 = 133, and it visits all 36 locations (V twice). No proof that 133 is optimal was posted. ]