A Tile-Expansion Router

A router based on a tile-expansion algorithm and corner stitching data structure is presented. This program finds connections with a minimum number of jogs and it ensures that a possible solution will be found. Using a working tree, it allows an exhaustive and recursive search along all available areas for routing. The connections are made going back through the working tree until the starting terminal is reached. There are two Manhattan layers that the user can choose for each direction to implement connections; the router can be used to wire hierarchical blocks using a chip planning methodology. The program has been successfully tested on examples concerning different classes of problems.