Вкусное угощение для любителей алгоритмов

Slither link — одна из моих любимых головоломок с ручкой и бумагой. Это тот же жанр, что и судоку, но я предпочитаю его, потому что он имеет более плавную кривую сложности при решении. Вы начинаете с такой сетки чисел:

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

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

В общих чертах алгоритм работает так:

  1. Сгенерируйте форму линии решения.
  2. Подсчитайте количество строк вокруг каждой ячейки и установите ячейку на это число. Эти числа образуют реальную головоломку со скользящими ссылками, но это слишком просто. Нам нужно оставить некоторые ячейки пустыми, чтобы увеличить сложность.
  3. Удаляйте числа один за другим, случайным образом, убедившись, что существует только одно действительное решение головоломки (наша исходная строка). Если удаление номера означает, что существует более одного решения, добавьте его обратно и попробуйте другой номер. Продолжайте делать это, пока у нас не закончатся числа, которые нужно удалить, или остановитесь раньше, чтобы упростить головоломку.

Шаг 3 относительно прост в реализации, а шаг 2 тривиален. Часть, на которой я застрял, — это создание хорошей линии для шага 1. Нам нужна линия, которая извивается вокруг сетки, не пересекаясь сама с собой, и покрывает большую часть сетки. Нам не нужны большие участки пустого пространства.

Недавно я нашел эффективный способ создания этой строки во время приступа бессонницы, связанной с 2020 годом.

Существует вариант головоломки, в котором вместо петли у вас есть вход с одной стороны и выход с другой, и вы должны сформировать единую непрерывную линию, соединяющую их. Вход и выход указаны вместе с номерами, как часть головоломки. Я сосредоточусь на этом варианте, потому что именно этого я хочу в своей игре, но этот алгоритм можно легко адаптировать для создания головоломок на основе циклов.

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

Предыдущие попытки

Сначала я попытался переформулировать «создать волнистую линию» более формально и математически: «Из набора всех возможных линий с одной стороны сетки на другую случайным образом выберите одну линию.

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

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

Другой подход, который я пробовал, — «разделяй и властвуй». Возможно, мы могли бы разделить сетку на 4 квадранта и рекурсивно запустить на них наш алгоритм.

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

Распределение вероятностей общего числа этих точек должно быть тщательно выбрано. Слишком много или слишком мало пересечений, и в последней строке будут видны границы квадрантов. Вероятно, есть способ получить это распределение математически, но для меня он не очевиден. Мы не можем просто случайным образом выбрать X% граничных ребер для рисования линий, потому что не все строки и столбцы имеют одинаковое количество линий.

Более того, мы должны убедиться, что когда все эти точки входа и выхода объединены, они образуют единую непрерывную линию. Таким образом, нам пришлось бы каким-то образом соединить точки входа и выхода в каждом квадранте случайным, но логически выполнимым образом. В целом, подход «разделяй и властвуй» казался слишком громоздким, и я не был уверен, что смогу заставить его работать.

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

Проблема с этим подходом заключается в том, что мы должны быть осторожны, чтобы убедиться, что мы не вносим пересечения при покачивании линии, и следить за тем, чтобы каждая деформация делала ее более волнистой с помощью некоторой эвристики. Наивная реализация каждой из этих проверок потребовала бы O (n) для сетки x на y с ячейками n = x * y. Таким образом, общий алгоритм потребует не менее O(n²), предполагая, что нам нужно в среднем O(n) деформаций, чтобы достичь максимальной волнистости.

Лучший подход

Я какое-то время застрял на этом подходе к деформации, но недавно нашел способ проверить, что конкретная деформация линии увеличивает волнистость и не вызывает пересечения линий за время O(1).

Основная идея проста. Вместо того, чтобы пытаться создать линию от одной стороны к другой, мы думаем об этом как о задаче раскраски ячеек. Цель состоит в том, чтобы разделить сетку на две ортогонально смежные области цвета, а последняя линия является границей этих областей. Наше начальное состояние прямой линии преобразуется в то, что верхняя половина сетки окрашена в один цвет, а нижняя половина — в другой:

После того, как все деформации сделаны, у нас должно получиться что-то вроде этого:

Последняя линия является границей этих областей:

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

Каждая деформация линии — это просто изменение цвета одной из ячеек, прилегающих к границе. Итак, вопрос в том, как нам убедиться, что изменение цвета конкретной ячейки увеличит волнистость границы, не разделяя ни одну из цветных областей?

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

Давайте рассмотрим эти случаи, начиная слева. Если все окружающие ячейки имеют тот же цвет, что и ячейка, изменение ее цвета оставит несвязанный участок цвета. Если 3 одинаковых цвета, а один другой, переворачивание увеличивает волнистость, так что это будет правильный переворот. Если 2 соседние ячейки одного цвета, их переворачивание ничего не меняет. Если только 1 соседняя ячейка одного цвета, ее переворачивание уменьшит волнистость. И справа мы никогда не должны увидеть случай, когда все 4 соседние ячейки имеют цвет, отличный от цвета нашей ячейки-кандидата, потому что это означало бы, что у нас уже есть несвязанный участок цвета.

На самом деле случай с двумя соседними ячейками немного сложнее. Это может изменить волнистость, а может и не изменить, в зависимости от цвета 4 смежных по диагонали ячеек.

Первый случай не должен произойти, а последний вызовет отключенные регионы. Из оставшихся случаев единственный, который увеличивает волнистость, — это случай, когда 3 диагональных ячейки имеют другой цвет, чем ячейка-кандидат. Также бывают случаи, когда недостаточно просто подсчитать количество ячеек одинакового и разного цвета, но все они покрываются проверкой связности региона ниже.

Эти правила не совсем работают на краях сетки, поэтому мы должны немного модифицировать проверку: волнистость увеличивается, если количество одноцветных ортогонально соседних ячеек больше, чем количество разноцветных, или если они одинаковые, но число клеток одного цвета, расположенных по диагонали рядом, больше, чем число клеток разного цвета. Это слишком много, поэтому резюмируем в псевдокоде:

тот же(O) › diff(O) или (тот же(O) == diff(O) и тот же(D) › diff(D))

Где O — набор ортогонально смежных ячеек, а D — диагонально смежных ячеек.

Проверка подключения оказывается довольно простой. Давайте рассмотрим несколько примеров, когда изменение цвета ячейки-кандидата может привести к отключению областей.

У всех этих случаев есть одна общая черта. Обходя 8 соседних ячеек, мы подсчитываем, сколько раз переворачивается цвет. Если общее количество равно 4 или более, то изменение цвета ячейки-кандидата приведет к отключению областей.

Опять же, края сетки немного сложнее. Пусть num(O) будет количеством ортогонально смежных ячеек, тогда проверка связности будет следующей:

переворачивает › 2 * число(O)−4

Собрав все это вместе, мы начинаем с сетки с верхней половиной одного цвета и нижней половиной другого цвета. Мы многократно выбираем случайную ячейку на границе между цветами, сохраняя массив возможных координат и используя всплывающую замену для удаления случайного элемента. Если эта ячейка соответствует вышеупомянутым условиям, мы меняем ее цвет и добавляем ее соседей в массив. Повторяйте, пока массив не станет пустым. В целом этот алгоритм (примерно) O (n), где n — количество ячеек в сетке.

Уточнение результатов

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

Мое предположение, почему это происходит, заключается в том, что начальное состояние, разделенное пополам по горизонтали, означает, что все действительные деформации в начале процесса являются вертикальными, и это искажает результаты.

Самое простое решение — каким-то образом рандомизировать начальные условия. Я попытался инициализировать его синусоидальным рисунком, и это устранило большую часть видимого смещения. Но я хотел по-настоящему рандомизировать его, потому что предвзятость все еще присутствовала, даже если я не мог легко ее увидеть. Я думал придумать вариацию на тему симплексный шум, но заставить его подчиняться правилу связности было бы мучением.

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

Мы можем запустить алгоритм на меньшей сетке, а затем масштабировать его, чтобы получить начальные условия для большей сетки. Делать это рекурсивно до тех пор, пока мы не достигнем минимального размера (я остановился на 4 на 4), по-прежнему будет O(n), потому что геометрический ряд сходится к кратному n.

Результаты выглядят великолепно, и такие сетки 50 на 50 генерируются практически мгновенно. Определенно достаточно быстро для использования в моей игре.

Есть небольшая вариация, с которой я все еще экспериментирую. Вторая половина проверки на извилистость генерирует чрезвычайно стабильные диагональные линии. В отличие от большинства других структур, их нельзя легко испортить дальнейшими деформациями, потому что это правило рассматривает любую деформацию от диагонали как уменьшение волнистости. Таким образом, эти неизменяемые диагонали могут заключать в себе небольшие области, что приводит к пробелам в головоломке. Вы можете увидеть некоторые из них на изображении выше. Они не обязательно являются проблемой, потому что все пробелы очень маленькие, но отключение этой половины проверки избавляет от них:

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

Генерация чисел

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

Почти все числа на краю головоломки либо 0, либо 1, а это не то, чем должна быть головоломка. Что происходит?

Что ж, поскольку самые внешние ячейки цветной сетки имеют один и тот же цвет в верхней и нижней частях, линия, которую генерирует этот алгоритм, никогда не будет касаться края сетки, кроме как на входе и выходе. Таким образом, нам фактически нужно создать сетку на 2 ячейки шире и выше желаемого размера, а затем отбросить контур.

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

Затем мы случайным образом выбираем ячейки (перебирая перетасованный список всех позиций ячеек), удаляем их количество и смотрим, решаема ли головоломка. Таким образом, ключом ко второй фазе алгоритма является написание быстрого решателя скользящих ссылок.

Решатель

Решатель скользящих ссылок по сути такой же, как и решатель судоку, и такого рода вещи являются распространенной проблемой при обучении кодированию. В худшем случае это NP-полная задача. Но решать эти головоломки было бы не очень весело, если бы единственным подходом был грубый перебор всех возможных решений. Забавная головоломка — это та, в которой применение логических правил поможет нам в большей части (если не во всем) пути к решению, а количество необходимой грубой силы будет минимальным.

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

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

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

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

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

В этом случае нас не волнует поиск решения (мы знаем, что это за решение), нас интересует ответ на вопрос «есть ли у этой головоломки ровно одно решение?». Так что нам просто нужно вести подсчет, сколько решений мы находим, и мы можем остановить поиск раньше, если найдем более одного. Алгоритм подсчета решений выглядит так:

  1. Повторно применяйте все жестко запрограммированные логические правила, пока они не перестанут работать.
  2. Проверьте, решена ли головоломка, не завершена ли она, но все еще в порядке, или она нарушает правила (например, слишком много строк вокруг числа или ответвлений в строке).
  3. Если головоломка решена или нарушает правила, отмените все изменения, сделанные на шаге 1, затем верните 1, если она решена, иначе верните 0.
  4. В противном случае найдите первое ребро, которое не заполнено или не пересечено, и заполните его. Также пусть n = 0 (эта переменная считает количество решений).
  5. Рекурсивно вызовите этот алгоритм и добавьте его результат к n.
  6. Отмените изменение с шага 4.
  7. Если n > 1, переходим к шагу 9, так как нас не интересует, сколько именно существует решений, важно, больше ли их 1.
  8. Попробуйте установить тот же край в крест, затем повторите шаги 5–7 еще раз.
  9. Отменить все изменения, сделанные всем алгоритмом.
  10. Вернуть н.

Этот алгоритм немного сложен для реализации. Эффективная обработка отмен требует сохранения стека всех модификаций, внесенных в головоломку. Логические правила должны отправлять свои изменения в стек и возвращать общее количество сделанных изменений, чтобы мы могли извлечь и отменить правильное количество.

Ускорение

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

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

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

Еще раз взглянув на верхний уровень алгоритма, который удаляет числа из сетки, мы можем применить здесь аналогичный подход отказа. Каждый раз, когда удаление числа приводит к тому, что головоломка имеет несколько решений, мы увеличиваем значение счетчика. Когда этот счетчик достигает предела, мы сдаемся и возвращаем готовую головоломку. Этот предел необходимо настроить в зависимости от размера головоломки. В настоящее время я установил его на x * y / 10.

Есть еще более мощная техника, которую можно применить во время удаления номера. Как правило, первые 20–40% удалений будут успешными. Таким образом, для сетки со 100 ячейками мы можем вслепую удалить 20 случайных номеров ячеек и проверить, есть ли у головоломки только одно решение. Если это так, мы пытаемся удалить еще 20 чисел, иначе мы добавим обратно 10. Мы можем применить двоичный поиск к этой проблеме.

Используя наш перетасованный список позиций ячеек, мы выбираем его среднюю точку и перебираем все позиции до этой средней точки, очищая соответствующие ячейки. Если полученная головоломка имеет более одного решения, мы устанавливаем верхнюю границу нашего поиска в среднюю точку, в противном случае мы устанавливаем нижнюю границу в эту точку. Промойте и повторите, пока границы не сойдутся. Чтобы реализовать это эффективно, мы должны очищать и заполнять только те ячейки, которые необходимо изменять на каждой итерации, а не каждый раз полностью сбрасывать сетку. Этот бинарный поиск того стоит. Удаление первых 30% сетки 30 на 30 наивно потребовало бы запуска решателя 270 раз, но с бинарным поиском нам нужно запустить его только 10 раз.

Окончательные результаты

Используя последнюю версию алгоритма, головоломку 10 на 10 можно сгенерировать примерно за 10–30 секунд, 20 на 20 — примерно за 3–5 минут, а 30 на 30 — примерно за 10–20 минут. Все это достаточно хорошо для моей игры, потому что, пока игрок решает одну головоломку, я могу сгенерировать следующую в фоновом режиме. Тем не менее, я буду продолжать пытаться сделать это быстрее, потому что внедрение большего количества правил — это действительно забавное упражнение, которое значительно влияет на время генерации. Чем быстрее работает решатель, тем сложнее я могу решать головоломки.