Jak widzieliśmy w tym pytaniu, złożone wyrażenia logiczne można wyrazić w postaci prostych łączników uogólnionego Saperka. Jednak uogólniony trałowiec nadal ma zwolnienia.

Aby uniknąć tych zwolnień, definiujemy nową grę o nazwie „Uogólniony Saper-1”.

Uogólniony-1 Saper to wersja Saper grana 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 mówi, że dokładnie jedna z sąsiednich komórek jest w (kopalnia). Wskaźniki nie liczą się jako same kopalnie.

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

Twoim celem jest stworzenie 2Saper Generali-1. W Generali-1 Saper zbudujesz strukturę, dzięki której będzie 8 określonych komórek, dla których wszystkie możliwe konfiguracje wartości mają dokładnie dwie komórki. Oznacza to, że zachowuje się dokładnie tak samo, jak 2tradycyjny trałowiec. 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, aby niektóre komórki wartości można było wydedukować ze stanu)

Punktacja

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

42 wierzchołki, 56 krawędzi

Każda zmienna jest wierzchołkiem wartości, a każde pole jest wierzchołkiem wskaźnika z krawędziami do zmiennych wewnątrz. Wejściami są x ₁ , ..., x ₈ . Na przykład, oto rozwiązanie z kopalniami na x ₃ i x ₅ , z kopalniami podświetlonymi na zielono.

Poziome ograniczenia upewnić się, że dokładnie jedna z A „s, a dokładnie jeden z b ” S posiada kopalnię. W tych dwóch kolumnach r nie zawiera kopalni, ale ma to miejsce w pozostałych sześciu kolumnach. (Należy zauważyć, że i b nie mogą oba mają kopalni w tej samej kolumnie). Każde wejście x znajduje się naprzeciwko R w kolumnę, tak dokładnie dwa wejścia mają min zgodnie z zapotrzebowaniem.

Do kdanych wejściowych wykorzystuje 5k+2wierzchołki ( 3kwartość i 2k+2wskaźnik) oraz 7kkrawędzie. Tutaj k=8dane wejściowe dają 42 wierzchołki i 56 krawędzi.

50 wierzchołków, 89 krawędzi

Oparty na bramce logicznej z odpowiedzi H.PWiz.

  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

Każde z nich *jest włączone, gdy dwa odpowiednie wejścia są włączone. Aby obsłużyć przypadek pojedynczego wejścia, używamy wartości pośrednich a=A&!Bitp. Łączenie wszystkich trzech wartości a, ba A&Bwejście drugiego poziomu bramek daje nam skuteczne wejście A|B(to oszczędza wierzchołki !(!A&!B)):

      *              *
      |              |
   #--1--#        #--1--#
   |  |  |        |  |  |
   1--?--1        1--?--1
  |||   |||      |||   |||
  A|B   C|D      E|F   G|H

Te *są włączone, jeśli dwa z nich (odpowiadające czterem wyjściowym wejściom) są włączone, z wyjątkiem par omówionych powyżej. Tymczasem możemy połączyć#*# węzły z ostateczną bramą. Mamy zatem następujące wyniki:

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]

Obejmują one wszystkie 28 przypadków dwóch danych wejściowych. Następnie pozostaje podłączyć ostateczny wskaźnik do tych siedmiu wartości. Jeśli mniej niż dwa wejścia są włączone, żadne z nich nie będzie włączone, więc wskaźnik zgaśnie. Jeśli więcej niż dwa wejścia są włączone, więcej niż jedno z nich będzie włączone, a wskaźnik zgaśnie.

197 wierzchołków, 308 krawędzi

Wymyśliłem tę odpowiedź zeszłej nocy, ale powstrzymałem się od opublikowania jej, ponieważ była to tak wysoka ocena. Ponieważ jednak bije inną odpowiedź tak bardzo , pomyślałem, że powinienem to opublikować.

Korzystam z następującej konfiguracji na wszystkich 28 parach komórek wartości w ABCDEFGH

   ?*
   |
?--1--?
|  |  |
1--?--1
|     |
A     B

?reprezentuje komórkę wartości, której nie ma ABCDEFGH. Tu, gdy ?*jest ON , Ai Bto zarówno na. W przeciwnym razie, Ai Bmoże być w każdej innej konfiguracji.

Łączę wszystkie 28 ?*s do jednej komórki wskaźnikowej. Oznacza to, że tylko jedna para ABCDEFGHbędzie miała dwie WŁĄCZONE . Która jest wystarczająca do wyegzekwowania, że dokładnie dwa z moich komórek wyjściowych będzie ON

354 węzły, 428 krawędzi

Aby udowodnić, że to możliwe. Poprawię to później z pewnym buforowaniem.

(mam nadzieję, że nie ma błędu kodu)

Próbowałem napisać tutaj program Mathematica aby sprawdzić poprawność programu, ale prawdopodobnie nie działa, ponieważ istnieje zbyt wiele zmiennych.

Wynik został wygenerowany przez program komputerowy: Wypróbuj online!

Używam bramy, która wygląda następująco:

               (f)
                |
                |
               (#)
              /   \
             /     \
           (d)     (e)
          /           \
         /             \
       (#) --- (c) --- (#)
     .'                  '.
   .'                      '.
(a)                          (b)

gdzie (#)są 1-wskaźniki, (a)..(f) są wartościami.

Następnie,

c = (not a) and (not b)
d = (not a) and      b
e =      a  and (not b)
f =      a  xnor     b

Także ta brama

(a) ----- (#) ----- (b)

daje

b = not a

. Skorzystaj z tych dwóch rodzajów bram, na których możesz zbudować dowolne wyrażenia.

Oczywiście, ten służy do stwierdzenia, że ​​to (a)musi być prawda:

(a) ----- (#)

81 węzłów, 108 krawędzi

Używając 13 węzłów i 14 krawędzi, tworzymy następującą bramkę Addera (C (arry) = X AND Y, S (um) = X XOR Y):

X - 1 --------------?
   | |
   ? - 1 - S - 1 -? - 1
   | | |
   | C |
T - 1 --------------?

Użyj czterech sumatorów M1, M2, M3, M4, aby dodać odpowiednio A + B, C + D, E + F, G + H, otrzymując odpowiednio przeniesienie C1, C2, C3, C4 i sumę S1, S2, S3, S4

Użyj dwóch sumatorów M5, M6, aby dodać S1 + S2, S3 + S4, otrzymując w ten sposób przeniesienie C5, C6 i sumę S5, S6.

Użyj jednego sumatora M7, aby dodać S5 + S6, aby uzyskać C7 i S7.

Teraz podłącz wszystkie przeniesienia do pojedynczego węzła wskaźnikowego w następujący sposób:

C1- |
C2- |
C3- |
C4 - + - 1
C5- |
C6- |
C7- |

i zmusza S7 (moduł 2 sumy 8 wartości) do 0 przez ten obwód:

S7--1 -? - 1

Argumentuję, że ten obwód wymusza ABCDEFGHna WŁ dokładnie dokładnie dwie wartości , ponieważ może to być tylko liczba parzysta (ponieważ S7 wynosi 0), i nie może być więcej niż 3 wartości ZAŁ (ponieważ tylko jedna z C1-C7 jest WŁĄCZONA).