10
\$\begingroup\$

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.

Simple game

(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.

\$\endgroup\$
  • \$\begingroup\$ Does any edge always connect an indicator vertex and a value vertex? \$\endgroup\$ – xnor Jan 31 '18 at 22:15
  • \$\begingroup\$ @xnor In order to maximize your score they ought, but I don't feel like I need to make that a rule. Edges that don't connect values to indicators don't change the behavior of the graph. \$\endgroup\$ – Sriotchilism O'Zaic Jan 31 '18 at 22:16
  • \$\begingroup\$ When 6 is subtracted from the score, what are the 6 inputs? Aren't there 8 cells? \$\endgroup\$ – xnor Jan 31 '18 at 22:21
  • \$\begingroup\$ @xnor Sorry should be 8. Fixed now. \$\endgroup\$ – Sriotchilism O'Zaic Jan 31 '18 at 22:22
  • \$\begingroup\$ What do you mean by "structure...such that there are 8 specific cells that the only possible configurations of values have exactly two cells on."? Are the only possible configurations supposed to have only two mines? \$\endgroup\$ – dylnan Jan 31 '18 at 23:06
6
\$\begingroup\$

42 vertices, 56 edges

Mines network

Each variable is a value vertex, and each box is an indicator vertex with edges to the variables inside it. The inputs are x1, ..., x8. For example, here's a solution with mines at x3 and x5, with mines highlighted in green.

Mines network solution

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Ah, I had similar idea, but ended up creating a more complicated version of this. Good job! \$\endgroup\$ – justhalf Feb 1 '18 at 22:58
  • \$\begingroup\$ I'm not convinced that there are 43 vertices. You clearly show 42, so you're saying you only need one more to connect it all up? \$\endgroup\$ – H.PWiz Feb 1 '18 at 22:58
  • \$\begingroup\$ Actually, if I have drawn correctly the graph you describe, I think it allows for states like ACE, BDF, ADG ... \$\endgroup\$ – H.PWiz Feb 1 '18 at 23:23
  • \$\begingroup\$ @H.PWiz I see what you mean... I think maybe I can solve that with extra edges to give the expression (a&b)+((a|b)&(c|d))+(c&d)+((a|b|c|d)&(e|f|g|h))+(e&f)+((e|f)&(g|h))+(g&h)==1, does that look right to you? \$\endgroup\$ – Neil Feb 2 '18 at 0:12
  • \$\begingroup\$ Maybe, although to me that expression looks like it solves the problem entirely. And I have no idea what edges you can add to get that... \$\endgroup\$ – H.PWiz Feb 2 '18 at 0:20
2
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Note that in the gate you have each of the 4 ?s corresponds to one of the 4 states of A B. \$\endgroup\$ – Sriotchilism O'Zaic Feb 1 '18 at 19:03
  • \$\begingroup\$ @HeebyJeebyMan Interesting, I hadn't considered that. I just found this gate by luck \$\endgroup\$ – H.PWiz Feb 1 '18 at 19:08
1
\$\begingroup\$

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) ----- (#)
\$\endgroup\$
1
\$\begingroup\$

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).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.