Кол (игра)

Col — это игра с карандашом и бумагой , а именно игра в раскрашивание карты , включающая закрашивание областей на линейном рисунке в соответствии с правилами раскрашивания графа . С каждым ходом граф должен оставаться правильным (никакие две области одного цвета не могут соприкасаться), а игрок, который не может сделать допустимый ход, проигрывает. Игра была описана и проанализирована Джоном Конвеем , который приписал ее Колину Воуту, в книге «О числах и играх» . ^[1]

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

Начальный график:

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

После первого хода:

Второй игрок теперь закрашивает белую клетку. Поскольку сейчас нет областей синего цвета, допускается любая белая клетка.

Два хода:

В этот момент вступает в силу требование правильности графика, поскольку необходимо создать красную область, не касающуюся существующей:

После того, как третья область окрашена:

Обратите внимание, что области считаются соприкасающимися только в том случае, если они имеют общие ребра, а не только вершины, поэтому этот ход допустим.

Игра продолжается, игроки ходят поочередно, пока один из игроков не сможет сделать ход. Этот игрок проигрывает. Возможное продолжение игры следующее (каждый ход пронумерован для ясности):

Игра закончена:

В этом случае игрок синего цвета проиграл.

Snort, изобретенный Саймоном П. Нортоном , использует похожее партизанское назначение двух цветов, но с антиклассическим ограничением: соседним регионам не разрешается назначать разные цвета. Раскрашивание регионов объясняется как назначение полей быкам и коровам, где соседние поля не могут содержать скот противоположного пола, чтобы они не отвлекались от выпаса.

Принятие решения о результате в Snort является PSPACE-полным на общих графах. ^[2] Это доказывается путем сведения партизанского узла Kayles , который является PSPACE-полным, к игре Snort.

Значение позиции Col всегда представляет собой либо число, либо число плюс звездочка ^[3]. Это делает игру относительно простой по сравнению со Snort, в которой представлено гораздо большее разнообразие значений.

• Берлекамп, Элвин Р .; Джон Х. Конвей; Ричард К. Гай (1982). Выигрышные пути для ваших математических пьес . Academic Press. ISBN 978-0-12-091101-1.Переработано и переиздано как
• Берлекэмп, Элвин Р. (2004) [2001]. Выигрышные пути для ваших математических игр (2-е изд.). AK Peters Ltd. ISBN 978-1-56881-130-7.
• Конвей, Джон Хортон (1976). О числах и играх . Academic Press. ISBN 978-0-12-186350-0.Переработано и переиздано как
• Конвей, Джон Хортон (2000). О числах и играх . AK Peters Ltd. ISBN 978-1-56881-127-7.

• [1] Игры Col и Snort на Google Play