Problem 7

Two railway engineers are designing the route of 'Low-Speed 2' - a new railway designed to connect four towns together.

"It's got to go through all four towns: Pythagaby, Gaussington, Wileshaven, Ollerenshaw," said the first. "It will start at Pythagaby and end at Ollerenshaw."

"And railways can't pass through mountains," said the second.

"And each section of the railway can only run north-south or east-west: no diagonals to cut corners! So we can plan it out on a square grid," said the first. They sketched the map below, with Pythagaby, Gaussington, Wileshaven and Ollerenshaw at A1, D3, G6 and J9 and mountains at D5, F6, F7, I3.

"Trains can go very fast on straight sections of track," said the first. "As this is Low-Speed 2, we'd better make sure there aren't any long straight sections."

"Good idea," said the second. "We won't have the railway passing through four or more consecutive squares in a straight line. And that includes 4 squares that go through a town."

"What about branch lines?" asked the first. “And could the railway double back on itself?"

"No," said the second, after some thought. "It must be one continuous line and it can't double back, so no U-shaped bends are allowed. Also, the railway must enter and leave each town through a different square."

"Also, the railway can't pass too close to itself," said the first. "Each square the railway passes through can only be adjacent (horizontally or vertically) to two other squares that the railway passes through. But just for clarity: adjacent doesn't include diagonals."

"And we've got a very precise budget for this project," said the second. "The railway must pass through exactly 6 squares between Pythagaby and Gaussington (excluding the towns themselves), then through exactly 15 squares between Gaussington and Wileshaven (excluding the towns themselves), and finally through exactly 5 squares between Wileshaven and Ollerenshaw (again, excluding the towns themselves)."

They both stared at the map. “There’s quite a few different ways to do this aren’t there?” said the first. The second nodded.

How many different possible routes are there for the railway, subject to the constraints given above?