Hexcellent Minesweeping

13

Hexcells ist ein Spiel von Minesweeper, das auf Sechsecken gespielt wird. (Vollständige Offenlegung: Ich habe nichts mit Hexcells zu tun. Tatsächlich mag ich das Spiel nicht wirklich.) Die meisten Hexcells-Regeln können ziemlich einfach in Generalized Minesweeper (Minesweeper, gespielt auf einem beliebigen Graphen) ausgedrückt werden. Das Schwierigste ist das {X}und die -X-Regeln.

Die {X}Regel besagt, dass eine Zelle an XMinen grenzt und dass alle diese Minen in einem kontinuierlichen Pfad aneinander grenzen. Wenn wir zum Beispiel das Board hätten:

  ?   ?

?  {3}  ?

  ?   ?

Die 6 Möglichkeiten für die Minenplatzierung wären

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

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

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

Ihr Ziel ist es, die Regel {3}in generalisierten Minesweeper zu implementieren .

Besonderheiten

Generalized Minesweeper ist Minesweeper, das auf einem beliebigen Graphen gespielt wird. Der Graph hat zwei Arten von Eckpunkten, einen "Indikator" oder einen "Wert". Ein Wert kann entweder ein oder aus sein (eine Mine oder ein Blindgänger), sein Status ist dem Spieler jedoch unbekannt. Ein Indikator teilt dem Spieler mit, wie viele benachbarte Scheitelpunkte sich auf (Minen) befinden und zählt nicht als Mine.

Das folgende Board für Generalized Minesweeper zeigt uns beispielsweise, dass die Zellen A und B entweder beide Minen sind oder keine von ihnen Minen sind.

Einfaches Spiel

(In der Grafik sind die Anzeigen grau markiert, während die Werte weiß sind.)

Anders als bei normalen Minensuchbooten, bei denen Sie auf Werte klicken, die deaktiviert sind, um Indikatoren anzuzeigen, gibt es bei Generalized Minesweeper keine solche Mechanik. Ein Spieler bestimmt einfach, für welche Zustände der Graph seinen Indikator erfüllen kann.

Ihr Ziel ist es, in Generalized Minesweeper eine Struktur zu erstellen, bei der es 6 bestimmte Zellen gibt, die nur Zustände haben können, die sich erfüllen, als wären sie mit der Hexcells-Regel verbunden {3}. Wenn Sie Ihre Lösung schreiben, sollten Sie keine spezifischen Werte für Wertezellen berücksichtigen. (In Beantwortung der Frage von H.PWiz ist es zulässig, dass einige Wertzellen aus dem Status ableitbar sind. Sie können jedoch jederzeit Ihre Punktzahl verbessern, indem Sie solche Zellen entfernen.)

Wertung

Ihre Antworten werden anhand der Anzahl der Eckpunkte im endgültigen Diagramm minus 6 (für die 6 Eingaben) bewertet, wobei eine niedrigere Punktzahl besser ist. Wenn zwei Antworten mit dieser Metrik übereinstimmen, ist der Gleichstand die Anzahl der Kanten.

Lösbarkeit

Dieses Problem ist lösbar. Ich habe eine Lösung für dieses Problem und werde sie veröffentlichen, sobald diese Herausforderung eine Woche alt ist.

Post Rock Garf Hunter
quelle
Müssen also immer 6 Kanten zwischen den 6 Eingangsscheitelpunkten sein?
Bergi
@Bergi Kanten zwischen Wertzellen sind redundant, da sie keine Bedeutung haben
H.PWiz
@ H.PWiz Aber die " {3}Regel" besagt " alle diese Minen grenzen in einem durchgehenden Pfad aneinander " - ohne Kanten gibt es keinen Pfad.
Bergi
@Bergi aber die Aufgabe ist es, ein Diagramm so zu erstellen, dass es 6 Zellen sind, die sich so verhalten , " als ob sie mit der Hexcells-Regel verbunden wären {3}". Sie müssen nicht verbunden sein
H.PWiz
1
@Pavel Generalized Minesweeper ist für mich eine Programmiersprache. Es mag sehr esoterisch sein, aber ich denke nicht, dass es zu weit vom Proof-Golf entfernt ist .
Post Rock Garf Hunter

Antworten:

15

7 5 Ecken, 14 10 Kanten

(Grafik erstellt mit diesem Online-Tool und malen.)

A- FSind unsere sechs Knoten, und Jist ein Hilfsknoten. Die drei 1-nodes erzwingen , die entgegengesetzte Knoten verschieden sind, während die 2-node stellt sicher , dass A, Cund Ekönnen weder alle Minen, noch alle leer.

Edit: -2 Vertices dank CalculatorFeline und H.PWiz!

Laikoni
quelle
1
Sie können 2 Scheitelpunkte entfernen.
CalculatorFeline
Beachten Sie, dass die 2-J-Struktur auch sicherstellt, dass ACE nicht alle leer sind.
CalculatorFeline
3

9 Eckpunkte, 17 Kanten

Wo ? Ist eine Wertezelle, die 6uns nicht interessiert, brauchen wir den folgenden Untergraphen.

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

Meine ASCII-Kunstfähigkeiten sind schrecklich.

Mit diesen 6 Ecken eingerichtet: ABCkann folgende Zustände haben: 111, 110, 011, 000, 100,001

Mit den Zellen der folgenden Sechseck entspricht, alles , was wir dann brauchen , sind 3 weitere Indikatorzellen A-1-D, B-1-E,C-1-F

  B  C
A      D
  F  E
H.PWiz
quelle
Es wäre viel kleiner, wenn Sie A,C,Estattdessen überprüfen A,B,C.
CalculatorFeline
@ CalculatorFeline Ich kann nicht verstehen, warum ...
H.PWiz
Wenn Sie das ABC-Prüfgerät aus Ihrer Lösung entfernen, funktioniert es fast, außer dass es auch ACEund zulässt BDF. In diesen Fällen ACEist die Anzahl der Minen entweder 0 oder 3, in einer gültigen Lösung jedoch 1 oder 2. Dies ermöglicht Ihnen eine Punktzahl von 5.
CalculatorFeline
@CalculatorFeline Richtig, und das wäre Laikonis Antwort minus 2. Ich verstehe jetzt. Dies ist definitiv schwer mit Text zu vermitteln
H.PWiz
@CalculatorFeline Da es nicht die Hauptidee meines Beitrags enthält, werde ich ihn nicht veröffentlichen. Ich denke, Laikoni wird
H.PWiz
3

44 Ecken, 66 Kanten

Zunächst beginnen wir mit einem Ring von 6 Wertzellen, die alle mit einer 3 verbunden sind. Diese Zellen sind die Zellen mit der {3}Regel.

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

Anschließend werden 012-Sensoren an die Wertzellenpaare (AB, BC, CD, DE, EF, FA) angeschlossen. Der Aufbau des 012-Sensors ist im Folgenden dargestellt.

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

A und B sind die Eingänge zum Sensor und O ist der Ausgang. Das ? Zellen sind Zellen mit generischem Wert. O wird eine Mine sein, wenn genau A und B eine Mine sind und ansonsten leer. Dann verbinden wir einen 2-Knoten mit allen Sensorausgängen. Dies stellt sicher, dass es genau 2 Paare mit genau 1 Mine gibt, und es kann bewiesen werden, dass die einzigen Konfigurationen, die dies erfüllen, diejenigen sind, die dies erfüllen {3}. Jeder Sensor benötigt 7 Knoten, also benötigen 6 Sensoren 42. Addieren Sie die 3 Knoten, die mit ABCDEF verbunden sind, und die 2 Knoten, die mit den Ausgängen verbunden sind, und Sie erhalten 44.

Diese Lösung kann auch angepasst werden , {1}- {5}durch den 3 Knoten auf einen anderen Wert zu ändern.

CalculatorFeline
quelle
Was sind die Ausgänge für jeden 012Sensor? Außerdem zähle ich nur 6 Knoten in Ihrem012
H.PWiz
Es gibt die 2 Knoten, die 2 1 Knoten, die 3? Knoten und C (der nicht einer der ABCDEF-Knoten ist, nur die Ausgabe des Sensors).
CalculatorFeline
2
@CalculatorFeline Verstanden, vielleicht umbenennen Cin O, da C ist inABCDEF
H.PWiz
Unterhaltsame Tatsache: Diese Lösung ist planar.
CalculatorFeline