Hexcells это игра , основанная прочь Сапер играл на шестиугольники. (Полное раскрытие: я не имею ничего общего с Hexcells. На самом деле игра мне не очень нравится.) Большинство правил Hexcells можно довольно легко выразить в Generalized Minesweeper (Minesweeper, играемый на произвольном графе). Один , который является наиболее сложным является {X}и -X-правила.

{X}Правило говорит нам , что клетка граничит Xмины и что все эти мины граничат друг с другом в непрерывном пути. Например, если у нас была доска:

  ?   ?

?  {3}  ?

  ?   ?

6 возможностей для размещения шахты будут

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

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

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

Ваша цель состоит в том, чтобы реализовать правило {3}в обобщенном тральщике.

конкретика

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

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

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

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

Ваша цель состоит в том, чтобы построить структуру в Generalized Minesweeper, чтобы в ней было 6 определенных ячеек, которые могут иметь только состояния, которые выполняются так, как если бы они были связаны с правилом Hexcells {3}. Когда вы пишете свое решение, вы не должны иметь в виду конкретные значения для ячеек значений. (В ответ на вопрос H.PWiz допускается, что некоторые ячейки значений могут быть выведены из состояния, но вы всегда можете улучшить свой счет, удалив такие ячейки)

счет

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

Разрешимость

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

7 5 вершин, 14 10 ребер

^{(График сделан с помощью этого онлайн-инструмента и краски.)}

A- Fэто наши шесть узлов, и Jэто вспомогательный узел. Три 1-nodes исполнения , что противоположные узлы различны, в то время как 2-node убеждается , что A, Cи Eне может быть ни все мины, ни пусты.

Изменить: -2 вершины благодаря CalculatorFeline и H.PWiz!

9 вершин, 17 ребер

Где ? является ячейкой значения, которая не относится к числу тех, которые 6нас интересуют, нам нужен следующий подграф.

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

^{Мои навыки ASCII-искусства ужасны.}

С тех 6 вершин настройки: ABCможет иметь следующие состояния: 111, 110, 011, 000, 100,001

С клетками соответствующих следующему шестиугольника, все мы тогда нужно еще 3 индикаторных клеток A-1-D, B-1-E,C-1-F

  B  C
A      D
  F  E

44 вершины, 66 ребер

Сначала мы начнем с кольца из 6 ячеек значений, которые все связаны с 3. Эти ячейки будут ячейками с {3}правилом.

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

Затем мы присоединяем датчики 012 к парам ячеек значений (AB, BC, CD, DE, EF, FA). Структура датчика 012 ниже.

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

A и B являются входами для датчика, а O является выходом. ? ячейки являются ячейками общего значения. O будет моим, если точно один из A и B будет моим и пустым в противном случае. Затем мы подключаем 2 узла ко всем выходам датчика. Это гарантирует, что есть ровно 2 пары с ровно одной шахтой, и можно доказать, что единственными конфигурациями, которые удовлетворяют этому, являются те, которые удовлетворяют {3}. Каждый датчик занимает 7 узлов, поэтому для 6 датчиков требуется 42. Добавьте 3 узла, подключенных к ABCDEF, и 2 узла, подключенных к выходам, и вы получите 44.

Это решение также может быть адаптировано для {1}- {5}путем изменения 3 узла к некоторому другому значению.