### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 177,972 hits

Advertisements

Programming Enigma Puzzles

16 July 2013

Posted by on **From New Scientist #1252, 7th May 1981** [link]

Here we have uniform square grid of roads, each 6 miles long, intersecting at 49 junctions. I want a route, starting at any junction and ending at any junction, and not going twice along any stretch of road, which meets two requirements: (1) It is as long as possible; (2) subject to that, it consists of as few “legs” as possible. In addition I should prefer a route which includes every junction, if that is possible without making the route shorter or leggier.

How many miles, and how few legs, in a route which best meets my requirements and my preferences?

[enigma108]

Advertisements

%d bloggers like this:

I found this one quite challenging to solve. I would have liked to write a program that avoids some of the specific analysis for the 6×6 case, but it was taking long enough as it is. So if anyone has any ideas for speeding up a more generic solution then let me know.

I started by considering the graph of an

n×ngrid. Let’s divide the vertices (junctions) into three kinds: (1) the 4 at the corners of the grid (corner vertices), (2) those along the sides of the grid (side vertices); (3) those interior to the grid (interior vertices).We note that there are no edge vertices or interior vertices if

n= 1, and ifn≥ 2 then the side vertices (of which there are 4(n– 1)) all have odd degree (there are 3 roads that meet at them). The corner vertices always have degree 2 and the interior vertices always have degree 4.In the case of a 6×6 grid we have 20 side vertices.

A path that traverses every edge of a graph exactly once is known as a

Eulerian path[ http://en.wikipedia.org/wiki/Eulerian_path ] and is only possible in graphs that have two vertices of odd degree, and these are the start and finish vertices of the path. And every connected graph with two vertices of odd degree has a Eulerian path, and this will give us a maximum length journey on the grid. So we need to find the maximal subgraphs (i.e. with the minimum number of edges removed) of our original grid that have only two vertices of odd degree, and examine them to find paths with the fewest number of legs.Looking at the 5 side vertices along each side of the grid, we can reduce the number of odd degree vertices along the side from 5 to 1 by removing two of the edges (as shown in the diagram below).

Hence with the removal of 8 edges from the graph we can reduce the number of vertices of odd degree from 20 to 4. Now, if two of the remaining vertices of odd degree are positioned such that they are adjacent to a corner vertex, then we can remove two edges that form a path between them to turn them into vertices of even degree.

However the first of these (C1) leaves a disconnected vertex, so although it will be possible to create a Eulerian path on the grid it won’t include all the junctions (as requested in the problem statement). But we must still consider such grids, as they may give the fewest number of legs in the journey (a requirement which is more important than visiting all the junctions).

So we consider the grids where the bottom-left corner is one of (C1) or (C2) and the top and right sides of the grid are some combination of (S1), (S2) and (S3). Giving us 2 × 3! = 12 subgraphs to consider.

The following program examines the 12 subgraphs to find Eulerian paths with the minimal number of legs. It runs in 48m48s – although it finds the solution pretty much straight away – most of the time is spent completing the exhaustive search. With the pruning away of paths longer than the best we’ve found the run time varies depending on the order in which the subgraphs are considered.

Solution:The longest possible journey is 74 miles. There are 22 legs in the journey. It is possible to visit every junction.There are two more solutions that are equally long and have the same number of legs, but omit one junction (although I think they are more pleasing on the eye).

The maximum path length on an

n×ngrid is given by the OEIS sequence A049486 [ http://oeis.org/A049486 ], although this doesn’t tell you what the minimum number of legs required is.