# Hexcellent Minesweeping

Hexcells is a game based off of Minesweeper played on hexagons. (Full disclosure: I have nothing to do with Hexcells. In fact I don't really like the game.) Most of Hexcells rules can be pretty easily expressed in Generalized Minesweeper (Minesweeper played on an arbitrary graph). The one that is most difficult is the {X} and -X- rules.

The {X} rule tells us that a cell borders X mines and that all of these mines border each other in a continuous path. For example if we had the board:

  ?   ?

?  {3}  ?

?   ?


The 6 possibilities for mine placement would be

  *   .       .   .       .   .       .   *       *   *       *   *

*  {3}  .   *  {3}  .   .  {3}  *   .  {3}  *   .  {3}  *   *  {3}  .

*   .       *   *       *   *       .   *       .   .       .   .


Your goal is to implement the rule {3} in generalized Minesweeper.

## Specifics

Generalized Minesweeper is 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 the player how many adjacent vertices are on (mines) and does not count as a mine itself.

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

Your goal is to build a structure in Generalized Minesweeper such that there are 6 specific cells that can only have states that fulfill as if they were connected with the Hexcells rule {3}. 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, but you can always improve your score by removing such cells)

## Scoring

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

## Solvability

This problem is solvable, I have a solution to this problem and I will post it once this challenge is a week old.

• So there always need to be 6 edges between the 6 input vertices? Commented Jan 28, 2018 at 21:50
• @Bergi edges between value cells are redundant, as they have no meaning Commented Jan 28, 2018 at 21:57
• @H.PWiz But the "{3} rule" says "all of these mines border each other in a continuous path" - without edges there is no path. Commented Jan 28, 2018 at 22:03
• @Bergi but the task is create a graph such that are 6 cells that act "as if they were connected with the Hexcells rule {3}". They need not be connected Commented Jan 28, 2018 at 22:06
• @Pavel Generalized minesweeper is a programming language as far as I am concerned. It may be very esoteric, but I don't think it is too far off from proof-golf. Commented Jan 29, 2018 at 2:17

# 7 5 vertices, 14 10 edges

(Graph made with this online tool and paint.)

A-F are our six nodes, and J is a helper node. The three 1-nodes enforce that opposite nodes are different, while the 2-node makes sure that A, C and E can neither be all mines, nor all empty.

Edit: -2 vertices thanks to CalculatorFeline and H.PWiz!

• You can remove 2 vertices. Commented Jan 28, 2018 at 21:15
• Note that the 2-J structure also ensures that ACE are not all empty. Commented Jan 29, 2018 at 1:21

# 44 vertices, 66 edges

First, we start with a ring of 6 value cells all connected to a 3. These cells will be the cells with the {3} rule.

  A   B
\ /
F---3---C
/ \
E   D


Then, we attach 012 sensors to the value cell pairs (AB,BC,CD,DE,EF,FA). The structure of the 012 sensor is below.

O   ?---1---?
\ /       /
2---?---1
/ \
A   B


A and B are the inputs to the sensor and O is the output. The ? cells are generic value cells. O will be a mine if exactly one of A and B is a mine and empty otherwise. Then, we connect a 2 node to all the sensor outputs. This ensures that there are exactly 2 pairs with exactly 1 mine, and it can be proven that the only configurations that satisfy this are the ones that satisfy {3}. Each sensor takes 7 nodes, so 6 sensors requires 42. Add the 3 node connected to ABCDEF and the 2 node connected to the outputs and you get 44.

This solution can also be adapted for {1}-{5} by changing the 3 node to some other value.

• What are the outputs for each 012 sensor? Also, I only count 6 nodes in your 012 Commented Jan 28, 2018 at 20:36
• There's the 2 node, the 2 1 nodes, the 3 ? nodes, and C (which is not one of the ABCDEF nodes, just the output of the sensor). Commented Jan 28, 2018 at 21:01
• @CalculatorFeline Got it, maybe rename C to O, since C is in ABCDEF Commented Jan 28, 2018 at 21:30
• Fun fact: This solution is planar. Commented Jul 23, 2018 at 18:00

# 9 Vertices, 17 Edges

Where ? is a value cell, that is not one of the 6 we care about, we need the following subgraph.

    ___________
?  /    ?      \?
\|    /|\     /
3¯¯¯¯ 1 ¯¯¯¯2
|\    |    /|
| \ /¯|¯¯¯¯ |
|  X  |     |
/  / \_|___  \
A__/    B   \__C


With those 6 vertices set up: ABC can have the following states: 111, 110, 011, 000, 100, 001

With the cells corresponding to the following hexagon, all we then need are 3 more indicator cells A-1-D, B-1-E, C-1-F

  B  C
A      D
F  E

• It would be a lot smaller if you checked A,C,E instead of A,B,C. Commented Jan 28, 2018 at 21:06
• @CalculatorFeline I can't see why... Commented Jan 28, 2018 at 21:09
• If you remove the ABC check device from your solution, it almost works, except that it also allows ACE and BDF. In those, the # of mines in ACE is either 0 or 3, but in a valid solution it's 1 or 2. This allows you to have a score of 5. Commented Jan 28, 2018 at 21:13
• @CalculatorFeline Right, and that would be Laikoni's answer minus 2. I see now. This is definitely hard to convey with text Commented Jan 28, 2018 at 21:23
• @CalculatorFeline Since it doesn't contain the main idea of my submission, I won't post it. I think Laikoni will Commented Jan 28, 2018 at 21:36