Get Two from One

Question

As we saw in this question complex logical statements can be expressed in terms of the simple connectives of generalized Minesweeper. However Generalized minesweeper still has redundancies.

In order to avoid these redundancies we define a new game called "Generalized-1 Minesweeper".

Generalized-1 Minesweeper is a version Minesweeper played on an arbitrary graph. The graph has two types of vertex, an "indicator" or a "value". A value can be either on or off (a mine or a dud) however its state is unknown to the player. An indicator tells that exactly one of the adjacent cells is on (a mine). Indicators do not count as mines themselves.

For example the following board for Generalized Minesweeper tells us that cells A and B are either both mines or neither of them are mines.

(In the diagram indicators are marked in gray while values are white)

Unlike in normal minesweeper where you click values that are off to reveal indicators, there is no such mechanic in Generalized Minesweeper. A player simply determines for what states of the graph can satisfy its indicators.

Your goal is to make a 2 in Generalized-1 Minesweeper. You will build a structure in Generalized-1 Minesweeper such that there are 8 specific cells for which all possible configurations of values have exactly two cells on. This means it behaves exactly as the 2 does in traditional minesweeper. When you write your solution you should not have specific values in mind for value cells. (In answer to H.PWiz's question it is allowed that some value cells might be deducible from the state)

Scoring

You answers will be scored by the number of vertices in the final graph minus 8 (for the 8 inputs) with a lower score being better. If two answers tie in this metric the tie breaker will be the number of edges.

Answer 1

42 vertices, 56 edges

Each variable is a value vertex, and each box is an indicator vertex with edges to the variables inside it. The inputs are x₁, ..., x₈. For example, here's a solution with mines at x₃ and x₅, with mines highlighted in green.

The horizontal constraints ensure that exactly one of the a's and exactly one of the b's has a mine. In those two columns, r does not hold a mine, but it does in the other six columns. (Note that a and b can't both have a mine in the same column.) Each input x is opposite the r in its column, so exactly two inputs have mines as desired.

For k inputs, this uses 5k+2 vertices (3k value and 2k+2 indicator), and 7k edges. Here, k=8 inputs gives 42 vertices and 56 edges.

Answer 2

50 Vertices, 89 edges

Based on the logic gate from H.PWiz's answer.

  A&B      C&D      E&F      G&H
   |        |        |        |
b--1--a  d--1--c  f--1--e  h--1--g
|  |  |  |  |  |  |  |  |  |  |  |
1--?--1  1--?--1  1--?--1  1--?--1
|     |  |     |  |     |  |     |
A     B  C     D  E     F  G     H

Each * is on when the two respective inputs are on. To handle the case of a single input, we use the intermediate values a=A&!B etc. Connecting all three values a, b and A&B to the input of a secondary level of gates gives us an effective input of A|B (this saves vertices over !(!A&!B)):

      *              *
      |              |
   #--1--#        #--1--#
   |  |  |        |  |  |
   1--?--1        1--?--1
  |||   |||      |||   |||
  A|B   C|D      E|F   G|H

These *s are on if two of their inputs (corresponding to four of the original inputs) are on, except in the case of the pairs already covered above. Meanwhile, we can connect the #*# nodes to a final gate. We therefore have the following results:

A&B
C&D
E&F
G&H
(A|B)&(C|D)         [4 cases]
(E|F)&(G|H)         [4 cases]
(A|B|C|D)&(E|F|G|H) [16 cases]

These cover all 28 of the cases of two inputs. It then remains to connect a final indicator to these seven values. If fewer than two inputs are on, then none of these will be on, so the indicator will be off. If more than two inputs are on, then more than one of these will be on, and the indicator will be off.

Answer 3

197 Vertices, 308 edges

I came up with this answer last night, but withheld posting it because it was such a high score. However, since it beats the other answer by so much, I though I should post it.

I use the following set up on all 28 pairs of values cells in ABCDEFGH

   ?*
   |
?--1--?
|  |  |
1--?--1
|     |
A     B

? represents an value cell not in ABCDEFGH. Here, when ?* is ON, A and B are both on. Otherwise, A and B could be in any other configuration.

I connect all 28 ?*s to one indicator cell. This means that only one pair in ABCDEFGH will have two ON. Which is sufficient to enforce that exactly two of my output cells will be ON

Answer 4

354 nodes, 428 edges

Just to prove it's possible. I will improve this later with some caching.

(hopefully no code error)

I tried to write a Mathematica program here to check program validity, but it doesn't work probably because there are too many variables.

The result was generated by computer program: Try it online!

---

I use a gate that looks like this:

               (f)
                |
                |
               (#)
              /   \
             /     \
           (d)     (e)
          /           \
         /             \
       (#) --- (c) --- (#)
     .'                  '.
   .'                      '.
(a)                          (b)

where (#) are 1-indicators, (a) .. (f) are values.

Then,

c = (not a) and (not b)
d = (not a) and      b
e =      a  and (not b)
f =      a  xnor     b

Also, this gate

(a) ----- (#) ----- (b)

gives

b = not a

. Use those two types of gates you can build any expressions.

Of course, this one is for asserting that (a) must be true:

(a) ----- (#)

Answer 5

81 Nodes, 108 Edges

Using 13 nodes and 14 edges, we create the following Adder gate (C(arry) = X AND Y, S(um) = X XOR Y):

X--1--------------?
   |              |
   ?--1--S--1--?--1
   |  |           |
   |  C           |
Y--1--------------?

Use four Adders M1, M2, M3, M4 to add A+B, C+D, E+F, G+H, respectively, with the resulting carry C1, C2, C3, C4, and sum S1, S2, S3, S4.

Use two Adders M5, M6 to add S1+S2, S3+S4, with the resulting carry C5, C6, and sum S5, S6.

Use one Adder M7 to add S5+S6 to get C7 and S7.

Now connect all carries to a single indicator node like the following:

C1-|
C2-|
C3-|
C4-+-1
C5-|
C6-|
C7-|

and force S7 (the modulo 2 of sum of 8 values) to be 0 by this circuit:

S7--1--?--1

I argue that this circuit forces exactly two values from ABCDEFGH to be ON, since it can only be an even number (since S7 is 0), and there cannot be more than 3 ON values (since only one of C1-C7 is ON).