13
\$\begingroup\$

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.

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

\$\endgroup\$
  • \$\begingroup\$ So there always need to be 6 edges between the 6 input vertices? \$\endgroup\$ – Bergi Jan 28 '18 at 21:50
  • \$\begingroup\$ @Bergi edges between value cells are redundant, as they have no meaning \$\endgroup\$ – H.PWiz Jan 28 '18 at 21:57
  • \$\begingroup\$ @H.PWiz But the "{3} rule" says "all of these mines border each other in a continuous path" - without edges there is no path. \$\endgroup\$ – Bergi Jan 28 '18 at 22:03
  • \$\begingroup\$ @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 \$\endgroup\$ – H.PWiz Jan 28 '18 at 22:06
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Wheat Wizard Jan 29 '18 at 2:17
15
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can remove 2 vertices. \$\endgroup\$ – CalculatorFeline Jan 28 '18 at 21:15
  • \$\begingroup\$ Note that the 2-J structure also ensures that ACE are not all empty. \$\endgroup\$ – CalculatorFeline Jan 29 '18 at 1:21
3
\$\begingroup\$

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

My ASCII-art skill are dreadful.

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
\$\endgroup\$
  • \$\begingroup\$ It would be a lot smaller if you checked A,C,E instead of A,B,C. \$\endgroup\$ – CalculatorFeline Jan 28 '18 at 21:06
  • \$\begingroup\$ @CalculatorFeline I can't see why... \$\endgroup\$ – H.PWiz Jan 28 '18 at 21:09
  • \$\begingroup\$ 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. \$\endgroup\$ – CalculatorFeline Jan 28 '18 at 21:13
  • \$\begingroup\$ @CalculatorFeline Right, and that would be Laikoni's answer minus 2. I see now. This is definitely hard to convey with text \$\endgroup\$ – H.PWiz Jan 28 '18 at 21:23
  • \$\begingroup\$ @CalculatorFeline Since it doesn't contain the main idea of my submission, I won't post it. I think Laikoni will \$\endgroup\$ – H.PWiz Jan 28 '18 at 21:36
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What are the outputs for each 012 sensor? Also, I only count 6 nodes in your 012 \$\endgroup\$ – H.PWiz Jan 28 '18 at 20:36
  • \$\begingroup\$ 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). \$\endgroup\$ – CalculatorFeline Jan 28 '18 at 21:01
  • 2
    \$\begingroup\$ @CalculatorFeline Got it, maybe rename C to O, since C is in ABCDEF \$\endgroup\$ – H.PWiz Jan 28 '18 at 21:30
  • \$\begingroup\$ Fun fact: This solution is planar. \$\endgroup\$ – CalculatorFeline Jul 23 '18 at 18:00

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.