3
$\begingroup$

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!

enter image description here

$\endgroup$
5
$\begingroup$

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:

enter image description here

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$.
enter image description here
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.

$\endgroup$
8
  • 1
    $\begingroup$ Question specified that the robot started on a specific vertex... $\endgroup$ – Steve Aug 25 '20 at 15:13
  • $\begingroup$ @Steve You're right. I have fixed my answer. $\endgroup$ – Jaap Scherphuis Aug 25 '20 at 15:47
  • $\begingroup$ Great answer, thank you. I believe it is possible to do it in fewer moves though. $\endgroup$ – Dmitry Kamenetsky Aug 25 '20 at 22:39
  • $\begingroup$ You assume that the solution is a Eulerian path, but I don't think that's true. A eulerian path visits each edge exactly once, but here we want to visit each edge at least once and we are allowed to revisit edges. $\endgroup$ – Dmitry Kamenetsky Aug 26 '20 at 1:06
  • 1
    $\begingroup$ You are right that it could be done in less, but this was because I assumed that it had to be an Euler circuit, not an Euler path. $\endgroup$ – Jaap Scherphuis Aug 26 '20 at 3:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.