Heuristics in the routing algorithm for circuit layout design

New heuristics in solving the maze routing problem are presented. The proposed MQ algorithm generates a shortest path based on the depth-first vertex traversal approach in the direction towards the target. A set of heuristics is formulated by assigning a directional priority sequence to each vertex while finding the path. This method will find a shortest path between two points, if one exists, on a rectangular grid-of vertices. Some vertices, named blocking vertices, are occupied by other circuitry or by paths already routed, and hence are not available for routing. Blocking vertices are introduced as a means of modelling obstacles during the path finding process. An implementation of the algorithm and its experimental results are also reported.