Эта и следующие статьи рекомендуются к прочтению после ознакомления с, непосредственно, "Сапером" - так Вам будет проще понимать вещи, которых здесь будет вестись речь. Помимого этого пригодится минимальное знание теории множеств и понимание записи математических утверждений. Приятного прочтения.
Введение
"Сапер" - занимательная головоломка, которая, несмотря на простоту правил, предлагает игроку уйму нетривиальных испытаний. Решения досок подразумевает постоянное прикидывания расположения мин в клетках, их подсчет, перебор разных вариантов закрытия конкретных ситуаций - в течении времени часть этих расчетов начинает делаться автоматически, поскольку человек способен запоминать и воспроизводить решения всяческих шаблонов. Так, например, существуют всем известные и не очень "паттерны" - комбинации клеток, заранее подготовленные решения которых можно использовать в сочетании с другими ситуациями на игровом поле.
Но у паттернов, а точнее у того, как их преподносят, есть существенные минусы. Человек, изучая их на конкретных примерах, неосознанно сужает возможности, которые эти паттерны дают, и их применения. Вот, например, очень наглядный пример. Перед Вами небольшой кусочек абстрактного поля:
Человек, который хотя бы немного знакомый с паттернами, машинально покажет, куда ставить мины:
И он окажется прав. Дело в другом: зачастую новые игроки совсем не придают значения доказательство данного факта, а если и придают, то понимают его только в конкретных, как эта, ситуациях. И вот я даю такое же "1-2-1":
И почти всегда человек здесь лишь недоумевает. Он не привык видеть "1-2-1" в подобном виде, и сразу теряется, думает, что тут уже никак не решить, или что еще хуже, просто повторяет решение прошлой ситуации.
А ведь всего три эти клетки уже позволяют открыть целых восемь! Ведь даже у такого, казалось бы, слишком общего паттерна, есть изящное решение - его я пока сохраню в тайне, ради интриги.
Но иногда человек не виноват в поверхностном понимании темы, ведь бывают действительно сложные поля, например как это:
Удивительно, но люди часто воспринимают это как нерешаемое логически поле, просто не увидев здесь какой-нибудь очевидной закономерности, а ведь и здесь можно с уверенностью открыть несколько клеток (это мы тоже отложим на потом). А если человек и находит это решение, то делает это долгим и муторным перебором вариантов. И ладно, такой метод тоже имеет право на существование, но обобщи задачу на произвольный N...
... то сдувается и такой надежный подход как перебор. Нет, конечно, можно кроме расположений мин перебирать и значения N, но это уже совсем ни в какие ворота. Очевидно, если и решать подобного рода общие задачи, то каким-нибудь более точным, быстрым, компактным и общим алгоритмом.
Итак, мы пришли к почти очевидной необходимости в некотором мощном инструменте для работы с подобного рода задачами. Я бы мог сразу начать расписывать принцип работы данной системы, но тогда бы было бы сложно прочувствовать нужность этого всего. Теперь же, когда мы убедились в этом на вышеприведенных примерах, можно приступать к следующему разделу, где мы зададим математический фундамент этого самого "инструмента".
Система аксиом математической модели "Сапера"
У нас появилась нужда в математической модели. Следующий шаг - с помощью системы аксиом задать поведение, аналогичное тому, как работает игра. Внимание: на данном шаге мы не задумываемся об удобстве записи или применения данной модели - все это впереди.
Дальнейшие действия такие: я буду расписывать "человеческим" языком правила, затем записывать их в математических терминах, попутно вводя нужные нам объекты и понятия, давая к ним такие же "человеческие" комментарии для лучшего понимания. Поехали.
На N-мерном пространстве введем декартову систему координат точками в целочисленных координатах. Точки далее будем называть клетками.
Каждая клетка находится в одном из двух состояний: либо она пустая, либо является миной. Состояние клетки будем называть ее типом и обозначаться это будет так:
При этом любая пустая клетка имеет свою особенную численную характеристику - номинал:
И, наконец, самое главное: для данной системы справедливо утверждение:
Для каждой пустой клетки количество клеток-мин вокруг нее равно ее номиналу.
Под "вокруг клетки" подразумевается Мура некоторого порядка ω (см. https://ru.wikipedia.org/wiki/Окрестность_Мура).
Формально вышеописанное записывается вот так:
.... и все! Подобную систему аксиом, а так же любые следствия и задачи в ней будем называть "N-мерный "Сапер" порядка ω" или кратко 𝓜(N, ω).
Всеми известный и любимый "Сапер" на Windows и порты на другие системы - это не что иное, как 𝓜(2, 1) (а.к.а. "Двумерный "Сапер" порядка 1").
Часть 1 - итоги
Итак, мы сформировали формальную систему аксиом, описывающую обобщенную версию "Сапера", которая включает собственно оригинальные правила. Теперь, имея на руках постулаты и базовые функции с начальной терминологией, можно будет переходить к выводу теорем, которыми мы будем пользоваться при решении всяческих задач в "Minesweeper" - однако все это, пока что, впереди.
Дело в том, что прежде чем бросаться с головой в решение задач, нужно в полной мере сформулировать понятия, чтобы не было никаких недосказанностей или разночтений. В общем, встретимся в следующей статье.
Спасибо за прочтение.
Ниже повторно привожу аксиомы, задающие математическую модель "Сапер":