UDC 681.142.32

CYBERNETICS

AND CONTROL THEORY

G. G. RYABOV

ON AN ALGORITHM FOR SOLVING A MAZE ON A DISCRETE FIELD AND ITS APPLICATION

(Presented by Academician S. A. Lebedev on May 28, 1965)

One of the most labor-intensive stages in the process of manufacturing modern electronic computers is the preliminary layout and production of multilayer printed wiring. The layout problem reduces to solving a maze problem on a discrete field. In paper (¹) an algorithm is considered for solving a maze on a discrete field, the essence of which consists in modeling wave propagation. The source of propagation is one of two points that are to be connected by a line without intersection with the obstacles located on the field. The key point of this method is the choice of the points nearest to a given one—the construction of a neighborhood (which we shall conventionally call the choice of a discrete topology). In (¹) the points \((i, j - 1)\), \((i + 1, j)\), \((i, j + 1)\), \((i - 1, j)\) are regarded as nearest to the given point \((i, j)\) (see Fig. 1). As is not hard to see, in the proposed algorithm the paths connecting points (cells of the field) will have as components only vertical and horizontal straight lines. Therefore in (¹) such a choice of discrete topology is called Manhattan geometry.

Fig. 1

Fig. 2

In the present article, the algorithm proposed in (¹) is further developed in the direction of choosing other discrete topologies and of passing to the spatial case, which is of substantial importance for practical applications.

1. Covering the field with non-square cells. Let us consider, for example, two concrete cases:

a) Covering the field with equilateral triangles. Those triangles that have one common side with a given triangle are regarded as nearest to it. This method induces the drawing of paths with components whose angles of inclination are \(\pi/6\), \(\pi/2\), \(5\pi/6\) (Fig. 2).

b) Covering the field with regular hexagons. Those hexagons that have a common side with a given one are regarded as nearest to it. Such a method induces the drawing of paths with components \(0\), \(\pi/3\), \(2\pi/3\).

1. In the case of a square grid, other discrete topologies can also be chosen. Thus, in the case when the points nearest to the point \((i, j)\) are taken to be
   \((i, j - 1)\); \((i + 1, j - 1)\); \((i + 1, j)\); \((i + 1, j + 1)\); \((i, j + 1)\); \((i - 1, j + 1)\); \((i - 1, j)\); \((i - 1, j - 1)\), the components of the connections will have slopes \(0\); \(\pi/4\); \(\pi/2\); \(-\pi/4\). In this case, intersection of components \(\pi/4\) and \(-\pi/4\) at an angle \(\pi/2\) will be permitted. (The method is applicable in the case where it is possible to spray dielectric onto conductors at the points of intersection with other conductors.)

If, from the set of points nearest to the given one, either \((i + 1, j + 1)\); \((i - 1, j - 1)\), or \((i + 1, j - 1)\); \((i - 1, j + 1)\), is discarded, then in the first case the components of the connections will have angles of inclination \(0\); \(\pi/2\); \(-\pi/4\), and in the second \(0\); \(\pi/2\); \(\pi/4\).

1. The transition from the planar case to the spatial case is of greatest value for practical application to multilayer assembly. In this case, a certain region of space is divided into cubes, tetrahedra, etc., and the problem of finding a way out of the labyrinth is solved in space. Thus, in the case of Manhattan geometry, the points nearest to the point \((i, j, k)\) are considered to be
   \((i, j - 1, k)\); \((i + 1, j, k)\); \((i, j + 1, k)\); \((i - 1, j, k)\); \((i, j, k + 1)\); \((i, j, k - 1)\) (see Fig. 3). The modifications mentioned above are applicable to the spatial case.

Although the algorithm solves the problem of the shortest connection of two points only in the presence of existing obstacles, in the spatial case it can be effectively applied to routing conductors in many layers, since a connection may pass from one layer to another.

Fig. 3

Fig. 4

At the Institute of Precision Mechanics and Computer Engineering of the USSR Academy of Sciences, a corresponding program has been created for the automatic production, on an electronic computer, of conductor routings for multilayer printed wiring. The input information is a table of contact connections on the board. A discrete topology was chosen that allowed paths on the \(k\)-th layer with components \(0\); \(\pi/2\); \(\pi/4\), and on the \((k + 1)\)-th layer with components \(0\); \(\pi/2\); \(-\pi/4\), in order to reduce interference in adjacent layers. The average running time of the program on a high-performance computer—

for circuits with up to 800 contacts and up to 400 conductors for two-layer wiring is 1–2 hours.

The program size is about 1000 instructions. The program includes, as components, programs for preliminary ordering and for “smoothing” after placement. The output information consists of the trajectories of all connections, with the layer indicated. In Fig. 4 examples are given of two layers of printed wiring for one of the circuits obtained automatically.

The proposed method is a gradient-descent method for the discrete case. In the continuous case, over the plane of the maze it is necessary to construct a surface formed by cones with vertices at the points that are to be connected and at the endpoints of the obstacles. The projection onto the plane of the path of descent along the surface from one point to another will be the shortest path in the plane between these two points without intersecting the obstacles.

Institute of Precision Mechanics
and Computer Engineering
of the Academy of Sciences of the USSR

Received
25 V 1965

CITED LITERATURE

¹ C. J. Lee, IRE Trans. EC, No. 3, IX, 346 (1961). ² V. A. Tyurenkov, Collection: Computing Systems, no. 6, 1963.