A robot visiting every edge of a 4x4 grid

Question

This is a harder version of this puzzle: A robot visiting every edge of a 3x3 grid

A robot is placed on the top-left vertex of a 4x4 grid. At each move the robot can take one step (up, down, left or right) along the edge of the grid to the adjacent vertex, but he cannot go outside the grid. The robot can revisit vertices and edges. What is the least number of moves required for it to visit every edge of the grid? Good luck!

Answer 1

There are $2\cdot4\cdot5=40$ edges in the graph, so obviously it needs at least $40$ moves.

However, there are $12$ vertices with odd degree. For an Euler path you need at most two odd degree vertices (and for an Euler circuit no odd-degree vertices at all), so some edges will have to be visited twice. We could duplicate some edges, i.e. add some edges parallel to the existing ones, to represent the multiple times some edges need to be used. In that way you get a graph that does have an Euler path or circuit.

The question is of course, which edges do we duplicate? Duplicating an edge between two odd-degree vertices immediately reduces the number of odd-degree vertices by 2. It would be nice if we could pair up all odd-degree vertices like that, cause then we would have a graph which is easily solvable. Unfortunately the odd-degree vertices come in triplets arranged along the edge of the square, and the triplets are not adjacent to each other. The starting point of the robot is given as the top-left corner, which is a vertex with even degree. This means we cannot use the start and end point of the robot as two of the odd-degree vertices, therefore we need all the odd-degree vertices to be made even by adding duplicate edges. Each triplet can be reduced to a single by adding one edge, but the four left-over odd-degree vertices are not adjacent, and to connect them in pairs requires using two duplicated edges per pair. The result is this graph:



So the minimum number of duplicated edges to get an Euler circuit is $8$ (one in each triplet, plus twice two to connect the two pairs of triplets) for a total of $48$ moves.

Note however that two of the duplicated edges connect to the starting vertex. This means that we can remove one of those edges and use an Euler path, leading to a solution with one fewer steps, $47$.

Any Euler path will do, but an easy one is to start at the corner, go once all the way around the outside of the square, and then zig-zag across the inside of the square in one direction and then the other, alternating between using duplicated edges and going straight across, and ending up at the marked vertex next to the starting corner.

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

Using the above labelling, the solution is:
A FKPU VWXY TOJE DCBA FGHIJ ONMLK PQRST Y XSNID CHMRW VQLGB

If you were allowed to choose a starting point for the robot, then you can do away with the other duplicated edge at the top-left corner and skip the first move from the solution.
See also this maths video about minimum duplication circuits.