Find the shortest tour through the points of a (a) 3 × 3 square grid; (b) 4 × 4 square grid; (c) 5 × 5 square grid; (d) generalize to n x m grid.
I can draw a tour on 3x3 with 9 edges, 8 of length 1 and 1 of length root2 (if the pts are 1 apart). Is this the shortest? How do I know? What about mxn?