Generating and counting valid patterns in routes between two points (Q1080436)

Given two points on a plane, any rectilinear route between them can be specified by directions (N,E,S,W for respectively North, East, South and West) and lengths of constituent line segments. Ignoring the length of a line segment, a word over the alphabet \(\{\) N,E,S,W\(\}\) is defined to represent a sequence of directions. In this paper the author characterizes and counts all valid words, that is, those words representing non-selfcrossing routes. From a practical point of view, a shortest route with few turns is often desired in the wire-routing design for printed circuit boards and integrated circuits.