Как мы видели в этом вопросе, сложные логические утверждения можно выразить в терминах простых связок обобщенного тральщика. Однако генерализованный тральщик по-прежнему имеет избыточность.

Чтобы избежать этих избыточностей, мы определяем новую игру под названием «Сапер Обобщенный-1».

Generalized-1 Minesweeper - это версия Minesweeper, играемая на произвольном графике. Граф имеет два типа вершин: «индикатор» или «значение». Значение может быть включено или выключено (мина или сбой), однако его состояние неизвестно игроку. Индикатор говорит, что ровно одна из соседних ячеек включена (мина). Индикаторы не считаются самими минами.

Например, следующая доска для Generalized Minesweeper говорит нам, что ячейки A и B являются либо минами, либо ни одна из них не является минами.

(На диаграмме индикаторы отмечены серым цветом, а значения - белым)

В отличие от обычного тральщика, где вы щелкаете значения, которые отключены, чтобы отобразить индикаторы, в Generalized Minesweeper нет такой механики. Игрок просто определяет, для каких состояний графика могут удовлетворять его показатели.

Ваша цель состоит в том, чтобы сделать 2в Generalized-1 Minesweeper. В Generalized-1 Minesweeper вы построите такую ​​структуру, чтобы в ней было 8 определенных ячеек, для которых во всех возможных конфигурациях значений есть ровно две ячейки. Это означает, что он ведет себя точно так же, как 2в традиционном тральщике. Когда вы пишете свое решение, вы не должны иметь в виду конкретные значения для ячеек значений. (В ответ на вопрос Х.П. Виза допускается, что некоторые ячейки значений могут быть выведены из состояния)

счет

Ваши ответы будут оцениваться по количеству вершин в итоговом графе минус 8 (для 8 входных данных), причем более низкий балл будет лучше. Если два ответа связаны в этой метрике, прерыватель связи будет числом ребер.

42 вершины, 56 ребер

Каждая переменная является вершиной значения, а каждое поле является вершиной индикатора с ребрами для переменных внутри нее. Входы: х ₁ , ..., х ₈ . Например, вот решение с минами в х ₃ и х ₅ , с минами, выделенными зеленым цветом.

Горизонтальные ограничения гарантируют, что у одного из a и точно одного из b есть мина. В этих двух столбцах r не содержит мины, но в остальных шести столбцах. (Обратите внимание, что a и b не могут иметь мины в одном и том же столбце.) Каждый вход x находится напротив r в своем столбце, поэтому ровно два входа имеют мины по желанию.

Для kвходных данных используются 5k+2вершины ( 3kзначение и 2k+2индикатор) и 7kребра. Здесь k=8входные данные дают 42 вершины и 56 ребер.

50 вершин, 89 ребер

На основании логических ворот из ответа Х.П.

  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

Каждый из *них включен, когда включены два соответствующих входа. Для того, чтобы обработать случай единого входа, мы используем промежуточные значения и a=A&!Bт.д. соединяющее все три значения a, bа A&Bна вход вторичного уровня ворота дают нам эффективный вход A|B(это экономит вершину более !(!A&!B)):

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

Они *включаются, если включены два из их входов (соответствующих четырем из исходных входов), за исключением случаев, описанных выше. Между тем, мы можем подключить #*#узлы к последним воротам. Поэтому мы имеем следующие результаты:

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]

Они охватывают все 28 случаев двух входов. Затем остается подключить окончательный индикатор к этим семи значениям. Если включено менее двух входов, то ни один из них не будет включен, поэтому индикатор будет выключен. Если включено более двух входов, то будет включено более одного из них, и индикатор погаснет.

197 вершин, 308 ребер

Я пришел с этим ответом вчера вечером, но отказался опубликовать его, потому что это был такой высокий балл. Однако, поскольку он намного превосходит другой ответ , я должен опубликовать его.

Я использую следующую настройку на все 28 пар значений клеток в ABCDEFGH

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

?представляет ячейку значения не в ABCDEFGH. Здесь, когда ?*это ПО , Aи Bоба на. Иначе Aи Bможет быть в любой другой конфигурации.

Я подключаю все 28 ?*секунд к одной индикаторной ячейке. Это означает, что только у одной пары ABCDEFGHбудет два ON . Который является достаточным для обеспечения , что ровно два моих выходных ячеек будет ON

354 узла, 428 ребер

Просто чтобы доказать, что это возможно. Я улучшу это позже с некоторым кэшированием.

(надеюсь, нет ошибки кода)

Я пытался написать программу Mathematica здесь , чтобы проверить программу действительности, но она не работает , вероятно , потому что есть слишком много переменных.

Результат был сгенерирован компьютерной программой: Попробуйте онлайн!

Я использую ворота, которые выглядят так:

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

где (#)1-показатели, (a).. (f)значения.

Потом,

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

Также эти ворота

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

дает

b = not a

, Используйте эти два типа ворот, которые вы можете создавать любые выражения.

Конечно, это для того, чтобы утверждать, что это (a)должно быть правдой:

(a) ----- (#)

81 узел, 108 ребер

Используя 13 узлов и 14 ребер, мы создаем следующие ворота Adder (C (arry) = X AND Y, S (um) = X XOR Y):

X - 1 --------------?
   | |
   ? - 1 - S - 1 - - 1
   | | |
   | C |
Y - 1 --------------?

Используйте четыре сумматора M1, M2, M3, M4, чтобы добавить A + B, C + D, E + F, G + H, соответственно, с результирующим переносом C1, C2, C3, C4 и суммой S1, S2, S3, S4.

Используйте два сумматора M5, M6, чтобы добавить S1 + S2, S3 + S4, с результирующим переносом C5, C6 и суммой S5, S6.

Используйте один сумматор M7, чтобы добавить S5 + S6, чтобы получить C7 и S7.

Теперь подключите все переносы к одному узлу индикатора, как показано ниже:

C1- |
С2- |
C3- |
С4 - + - 1
С5- |
С6- |
С7 |

и заставить S7 (по модулю 2 суммы из 8 значений) быть 0 этой схемой:

S7--1 - - 1

Я утверждаю, что эта схема принудительно ABCDEFGHприводит к включению ровно двух значений , поскольку это может быть только четное число (поскольку S7 равно 0), и не может быть больше 3 значений ВКЛ (поскольку включено только одно из C1-C7).