Ответ 1

Сокращение до SAT

Основная идея

• Уменьшите проблему до SAT
• Для решения проблемы используйте современный SAT-решение.
• Profit

Сложность

Проблема, очевидно, в NP: если вы догадываетесь о созвездии платы, то легко (поли-время) проверять, разрешает ли она проблему.

Является ли это NP-hard (что так сложно, как любая другая проблема в NP, например SAT), не ясна. Конечно, современные SAT-решатели все равно будут волноваться и решать большие случаи на ветру (думаю, до 100x100).

Литература по числовой ссылке

Здесь я просто копирую комментарий Nuclearman к OP:

Поиск "формулировки SAT номерной линии" и "NP-полнота номерной линии" приводит к двум ссылкам. Неудивительно, что два самых интересных из них на японском языке. первый - это фактическое доказательство NP-полноты. второй описывает, как решить NumberLink с помощью SAT-решения Sugar. -

Подсказка для восстановления до SAT

Существует несколько возможностей для кодирования проблемы. Я дам тот, который я мог бы сделать быстро.

Примечание

j_random_hacker отметил, что автономные циклы не допускаются. Следующая кодировка позволяет им. Эта проблема делает кодирование SAT немного менее привлекательным. Простейший метод, который я мог бы описать, чтобы запретить свободно стоящие циклы, ввел бы новые переменные O (n ^ 2), где n - количество плиток на доске (количество отсчетов от следующего приемника для каждой плитки), если только не используется журнал кодирование для этого, что привело бы его к O(n*log n), что может затруднить задачу для решателя.

Переменные

Одна переменная для каждой плитки, типа и цвета. Пример, если какая-либо переменная X-Y-T-C истинна, она кодирует, что плитка в позиции X/Y имеет тип T и имеет цвет C. Вам не нужен пустой тип плитки, поскольку это невозможно в решении.

Установить начальные переменные

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

Ограничения

• Для каждой позиции точно одна комбинация цвета/куска верна (ограничение мощности).
• Для каждой переменной (позиция, тип, цвет) четыре соседних плитки должны быть совместимы (если цвет соответствует).

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

Ответ 2

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

• Для каждого пустого квадрата сформируйте набор возможных цветов для этого квадрата, а затем многократно выполняйте логические выводы на каждом квадрате, чтобы уменьшить разрешенный набор цветов для этого квадрата.
• Всякий раз, когда квадрат набора возможных цветов уменьшается до размера 1, определяется цвет для этого квадрата.
• Если мы достигнем состояния, в котором более логичные выводы не могут быть выполнены, и головоломка еще не полностью решена (т.е. есть хотя бы один квадрат с более чем одним возможным цветом), выберите один из этих нерешенных квадратов и запишите на него, пробуя каждый из возможных цветов по очереди. Каждая попытка либо приведет к решению, либо противоречию; последний устраняет этот цвет как возможность для этого квадрата.

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

[РЕДАКТИРОВАТЬ: Важно избегать возможности создания недействительных "петель" трубы. Один из способов сделать это - сохранить для каждого разрешенного цвета я каждого квадрата x два бита информации: связан ли квадрат x с контуром определенных i-цветных плит первым концом i-цвета и тем же для второй i-цветной конечной точки. Затем при рекурсировании никогда не выбирайте квадрат, у которого есть два соседа с одним и тем же набором бит (или без набора бит) для любого разрешенного цвета.]

Фактически вам не нужно использовать какие-либо логические выводы, но чем больше и лучше вы используете вычеты, тем быстрее программа будет работать, как они (возможно, резко) уменьшит количество рекурсии. Некоторые полезные выводы включают в себя:

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

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

Этот простой подход обеспечивает полное решение без какой-либо рекурсии в примере 5x5: квадраты в (5, 2), (5, 3), (4, 3) и (4, 4) вынуждены быть оранжевыми; (4, 5) вынужден быть зеленым; (5, 5) также вынуждены быть зелеными в силу того факта, что никакой другой цвет не мог попасть на этот квадрат, а затем обратно; теперь оранжевая дорожка, заканчивающаяся на (4, 4), некуда идти, за исключением того, чтобы закончить оранжевую дорожку (3, 4). Также (3, 1) вынужден быть красным; (3, 2) вынуждена быть желтой, что, в свою очередь, вынуждает (2, 1), а затем (2, 2) быть красным, что, наконец, вынуждает желтый путь заканчиваться (3, 3). Красная труба при (2, 2) усиливает (1, 2) синюю, а красные и синие пути заканчиваются полностью, "заставляя друг друга", когда они идут.

Ответ 3

Я нашел запись в блоге Needlessly Complex, которая полностью объясняет, как использовать SAT для решения этой проблемы.

Код также является открытым исходным кодом, поэтому вы можете посмотреть его (и понять) в действии.

Я приведу здесь цитату, в которой описываются правила, которые необходимо реализовать в SAT:

• Каждой ячейке присваивается один цвет.

• Цвет каждой ячейки конечной точки известен и указан.

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

Спасибо, @Matt Zucker для создания этого!

Ответ 4

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

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

Это истинные "большинство времени", но не всегда.

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

Конечно, прежде чем использовать эти правила "большинства времен", вам необходимо следовать правилам абсолютности (см. два вывода из сообщения j_random_hacker).

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

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