#algorithm #graph #path-finding
Вопрос:
Я только что нашел головоломку, которая заставила меня задуматься. Подсказка:
Учитывая карту M , состоящую из N*N плиток (N может быть размером до 1000), рассмотрим такую операцию R , которая R{x,y,t} поворачивает плитку из M, в координатах [x,y] , t раз — поворот на 90 градусов по часовой стрелке.
Вычислите набор R операций, которые создают карту, не содержащую циклов и висячих плиток (для каждой плитки она связывается со своими соседями по крайней мере по одному краю).
В качестве примера: Ввод:
┛┃╻┗╺╺┏╻
┣╹╺╋┫┓┃╹
┏┏┓┏━╻━━
╹┳┳╻╹━┣┛
━╻┻┣╻┳┣╺
┏┓┃┓┫┻╹╺
┗┳┳┓┛╋┓━
╻┗┓╺╸┗━┏
Может быть переставлен на:
┏━╸┏╸╻┏╸
┣╸╺╋┳┛┃╻
┗┓┏┛┃╻┃┃
╻┣┫╻╹┃┣┛
┃╹┣┫╻┣┻╸
┗┓┃┗┻┫╻╻
┏┫┣┓┏╋┛┃
╹┗┛╹╹┗━┛
Которая представляет собой модифицированную карту, которая не содержит циклов или оборванных фрагментов.
Набор возможных плиток включает в себя:
"╸" and rotations: "╺", "╻", "╹"
"━" and rotation: "┃"
"┓" and rotations: "┛", "┏", "┗"
"┣" and rotations: "┳", "┻", "┫"
"╋"
Конечно, решение грубой силы (поворачивайте каждую фигуру, проверяйте правильность) нежизнеспособно, так как карта может быть большой.
Каждое решение, которое я могу придумать (график с остовным деревом, DP, даже генетический алгоритм, рекурсивное отслеживание — можем ли мы вообще что-нибудь обрезать?) оказывается столь же неэффективным, как и применение грубой силы. Если набор уникален, это что-нибудь меняет?
Лучшие,
Комментарии:
1. «без свисающих плиток» значительно сокращает пространство поиска. Таким образом, даже грубый подход должен устранить многие случаи довольно рано.
2. Что означает «повернуть плитку t раз»? Возможно, повернуть плитку на t раз на 90 градусов по часовой стрелке? А как насчет болтания? Возможно, что-то вроде того, что каждый край черной плитки касается хотя бы одного черного края соседней плитки? Является ли это представлением какой-то физической системы или просто абстрактной идеей?
3. Эй, @ravenspoint, я отредактирую, чтобы добавить ваши предложения. Это абстрактная идея.
4. Одна попытка была бы решением проблемы SAT. Если я правильно интерпретирую эту задачу, то при некоторой предварительной обработке каждой 4-соседней плитки вся проблема без ацикличности может быть описана как:
tile x,y,o -> neighbor-tile-config_0 || neighbor-tile-config_1, ...где конфигурация соседней плитки-это другая (априори выведенная соседняя) плитка, выбранная ориентация которой делаетtile x,y,oне зависающийexactly_one(tile x,y,{o})для каждой плитки. Ацикличность сложнее (см.SAT modulo Graphs: Acyclicity (Gebser et al.). Сработает ли этоN=1000, может быть. Это (имхо) победит грубую силу.