Cross the wires without crossing the wires: fill the black box with some quantity of NAND gates.

logic/crossing.wires New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Cross the wires without crossing the wires: fill the black box with some
quantity of NAND gates.

    input          output

A -----> +-------+ -----> B
         | black |
B -----> |  box  | -----> A
         +-------+

I found this problem in a computer magazine.  There is a U.S. patent
with the optimal solution.

[ Editor: that is, the signals on the two lines are to be exchanged by a
planar circuit of NAND gates, with no wires crossing. ]

Show solution

I have a solution that uses 10 2-input nand gates,
4 to generate A xor B,
3 more to generate B,
3 more to generate A.

-- Dennis Yelle <dennis@netcom.com>

THE EIGHT-GATE SOLUTION

In the eight-gate circuit there is one 3-input nand-gate!
And two single-input nand-gates!

A ---+---------------|\                    |\    |\
     |               | O---+---------------| O---| O--- B
     |           /---|/    |           /---|/    |/
      \___|\    |           \---|\    |
          | O---+---------------| O---+
      /---|/    |           /---|/    |
     |           \___|\    |           \___|\    |\
     |               | O---+---------------| O---| O--- A
B ---+---------------|/                    |/    |/

PS:

NAND(a) = NAND(a,a) = NOT(a)
                               a
a ----|)o----- b      =         =====|)o----- b
                               a

-- Jose Manuel Oliveira <si504340@ci.uminho.pt> (poser of the problem)