Permutation procedure for the backboard-wiring problem

A general method is described for solving the backboard-wiring problem. This problem is concerned with placing logic elements in an array of positions to minimise some function of the connection pattern such as total wire length. Any placement of the elements can be expressed as a permutation, and the proposed procedure determines a permutation which is optimal with respect to a given set of exchanges. It is thus possible to balance the quality of optimisation against the computational cost. The results show that simple sets of exchanges can offer marked improvements on a Monte Carlo search.