[Solved]: Minimum distance between start and end by going through must visit points in a maze

Most real mazes are trees and there is a polynomial time algorithm for this problem on trees. For ease of description, orient all edges of the tree to point away from the start vertex. Now, for each vertex, delete any child if the subtree rooted at that child contains no vertices that must be visited (i.e., contains no grey or red vertices). The result is a tree where every leaf is grey or red (there may be grey and red vertices in the interior of the tree, too). Now perform a depth-first traversal of the tree, investigating the children of each node in arbitrary order, except that, if one of the children is on the path from the start to the red (end) node, that child is investigated last. If the red node was a leaf, you are done; if not, take the unique path from the leaf you finished at to the red node. The total distance is twice the number of edges in the reduced tree, minus the number of edges on the shortest path from the start to the red vertex. For general graphs, the problem is NP-hard. Consider the special case where the “maze” actually has no black squares. What we have is, essentially, a so-called rectlinear TSP, where the start, end and grey squares are the “cities”. Rectilinear TSP is metric TSP using the Manhattan distance as the metric. The input is a set of points with 2D integer co-ordinates. Observe that metric TSP doesn’t care whether you revisit cities or not because it obeys the triangle inequality: if the shortest route from A to B is via C, and the salesman has already visited C, he’ll just drive straight past; in the maze world, we don’t care whether he stops or not, since he’s allowed to stop in a city as many times as he wants. Rectilinear TSP is NP-hard: see Garey, Graham and Johnson, Some NP-Complete Problems (Proc. 8th STOC, pp. 10–22, 1976; ACM DL). To prove NP-hardness of the maze problem, we need to demonstrate a reduction from rectilinear TSP. This isn’t quite trivial because the maze problem has specified and distinct start and end squares but I’m reducing from rectilinear TSP, in which the salesman starts at any city he chooses and returns to that city at the end. But observe that it doesn’t matter what the start city is, since the tours ABCDA and CDABC have exactly the same length: forcing the tour to start at a particular city doesn’t actually change the answer. So, if I’m allowed to cheat once more and put the red and orange squares in the same place, I’ll do that. But you probably mean that squares have a unique colour, so here’s the full reduction:

Take the northern-most of the cities and make it be the start square (if there are multiple cities equally far north, choose any one of them. Make every other city a grey square. Place the end square one square to the north of the start square and colour black the squares north, east and west of the end square. Make every other square white.

Because of the black walls, any route from the start square to the end square must revisit the start square immediately before going to the end. The end square and its black walls are outside the convex hull of the original cities, so no optimal tour of the original cities would have gone through those squares. Therefore, a shortest route from the start square to the end square consists of a solution to the rectilinear TSP problem (a shortest tour from the start city, through all the other cities and back to the start city), followed by the one-square move from the start square to the end square. This completes the reduction.