The problem is to visit all the intersections in the minimum time. My first thought was to find a minimal path of 35 edges (roads between intersections) to visit all 36 intersections while minimizing the slower edges and maximizing the faster edges. That results in the solution you see here in red lines. But I also had the thought that I might save time by using faster edges to bypass some of the slower edges. Investigation of the 6x6 puzzle proved that this could indeed be done as indicated by the blue lines. To get there faster one does a U-turn onto the blue trail instead of following the slowest red trail. At the end of the blue trail one does another U-turn back onto the red trail. The trick is to know how far to go back. It was these blue trails that piqued my interest to see what happened if the grid were made larger.

Another thing that I noticed as I added up my times is that each addition of a loop to the route added 1 + 2(n-1)/n "hours" to the travel time, where n the road number (starting with 1, as in counting, not addressing). That is what the plot at the bottom is all about. The plot is color coded - the red plot is for the red route, and the blue plot is for the red route as modified in blue. Notice how much time is saved. On very large grids you get there in only little more than two thirds the time.

When I first placed this page on the web the programs were finding the depth of the backtracking on the loops by trial in a loop. Since then I found a way to calculate it.

For the nth loop of depth m-1, m being the speed of the crossover road, the time required to backtrack is

t = (m-1)(1/(n - 1) + 1/n) + 1/m

Since we want to find the m which minimizes t we differentiate t with respect to m, set dt/dm to 0 and solve for m to get:

m = sqrt(n*(n - 1)/(2*n - 1)))

since m is an integer and the above formula yields an exact answer we need to truncate m, and calculate the times using both m and m + 1, then take the smallest one.

This speeds up the calculation significantly, especially for large grids.