# Logic gate puzzle

I have a game on my phone (Circuit Scramble on Android) which is a game in which you need to work out what set of inputs and switch positions will allow you to power the "level complete" sign.

I have found one puzzle from the randomly generated section which I cannot find a solution for: The options you have to choose from are to toggle any of the inputs at the bottom and to move either of the switches in the middle of the puzzle.

To complete the level all of the inputs to the top must be ON.

I've also created a play version of this on a cool site I found: https://simulator.io/board/F0aztyxm5D/1 - I couldn't work out how to do switches so you'll need to just add wires in to match the position of your switch. Also the NAND, NOR and XNOR are simulated by a NOT gate following the appropriate gate.

My current logic is as follows (hidden in case anybody wants to puzzle over it themselves first - please note that I believe this puzzle has no solution):

The AND on the top row must have both of its inputs set which means that likewise the AND in the row below that and the one below that must all have their inputs (and outputs) set. If we then look at the NOR gate in the second row because the AND below it must be outputting then it must be getting an input which means it will never output anything. This in turn means that the XOR on the top left must be receiving an input from its left hand connection.

This means that the XOR on the second row must be receiving one and only one input. This means either the XNOR on the third row must be outputting or the AND on the bottom left must be outputting. THE XNOR in question is already getting an input on its right terminal (the OR needs to power the AND) which means the only way it can output is if the left terminal is also on. However the left terminal being on means that the XOR above is now getting input on both its terminals. It is however obvious that we can't power the left wire without also supplying to the XNOR which we've just established is wrong.

So that's my logic that suggests this is impossible.

So the question: Is there a valid solution to this puzzle such that all three wires at the top are powered?

Appendix 1 - Element Logic

AND - output ON only if both inputs are ON
OR - output ON if one or both of the inputs are ON
XOR - output ON if one and only one input is ON
NAND - output OFF only if both inputs are ON (same as AND but output reversed)
NOR - output OFF if one or both of the inputs are ON (same as OR but output reversed)
XNOR - output ON if both inputs are the same (ie both ON or both OFF) (same as XOR but output reversed)
SWITCH - the input is transmitted to the side the switch is on, the other output is always off. eg if switch is left and input is ON then left is ON and right is off. If the input is OFF both are OFF. Wires - In the image Wires are either yellow or blue and white. They are both the same. The difference is because the blue and white show ones that are currently ON in the visible configuration.

• Not sure if there are any more relevant tags for this. It feels very untagged at the moment due to how broad the logical deduction tag seems to be... Jul 11 '17 at 11:45
• Does a switch send the signal below to whichever side above the switch position is, and an OFF to the other side? Jul 11 '17 at 12:01
• @GarethMcCaughan: That is correct, yes. I'll add a note to that effect. Jul 11 '17 at 12:05
• @Chris What are the blue with white dot lines? Jul 11 '17 at 13:06
• Wow, I just downloaded and played this yesterday. I do agree with your conclusion that this puzzle is not solvable. Jul 11 '17 at 20:03

I also think this is unsolvable. My reasoning resembles Chris's:

1. Top-right AND must have both inputs 1.
2. Right-hand switch must be positioned right, and input to that switch must be 1.
3. Output of AND gate below that switch must be 1, so both its inputs must be 1.
4. Output of AND gate below that must be 1, so both its inputs must be 1.
5. Right-hand input of XNOR gate near bottom left is 1, so left-hand input and output must be equal.
6. The two inputs to the XOR at middle left are equal, so output is 0.
7. Top-left XOR's left input is 0, so its right input must be 1.
8. Output of middle-left NOR must be 1, so its inputs must both be 0.
9. Now we have a contradiction, because 3 says left input of middle-right AND is 1 but 8 says right input of middle-left NOR is 0, but those two are tied together.

I've also brute-forced it by computer; of course my code may have bugs but probably not the same bugs as my reasoning above. This displays intermediate results as well as final output.

for n in range(1<<6):
s = (n>>4)&1, (n>>5)&1
r = n&1, (n>>1)&1, (n>>2)&1, (n>>3)&1 # just above bottom gates
t = [r]
r = r, 1-(r^r), r&r, r|r, r
t.append(r)
r = r^r, 1-(r|r), r&r, r|r
t.append(r)
r = r, (1-s)&r, s&r, (1-s)&r,s&r, r
t.append(r)
r = r^r, 1-(r&r), r&r
t.append(r)
win = r&r&r
print("%.02d"%n,t,win)


Notice that no line of its output ends in a 1.

• Thanks for taking the time to look. I'll not accept the answer immediately just in case something else comes along. Hopefully I won't forget to come back here and accept later. :) Jul 11 '17 at 12:15

It's easier to see what's going on with a diagram. Working down from the top, we can see the following: Then working up from the bottom (ignoring the right hand side, which is easy but irrelevant), we can see the following: And we have a contradiction in the top-left XOR.