--------
A --| |-- B
| ckt? |
B --| |-- A
-------- What is the minimum number of gates needed?
Source: Original extension of a problem from John Guilford (Agilent Technologies) as quoted in Macalester Problem of the Week #919.
Igor Volov provided a good explanation of the standard solution, which results in a 13-gate solution:
The simplest way to swap two variables X and Y is
X=X XOR Y
Y=X XOR Y
X=X XOR Y
so the circuit is
X ---\----XOR--> Y
\ /
XOR
/ \
Y ---/----XOR--> X
and the plain circuit for XOR is
X ---\---------AND-
\ / \
AND--NOT OR --> X XOR Y
/ \ /
Y ---/---------AND-
We get planar circuit of 15 gates. If we simplify the circuit we
shall get the following
---------------- AND
/ / \
/ NOT-- OR--> Y
/ / \ /
/ / AND
/ / /
X ---<---------AND- /
\ / \ /
AND--NOT OR --
/ \ / \
Y ---<---------AND \
\ \ \
\ \ AND
\ \ / \
\ NOT-- OR--> X
\ \ /
---------------- AND
The circuit is of 13 gates.
| |
A| |B
| |
/ \ / \
/ \ / \
+-----+ +-----+ +-----+
| NOT | | AND | | NOT |
+-----+ +-----+ +-----+
| | |
| | |
| / \ /
| / \ /
| / \ /
| / +----+
| | | OR |
| | +----+
| | |
| | |
| | / \
| | / \
| | +-----+ \
| | | NOT | \
| | +-----+ \
| | | |
| | | |
| \ / |
| \ / |
| +----+ |
| | OR | |
| +----+ |
| | |
\ | |
\ / \ |
\ / \ |
+----+ \ |
| OR | \ |
+----+ \ |
| \ |
| | |
/ \ | |
/ \ | |
| +-----+ | |
| | NOT | | |
| +-----+ | |
| | | |
| | | |
| \ / |
| \ / |
| +----+ |
| | OR | |
| +----+ |
\ | |
\ | |
\ / \ /
\ / \ /
+-----+ +-----+
| AND | | AND |
+-----+ +-----+
| |
B| |A
| |
Al's Programming Commentary:
Much to my own surprise, the data structures and the algorithm were almost trivial. Here's how it played out.
Note that any line in a two-input circuit is a boolean function of the two inputs (say, A and B) and can therefore be represented by a number from 0 to 15. For clarity, those 16 values can be represented as a binary value from 0000 to 1111. False is represented as 0000. True is 1111. If we represent the boolean function "A" as 0011 and "B" as 0101, then "A AND B" is (0011 AND 0101) = 0001; "A OR NOT B" is 1011; and so forth.
A two-input circuit can have any number of outputs. If the circuit is planar we can list those outputs from left to right (or top to botton, depending on how you've oriented the circuit). So any such circuit's outputs can be specified as a sequence of numbers, each such number being from 0000 to 1111. If we use 16 different characters to represent 0000 thru 1111, then the outputs of the circuit can be represented by a string of characters. In my program, I used "@" to represent 0000 and the letters "a" through "o" to represent 0001 through "1111". So the empty circuit (having inputs A and B, outputs A and B, and no gates) is represented by the string "ce". If we add an AND gate we have a circuit with a single output, A AND B, and this circuit's outputs are thus represented by the string "a". Our target circuit, which has outputs of B and A, has outputs represented by "ec".
Forking lines in our circuit are going to cause us a problem. To circumvent those problems, we create a conceptual "pseudo-gate" which accepts one input and outputs two exact copies.
If we have a planar two-input circuit, we can attach an additional gate to one (if we are attaching a NOT or a pseudo-gate) or two (if we are attaching an AND or an OR) of its outputs. Note that if we attach an AND or an OR, the two outputs to which we attach the gate must be adjacent (otherwise the intervening outputs would dead end). How does attaching an additional gate effect the string which represents the circuit's outputs?
If we attach a NOT, then one of the letters in the string will change. If we attach a pseudo-gate, then one of the letters will be replicated. If we attach an AND or an OR, then a pair of adjacent letters will merge.
So the processing goes like this. Start with the string representing the outputs A and B (that's the string "ce"). Generate all successor circuits, that is, all circuits with one additional gate (those are the strings "le", "cj", "cce", "cee", "g", and "a"). Store each of these successors along with the string from which it was derived (so that we can backtrack when we reach our goal). And just keep on generating successors until we get out target "ec".