Hexcells to gra oparta off Saper grał na sześciokątów. (Pełne ujawnienie: Nie mam nic wspólnego z Hexcells. W rzeczywistości nie lubię gry.) Większość zasad Hexcells można dość łatwo wyrazić w Uogólnionym Saperu (Saper gra na dowolnym wykresie). Ten, który jest najtrudniejszy, to {X}i -X-rządzi.

{X}Reguła mówi, że komórka graniczy Xkopalnie i że wszystkie te kopalnie graniczą ze sobą w ciągłej drodze. Na przykład, gdybyśmy mieli zarząd:

  ?   ?

?  {3}  ?

  ?   ?

Byłoby 6 możliwości umieszczenia min

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

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

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

Twoim celem jest wdrożenie reguły {3}w uogólnionym Saperu.

Specyfika

Uogólniony Saper to Saper rozgrywany na dowolnym wykresie. Wykres ma dwa typy wierzchołków, „wskaźnik” lub „wartość”. Wartość może być włączona lub wyłączona (kopalnia lub niewypał), jednak jej stan jest nieznany graczowi. Wskaźnik informuje gracza o liczbie sąsiadujących wierzchołków (min) i nie liczy się jako sama kopalnia.

Na przykład poniższa tablica dla Uogólnionego Sapera mówi nam, że komórki A i B są albo kopalniami, albo żadna z nich nie jest kopalniami.

(Na schemacie wskaźniki są zaznaczone na szaro, a wartości są białe)

W przeciwieństwie do zwykłego trałowca, w którym klikane są wartości, które są wyłączone, aby odsłonić wskaźniki, nie ma takiej mechaniki w Uogólnionym Saperu. Gracz po prostu określa, które stany wykresu mogą spełnić jego wskaźnik.

Twoim celem jest zbudowanie struktury w Uogólnionym Saperach, tak aby istniało 6 określonych komórek, które mogą mieć tylko te stany, które spełniają się tak, jakby były połączone z regułą Hexcells {3}. Kiedy piszesz swoje rozwiązanie, nie powinieneś mieć na uwadze konkretnych wartości dla komórek wartości. (W odpowiedzi na pytanie H.PWiza dozwolone jest, że niektóre komórki wartości można oddzielić od stanu, ale zawsze możesz poprawić swój wynik, usuwając takie komórki)

Punktacja

Twoje odpowiedzi zostaną ocenione na podstawie liczby wierzchołków na końcowym wykresie pomniejszonej o 6 (dla 6 danych wejściowych), przy czym niższy wynik będzie lepszy. Jeżeli dwie odpowiedzi wiążą się w tej metryki, przerywnikiem będzie liczba krawędzi.

Rozwiązalność

Ten problem można rozwiązać, mam rozwiązanie tego problemu i opublikuję go, gdy wyzwanie pojawi się za tydzień.

7 5 wierzchołków, 14 10 krawędzi

^{(Wykres wykonany za pomocą tego narzędzia online i farby.)}

A- Fsą naszymi sześcioma węzłami i Jsą węzłem pomocniczym. Trzy 1-nodes egzekwować że węzły przeciwne są różne, natomiast 2-node zapewnia, że A, Ca Emoże nie być wszystkie kopalnie, ani puste.

Edycja: -2 wierzchołki dzięki CalculatorFeline i H.PWiz!

9 wierzchołków, 17 krawędzi

Gdzie ? to komórka wartości, która nie należy do tych 6, na których nam zależy, potrzebujemy następującego podrozdziału.

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

^{Moje umiejętności ASCII-art są straszne.}

Z tych 6 wierzchołki skonfigurować: ABCmoże mieć następujące stany: 111, 110, 011, 000, 100,001

Z komórek odpowiadających następującym sześciokąta, wszystko nam wtedy potrzebne są 3 kolejne komórki wskaźnikowe A-1-D, B-1-E,C-1-F

  B  C
A      D
  F  E

44 wierzchołki, 66 krawędzi

Najpierw zaczynamy od pierścienia z 6 komórkami wartości, połączonymi z 3. Komórki te będą komórkami z {3}regułą.

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

Następnie podłączamy czujniki 012 do par komórek wartości (AB, BC, CD, DE, EF, FA). Struktura czujnika 012 znajduje się poniżej.

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

A i B to wejścia do czujnika, a O to wyjście. The? komórki są komórkami wartości ogólnej. O będzie kopalnią, jeśli dokładnie jeden z A i B jest kopalnią, a inaczej pustą. Następnie podłączamy 2 węzeł do wszystkich wyjść czujników. Zapewnia to, że są dokładnie 2 pary z dokładnie 1 kopalnią, i można udowodnić, że jedyne konfiguracje, które to spełniają, są tymi, które spełniają {3}. Każdy czujnik zajmuje 7 węzłów, więc 6 czujników wymaga 42. Dodaj 3 węzeł podłączony do ABCDEF i 2 węzeł podłączony do wyjść, a otrzymasz 44.

To rozwiązanie można również dostosować do {1}- {5}zmieniając 3 węzeł na inną wartość.