An Efficient Variable-Cost Maze Router

A variable cost maze router is described. The router is substantially faster than most other maze routers and also provides a flexibility which is valuable in a variety of ways. It is particularly well suited for use on multiple layer routing surfaces in which adjacent layers have primary wire directions which are perpendicular to each other. The router has been incorporated as a final phase into both a circuit board routing system and an LSI gate array router. Experience with these systems is described. Potential applications of the variable cost ability are also discussed.