Maze routing algorithms are widely used for finding an optimal path in deta
iled routing for very large scale integration, printed circuit board and mu
ltichip modules In this paper, me show that finding an optimal route of a t
wo-pin net in a multilayer routing environment under practical via design r
ules can be surprisingly difficult, A straightforward extension to the maze
routing algorithm that disallows via-rule incorrect routes may either caus
e a suboptimal route to be found, or more seriously, cause the failure to f
ind any route even if one exists, We present a refined heuristic to this pr
oblem by embedding the distance to the most recently placed via in an exten
ded connection graph so that the maze routing algorithm has a higher chance
of finding a via-rule correct optimum path in the extended connection grap
h. We further present efficient data-structures to implement the maze routi
ng algorithm without the need to preconstruct the extended connection graph
, Experimental results confirmed the usefulness of our algorithm and its ap
plicability to a wide range of CMOS technologies.