Решите этот Алькасар для меня

39

Недавно я играл в игру под названием Alcazar. Это настольная игра-головоломка, в которой ваша цель - войти через одну дверь, пройти через все квадраты и выйти через другую дверь. Единственные правила:

  • Введите один раз, оставьте один раз;
  • Пройти через все квадраты;
  • Не проходите через квадрат более одного раза

На рисунке ниже показан пример доски Alcazar и справа решенная головоломка (конечно, это простая задача):

Образец пазла Альказар

Вы можете найти больше головоломок на http://www.theincrediblecompany.com/try-alcazar и загрузить игру в PlayStore (PS: не реклама).

Моя проблема в том, что я почти закончил игру, за исключением одного уровня. Я просто не могу найти способ решить это. Итак, задача, которую я предлагаю: создать алгоритм, который решает любой нормальный 1- разрешимый 2-й уровень Алькасара.

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

╔═══════╗         ╔═══════╗
║▒ ▒ ▒ ▒║         ║┌─┐ ┌─┐║
║     ║ ║         ║│ │ │║│║
╣▒ ▒ ▒║▒╠         ╣│ └─┘║└╠
║ ══╦═╩═╣         ║│══╦═╩═╣
║▒ ▒║▒ ▒║         ║└─┐║┌─┐║
║   ║   ║   ==>   ║  │║│ │║
╣▒ ▒║▒ ▒║         ╣┐ │║│ │║
║ ║ ║   ║         ║│║│║│ │║
╣▒║▒ ▒ ▒║         ╣│║└─┘ │║
║ ║     ║         ║│║    │║
║▒ ▒ ▒ ▒║         ║└─────┘║
╚═══════╝         ╚═══════╝

На доске выше, ▒ячейки должны быть заполнены.

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

╔════╩╗         ═ ═ ╩ 
║▒ ▒ ▒║        ║▒ ▒ ▒║
║ ═══ ║           ═   
║▒ ▒ ▒║   ==   ║▒ ▒ ▒║
║     ║               
║▒ ▒ ▒║        ║▒ ▒ ▒║
╚╦════╝         ╦═ ══

Это также верно для решений. То есть не обязательно подключать ячейки:

╔════╩╗        ╔════╩╗        ╔════╩╗
║▒ ▒ ▒║        ║┌───┘║        ║┌ ─ ┘║
║ ═══ ║        ║│═══ ║        ║ ═══ ║
║▒ ▒ ▒║   ==   ║└───┐║   =>   ║└ ─ ┐║
║     ║        ║    │║        ║     ║
║▒ ▒ ▒║        ║┌───┘║        ║┌ ─ ┘║
╚╦════╝        ╚╦════╝        ╚╦════╝

В приведенном выше примере оба решения означают одно и то же.

Да, тестовые случаи. Вот они:

Головоломка 1

╔════╩╗        ╔════╩╗
║▒ ▒ ▒║        ║┌ ─ ┘║
║ ═══ ║        ║ ═══ ║
║▒ ▒ ▒║   =>   ║└ ─ ┐║
║     ║        ║     ║
║▒ ▒ ▒║        ║┌ ─ ┘║
╚╦════╝        ╚╦════╝

Головоломка 2

╔═════╗        ╔═════╗
║▒ ▒ ▒║        ║┌ ─ ┐║
║   ║ ║        ║   ║ ║
╣▒ ▒║▒║        ╣└ ┐║│║
║ ║ ║ ║   =>   ║ ║ ║ ║
╣▒║▒ ▒╠        ╣┐║│ │╠
║ ║   ║        ║ ║   ║
║▒ ▒ ▒║        ║└ ┘ │║
╚════╦╝        ╚════╦╝

Головоломка 3

╔════╩══╗        ╔════╩══╗
║▒ ▒ ▒ ▒║        ║┌ ┐ └ ┐║
║ ║   ║ ║        ║ ║   ║ ║
╣▒║▒ ▒║▒╠        ╣┘║└ ┐║│╠
║ ╚══ ║ ║        ║ ╚══ ║ ║
║▒ ▒ ▒ ▒╠   =>   ║┌ ─ ┘ │╠
║   ═══ ║        ║   ═══ ║
║▒ ▒ ▒ ▒║        ║│ ┌ ┐ │║
║   ║   ║        ║   ║   ║
║▒ ▒║▒ ▒║        ║└ ┘║└ ┘║
╚═══╩═══╝        ╚═══╩═══╝

головоломка 4

╔═══════╗        ╔═══════╗
║▒ ▒ ▒ ▒║        ║┌ ┐ ┌ ┐║
║     ║ ║        ║     ║ ║
╣▒ ▒ ▒║▒╠        ╣│ └ ┘║└╠
║ ══╦═╩═╣        ║ ══╦═╩═╣
║▒ ▒║▒ ▒║        ║└ ┐║┌ ┐║
║   ║   ║   =>   ║   ║   ║
╣▒ ▒║▒ ▒║        ╣┐ │║│ │║
║ ║ ║   ║        ║ ║ ║   ║
╣▒║▒ ▒ ▒║        ╣│║└ ┘ │║
║ ║     ║        ║ ║     ║
║▒ ▒ ▒ ▒║        ║└ ─ ─ ┘║
╚═══════╝        ╚═══════╝

Головоломка 5

╔══╩══════╗        ╔══╩══════╗
║▒ ▒ ▒ ▒ ▒║        ║┌ ─ ┐ ┌ ┐║
║   ║     ║        ║   ║     ║
║▒ ▒║▒ ▒ ▒╠        ║└ ┐║└ ┘ │╠
║   ╠════ ║        ║   ╠════ ║
║▒ ▒║▒ ▒ ▒║   =>   ║┌ ┘║┌ ─ ┘║
║   ║     ║        ║   ║     ║
║▒ ▒║▒ ▒ ▒╠        ║└ ┐║└ ─ ─╠
║   ╠═════╣        ║   ╠═════╣
║▒ ▒║▒ ▒ ▒║        ║┌ ┘║┌ ─ ┐║
║   ║     ║        ║   ║     ║
║▒ ▒ ▒ ▒ ▒║        ║└ ─ ┘ ┌ ┘║
╚══╦═══╦══╝        ╚══╦═══╦══╝

Головоломка 6

╔═══════════╗        ╔═══════════╗
║▒ ▒ ▒ ▒ ▒ ▒║        ║┌ ┐ ┌ ┐ ┌ ┐║
║           ║        ║           ║
║▒ ▒ ▒ ▒ ▒ ▒║        ║│ └ ┘ └ ┘ │║
║       ═══ ║        ║       ═══ ║
║▒ ▒ ▒ ▒ ▒ ▒║        ║└ ┐ ┌ ─ ─ ┘║
║     ═══   ║        ║     ═══   ║
╣▒ ▒ ▒ ▒ ▒ ▒╠   =>   ╣┐ │ │ ┌ ┐ ┌╠
║           ║        ║           ║
║▒ ▒ ▒ ▒ ▒ ▒║        ║│ │ │ │ │ │║
║   ║   ║   ║        ║   ║   ║   ║
║▒ ▒║▒ ▒║▒ ▒║        ║│ │║│ │║│ │║
║   ║   ║   ║        ║   ║   ║   ║
║▒ ▒ ▒ ▒ ▒ ▒║        ║└ ┘ └ ┘ └ ┘║
╚═══════════╝        ╚═══════════╝

Головоломка 7

╔════╩════════╦╩╗        ╔════╩════════╦╩╗
║▒ ▒ ▒ ▒ ▒ ▒ ▒║▒║        ║┌ ─ ─ ─ ─ ─ ┐║│║
║ ║       ║   ║ ║        ║ ║       ║   ║ ║
║▒║▒ ▒ ▒ ▒║▒ ▒ ▒║        ║│║┌ ─ ─ ┐║┌ ┘ │║
║ ║ ║ ═══ ║     ║        ║ ║ ║ ═══ ║     ║
║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒╠        ║│ │║┌ ─ ┘ └ ┐ │╠
║   ║           ║        ║   ║           ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║        ║│ │ └ ┐ ┌ ┐ └ ┘║
║     ║ ║     ══╣        ║     ║ ║     ══╣
║▒ ▒ ▒║▒║▒ ▒ ▒ ▒║        ║│ └ ┐║│║│ └ ─ ┐║
║     ║ ║       ║        ║     ║ ║       ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║        ║│ ┌ ┘ │ └ ┐ ┌ ┘║
║           ║ ══╣   =>   ║           ║ ══╣
║▒ ▒ ▒ ▒ ▒ ▒║▒ ▒║        ║└ ┘ ┌ ┘ ┌ ┘║└ ┐║
╠══       ║ ╚══ ║        ╠══       ║ ╚══ ║
║▒ ▒ ▒ ▒ ▒║▒ ▒ ▒║        ║┌ ┐ └ ┐ │║┌ ─ ┘║
║     ║ ║ ║     ║        ║     ║ ║ ║     ║
║▒ ▒ ▒║▒║▒ ▒ ▒ ▒║        ║│ └ ┐║│║│ └ ─ ┐║
║ ║   ║ ║ ╔══   ║        ║ ║   ║ ║ ╔══   ║
║▒║▒ ▒ ▒ ▒║▒ ▒ ▒║        ║│║┌ ┘ │ │║┌ ┐ │║
║ ║     ║ ║     ║        ║ ║     ║ ║     ║
║▒ ▒ ▒ ▒║▒ ▒ ▒ ▒║        ║│ └ ─ ┘║└ ┘ │ │║
║       ╚══     ║        ║       ╚══     ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║        ║└ ─ ─ ─ ─ ─ ┘ │║
╚════╦═╦═╦═════╦╝        ╚════╦═╦═╦═════╦╝

Головоломка 8 (Извините, у меня действительно нет решения этой проблемы)

╔══╩╦══╩═══╩═╩═╩═══╩╗
║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║
║   ║               ║
╣▒ ▒║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║
║   ╚══ ╔══     ╔═══╣
╣▒ ▒ ▒ ▒║▒ ▒ ▒ ▒║▒ ▒╠
║       ║   ╔══ ║   ║
╣▒ ▒ ▒ ▒ ▒ ▒║▒ ▒ ▒ ▒╠
║           ║       ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒╠
║           ║       ║
╣▒ ▒ ▒ ▒ ▒ ▒║▒ ▒ ▒ ▒╠
║   ╔═══╗   ╚══     ║
╣▒ ▒║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒║
║   ║   ║           ║
╣▒ ▒║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒╠
║ ══╝   ║       ╔══ ║
║▒ ▒ ▒ ▒║▒ ▒ ▒ ▒║▒ ▒║
║   ══╗ ╚══ ╔══ ║   ║
╣▒ ▒ ▒║▒ ▒ ▒║▒ ▒ ▒ ▒╠
║     ║     ║   ║   ║
╣▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║▒ ▒║
║   ═══   ══╗   ║   ║
╣▒ ▒ ▒ ▒ ▒ ▒║▒ ▒ ▒ ▒╠
╠══ ║       ║   ╔══ ║
║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒║▒ ▒╠
║   ╚══ ║   ║   ║   ║
╣▒ ▒ ▒ ▒║▒ ▒║▒ ▒ ▒ ▒╠
║       ║   ║       ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║
╚══╦═══╦═══╦═╦═╦═╦═╦╝

вход

Ввод вашего кода может иметь любое представление при условии соблюдения следующих правил:

  1. Это должен быть графический ввод. Так что невозможно прочитать список координат, например.

  2. Горизонтальные стены, вертикальные стены и двери должны быть различимы, и они должны быть сделаны из видимого символа (без пустых символов).

  3. ▒Могут быть заменены пробелами. Я просто использовал другого персонажа, чтобы выделить их.

Выход

Вывод также может иметь любое представление, если оно соответствует этим правилам:

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

  2. Правило номер один подразумевает, что символы пути будут разными. То есть должно быть не менее 6 символов пути; горизонтальный, вертикальный и углы.

  3. Чтобы ответ был действительным, выходные данные должны быть на той же доске, что и входные данные (очевидно) со всеми ▒заполненными ячейками (в моем представлении ). Заполнение пробелов между ячейками необязательно.

счет

Это код-гольф , поэтому выигрывает самый короткий код в байтах.

1 В некоторых уровнях Alcazar есть дополнительные ячейки и туннели. Это не будет рассматриваться.

2 Некоторые доски Alcazar невозможны.

code-golf ascii-art puzzle-solver Фелипе Олейник
источник
2
Моя программа не находит решения для головоломки 8. Вы уверены, что она разрешима? Может быть, опечатка?
edc65
1
@ edc65 то же самое здесь - нет решения для # 8
ngn

Ответы:

5

Python 3 , 809 728 723 714 693 688 684 663 657 641 639 627 610 571 569 байт

Редактировать: Сохранено 55 байтов благодаря @ Филипе Нарди Батиста

Не выполняет последний контрольный пример за 60 секунд на TIO, но, тем не менее, должен работать правильно. Возвращает список координат для пути. Около 400 байтов используются для получения списков данных из ввода / вывода.

A=enumerate
I,J="═║"
B=range
L=len
K=-1
Z=1,0
X=0,1
C=K,0
V=0,K
E=lambda a,b,p:(((a,b)in d)*L(p)==H*h)*p or max([E(q+a,w+b,p+[(q+a,w+b)])for q,w in y[a][b]if~-((q+a,w+b)in p)*-h>w+b>K<q+a<H]+[[]])
x=input().split("\n")
h=L(x[0])//2
H=L(x)//2
y=[[{C,Z,V,X}for i in B(h)]for j in B(H)]
d=[]
exec('d+=[(%s,i)for i,a in A(x[%s][1::2])if I<a]\nfor i,u in A(x[%s:%s:2]):\n d+=[(i,0)]*(J<u[0])+[(i,h-1)]*(J<u[K])\n for j,w in A(u[%s:%s:2]):\n  if"%s"==w:y[i][j]-={%s};y[i+%s][j+%s]-={%s}\n'*2%(0,*X,"",2,K,J,X,*X,V,H-1,K,2,K,1,"",I,Z,*Z,C))
print(max(E(*D,[D])for D in d))

Попробуйте онлайн!

Халвард Хаммель
источник
@HalvardHummel Ну, извините за плохую формулировку задачи. Поэтому я предлагаю следующее. Оценка должна быть рассчитана путем умножения количества байтов на время выполнения, поэтому и время выполнения, и количество байтов должны быть вознаграждены. Что вы думаете?
Фелипе Олейник,
1
@PhelypeOleinik Я не думаю, что это очень хорошая система начисления очков. Лучше решить эту проблему для гольфа, но если вы действительно ищете решение, я уверен, что это можно изменить, чтобы сделать его более эффективным.
Caird Coneheringaahing
@cairdcoinheringaahing Я понимаю, что самое элегантное решение - оставить все как есть. Но алгоритм, который занимает «дни или даже месяцы», чтобы решить головоломку 8x12, почему-то неэффективен, не так ли? На мой взгляд, алгоритм, который решает проблему за меньшее время, должен быть вознагражден, даже если он немного дольше.
Фелипе Олейник,
3
@PhelypeOleinik «Эффективность» кода не имеет значения. Вы предложили нам написать короткий код, и это основа вашей задачи. Добавление скорости, с которой программа работает в миксе, только усложняет вещи и может также использоваться для смешных результатов. Пользовательские системы начисления баллов не работают. Если вы хотите короткий код, задайте вопрос по коду для игры в гольф. Если вы хотите быстрый код, задайте вопрос с быстрым кодом. Попытка смешать их не очень хорошая идея.
LyricLy
В вашей exec(...)строке есть пять новых строк, представленных как \n5 * 2 = 10 байтов. Использование строки в тройных кавычках добавит 4 байта ( ...''...''...), но затем удалит 5 байтов, поскольку могут использоваться фактические символы новой строки. Всего это может сэкономить один байт.
Джонатан Фрех,
5

APL (Dyalog Classic) , 319 байтов

i←N⍴j←⍳1+n←×/N←⌊2÷⍨⍴a←⎕⋄e←↑⊃,/{(,~'#='∊⍨a[(⍵⌽⍳2)∘+¨2×⍳N+⍵=⍳2])/,2,/[⍵]⊃,[⍵]/n i n}¨⍳2
r←{e g c←⍵⋄d←+/j∘.=∊g⋄e⌿⍨←(≠/c[e])∧2>⌈/d[e]⋄n≡≢g:g⍪j/⍨d=1⋄0≡≢e:0⋄2>⌊/d+D←+/j∘.=,e:0⋄u←,¯1↑e←e[⍒⌊/D[e];]⋄e↓⍨←¯1⋄0≢r←∇e(g⍪u)(c-(-/c[u])×c=c[⊃u]):r⋄∇e g c}e(0↑e)j
a[1+2×⍳N]←' ??┌?─┐┬?└│├┘┴┤┼'[2⊥(↑(⊂i),¨¨{⊖∘⍉⍣⍵⊢n⍪¯1↓⌽∘⍉⍣⍵⊢i}¨⍳4)∊↓r⍪⌽r]
a

Попробуйте онлайн!

Ввод используется =#F7LJ<>^v.вместо ═║╔╗╚╝╣╠╩╦▒того, чтобы вписаться в классическую кодировку .

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

Последний тест занимает 47 минут на моем компьютере и не дает решения.

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

СПП
источник
Очень хорошо! Если я могу спросить, какой подход использует ваш код для решения? Исчерпывающий поиск или что-то более элегантное? Кроме того, как я уже сказал, я не решал последнюю головоломку вручную. Он не имеет четкого пошагового решения и требует, даже при решении вручную, догадки, чтобы найти некоторые ответы. Эта головоломка включена в оригинальную игру, но может не иметь решения, поэтому, вероятно, не следует принимать во внимание.
Фелипе Олейник,
1
@PhelypeOleinik Да, это довольно простой поиск. Причина, по которой он быстро находит существующие решения, заключается в том, что он сначала пытается выполнить более вероятный случай (с vs без определенного ребра в графе - моя эвристика - это минимум степеней двух вершин, нижняя - более вероятная). Причина, по которой он работает ужасно в последнем случае, заключается в том, что он все равно проверяет все возможности и сокращает рекурсию только на очевидных противоречиях. Кажется, нет известных хороших алгоритмов гамильтоновых путей, даже для частного случая графов ограниченной степени (≤4 соседей).
СПП
3

JavaScript (ES6), 274 байта

Ввод в виде многострочной строки, каждая строка заканчивается символом новой строки. Двери отмечены символом «2»

Выведите в виде многострочной строки с путем, отмеченным символом «1», очень легко различимым.

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

z=>(w=z.search`
`+1,t=(w-2)*(z.length/w-1)/4,z=[...z],R=(p,l,q)=>[1,-1,w,-w].some(d=>l<t?z[q=p+d]<1&z[q+d]<1&&(R(q+d,++z[q]+l)||--z[q]):z[p+d]>1&&--z[p+d],++z[p])||--z[p],z.some((c,i)=>-c&&(x=i%w,R(i<w?i+w:x?x>w-3?i-1:i-w:i+1,--z[i])||++z[i]*0))&&z.join``.replace(/0/g,' '))

Меньше гольфа

z => (
  w = z.search`\n`+1, // board width and offset to next row
  t = (w-2)*(z.length/w-1)/4, // total size of board, number of cells that must be filled
  z = [...z], // convert string to array
  d = [1, -1, w, -w], // delta to next position in all directions
  // recursive search
  // given a current position, try to move in all directions
  // if the board is not full, look for an emoty cell
  // if the board is full, look for a door
  R = (p, // current position
       l, // fill level
       q  // parameter used as a local variable
      ) => (
        ++z[p], // mark current position
        // .some will terminate early if the called function returns true
        // in case of return true the recursive function returns all way up leaving the path marked
        // in case of return false we need to unmark path and backtrack
        d.some( d => // for each direction, offset in d
          l < t // check if board is full
          ? z[q=p+d] < 1 & z[q+d] < 1 // not full, try to advance 
            && (++z[q], // mark intermediate cell
                R(q+d, 1+l) // recursive call incrementing fill level
                || --z[q] // if R return false, backtrack: unmark intermediate cell
               )
          : z[p+d] > 1 && --z[p+d]
        ) // full, ok only if I find a door nearby
        || --z[p], // if some returns false, unmark and backtrak
  // look for doors and for each door call R 
  // when R returns true, stop and return the marked board
  // if R returns false for each door, no solution, return false
  z.some((c,i) => 
   -c && // if numeric and != 0
    (x = i%w,
     z[i]=1, // marking starting position (door)
     R(i<w ? i+w : x ? x > w-3 ? i-1 : i-w : i+1, 1)
     || (z[i] = 2, false) // if R returned false, unmark a return false
    ) 
  ) && z.join``.replace(/0/g,' ') 
)

Внутри тестового фрагмента есть решение, использующее DFS с некоторым ограничением, которое решает головоломку 7 менее чем за минуту (на моем ПК). Головоломка 8 не имеет решения. Ограничения:

  • Все пустые ячейки должны быть доступны из текущей ячейки - пустое пространство не должно быть разделено на две части
  • Должна быть доступная дверь
  • Конфигурация ячеек не может быть исследована более одного раза
  • Не удается пропустить ячейку, в которой есть только одна пустая соседняя ячейка

Тест

Осторожно, головоломка 7 намного превышает тайм-аут для выполнения javascript в любом браузере (с использованием решателя Short and Slow)

Показать фрагмент кода

edc65
источник