Resuelve este Alcazar por mi

39

Recientemente he estado jugando un juego llamado Alcazar. Es un juego de rompecabezas en el que tu objetivo es entrar por una puerta, atravesar todos los cuadrados y salir por otra puerta. Las únicas reglas son:

  • Entra una vez, sal una vez;
  • Pase por todos los cuadrados;
  • No pases por un cuadrado más de una vez

La imagen a continuación muestra un ejemplo de un tablero de Alcazar y, a su derecha, el rompecabezas resuelto (por supuesto, este es fácil):

Muestra Alcazar Puzzle

Puede encontrar más acertijos en http://www.theincrediblecompany.com/try-alcazar y descargar el juego en PlayStore (PS: no es un anuncio).

Mi problema es que casi termino el juego, excepto por un nivel. Simplemente no puedo encontrar una manera de resolverlo. Entonces, el desafío que propongo es: crear un algoritmo que resuelva cualquier nivel normal de Alcazar 1 solucionable 2 .

Por supuesto, no le pido a nadie que construya un intérprete de imágenes para leer la imagen y resolver el rompecabezas (¿o sí?). Así que volví a dibujar el rompecabezas anterior usando personajes de dibujo de caja. El rompecabezas y su solución sería así:

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

En el tablero de arriba, ▒son las celdas que se llenarán.

Se puede observar que hay una abertura vertical y horizontal entre las celdas. Esto se debe a que tuve que insertar un espacio entre las celdas para agregar las paredes. Esto significa que las únicas celdas importantes son las que están arriba, abajo, a la izquierda y a la derecha de cada celda. Las diagonales podrían eliminarse sin pérdida de información. Por ejemplo, en el tablero a continuación, ambos representan el mismo rompecabezas:

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

Esto también es válido para las soluciones. Es decir, no es necesario conectar las células:

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

En el ejemplo anterior, ambas soluciones significan lo mismo.

Sí, los casos de prueba. Aquí están:

Rompecabezas 1

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

Puzzle 2

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

Puzzle 3

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

rompecabezas 4

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

Puzzle 5

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

Puzzle 6

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

Puzzle 7

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

Puzzle 8 (Lo siento, realmente no tengo la solución para este)

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

Entrada

La entrada de su código puede tener cualquier representación siempre que siga estas reglas:

  1. Debe ser una entrada gráfica. Por lo tanto, no es posible leer una lista de coordenadas, por ejemplo.

  2. Las paredes horizontales, las paredes verticales y las puertas deben ser distintas, y deben estar hechas de un carácter visible (sin caracteres en blanco).

  3. El ▒puede ser reemplazado por espacios en blanco. Solo usé un personaje diferente para resaltarlos.

Salida

La salida también puede tener cualquier representación siempre que siga estas reglas:

  1. Debe ser una salida gráfica. Es decir, uno puede ver el camino al mirarlo.

  2. La regla número uno implica que los caracteres de la ruta sean diferentes. Es decir, habrá al menos 6 caracteres de ruta; horizontal, vertical y esquinas.

  3. Para que la respuesta sea válida, la salida debe ser la misma placa que la entrada (obviamente) con todas las celdas (en mi representación, la ▒) llena. Llenar los espacios entre las celdas es opcional.

Tanteo

Este es el código de golf , por lo que gana el código más corto en bytes.

1 Hay algunos niveles de Alcazar que tienen celdas y túneles opcionales. Estos no serán considerados.

2 Hay algunas placas Alcazar que son imposibles.

code-golf ascii-art puzzle-solver Phelype Oleinik
fuente
2
Mi programa no encuentra una solución para el rompecabezas 8. ¿Estás seguro de que es solucionable? Tal vez algún error tipográfico?
edc65
1
@ edc65 igual aquí - no hay solución para el # 8
ngn

Respuestas:

5

Python 3 , 809 728 723 714 693 688 684 663 657 641 639 627 610 571 569 bytes

Editar: Guardado 55 bytes gracias a @Felipe Nardi Batista

No ejecuta el último caso de prueba en 60 segundos en TIO, pero de todos modos debería funcionar correctamente. Devuelve una lista de coordenadas para la ruta. Alrededor de 400 de los bytes se utilizan para obtener las listas de datos de la E / S.

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))

Pruébalo en línea!

Halvard Hummel
fuente
@HalvardHummel Bueno, perdón por la mala formulación del desafío. Entonces propongo lo siguiente. La puntuación se calculará multiplicando el recuento de bytes por el tiempo de ejecución, por lo que se recompensará tanto el tiempo de ejecución como el recuento de bytes. ¿Qué piensas?
Phelype Oleinik
1
@PhelypeOleinik No creo que sea un muy buen sistema de puntuación. Mantenerlo en el golf mixto es una mejor solución, pero si realmente está buscando una solución, estoy seguro de que se puede modificar para que sea más eficiente.
caird coinheringaahing
@cairdcoinheringaahing Entiendo que la solución más elegante es mantenerse como está. Pero un algoritmo que lleva "días o incluso meses" para resolver un tablero de rompecabezas 8x12 es de alguna manera ineficiente, ¿no crees? A mi modo de ver, un algoritmo que resuelve el problema en menos tiempo debería ser recompensado, incluso si es un poco más largo.
Phelype Oleinik
3
@PhelypeOleinik La "eficiencia" del código es irrelevante. Nos ha desafiado a escribir un código corto, y esa es la base de su desafío. Agregar la velocidad a la que se ejecuta el programa a la mezcla solo complica las cosas innecesariamente y también puede explotarse para obtener puntajes ridículos. Los sistemas de puntuación personalizados no tienden a funcionar. Si desea un código corto, haga una pregunta de código de golf. Si desea un código rápido, haga una pregunta de código más rápido. Intentar mezclarlos no es una buena idea.
Letra
En su exec(...)cadena hay cinco líneas nuevas, representadas como \n5 * 2 = 10 bytes. El uso de una cadena entre comillas triples agregaría 4 bytes ( ...''...''...) pero luego eliminaría 5 bytes, ya que podrían usarse caracteres de línea nuevos reales. En total, esto podría ahorrar un byte.
Jonathan Frech
5

APL (Dyalog Classic) , 319 bytes

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

Pruébalo en línea!

Los usos de entrada en =#F7LJ<>^v.lugar de ═║╔╗╚╝╣╠╩╦▒para encajar en el juego de caracteres clásico .

Todos los casos de prueba, excepto el último, pasan en unos segundos.

La última prueba toma 47 minutos en mi computadora y no da solución.

Cuando el camino resultante usa una puerta cerca de una esquina, puede representarse incorrectamente (es como si el sendero se bifurca y pasa a través de una puerta imaginaria adicional), pero aún es perceptible y sin ambigüedades.

ngn
fuente
¡Muy bien! Si puedo preguntar, ¿qué enfoque utiliza su código para resolver? ¿Búsqueda exhaustiva o algo más elegante? Además, como dije, no resolví el último rompecabezas a mano. No tiene una solución clara paso a paso y requiere, incluso cuando se resuelve a mano, una conjetura para encontrar algunas respuestas. Este rompecabezas está incluido en el juego original, pero es posible que no tenga una solución, por lo que probablemente no debería tenerse en cuenta.
Phelype Oleinik
1
@PhelypeOleinik Sí, es una búsqueda exhaustiva poco sofisticada. La razón por la que encuentra rápidamente las soluciones existentes es porque primero intenta el caso más probable (con vs sin un cierto borde en el gráfico: mi heurística es el mínimo de los grados de los dos vértices, menor es más probable). La razón por la que funciona horriblemente en el último caso es que prueba todas las posibilidades de todos modos y elimina la recurrencia solo en contradicciones obvias. Parece que no se conocen buenos algoritmos de ruta hamiltoniana, incluso para el caso especial de gráficos de grado acotado (≤4 vecinos).
ngn
3

JavaScript (ES6), 274 bytes

Ingrese como una cadena multilínea, cada línea termina con un carácter de nueva línea. Las puertas están marcadas con el carácter '2'

Salida como una cadena multilínea con la ruta marcada con el carácter '1', muy fácilmente discernible.

Esta es una Búsqueda de profundidad primero , probando todos los caminos y retrocediendo cuando está atascado. No es eficiente en absoluto, pero puede resolver acertijos 1 .. 6 en menos de 1 minuto.

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,' '))

Menos golf

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,' ') 
)

Dentro del fragmento de prueba hay una solución que utiliza un DFS con alguna restricción que resuelve el rompecabezas 7 en menos de un minuto (en mi PC). Puzzle 8 no tiene solución. Restricciones:

  • Todas las celdas vacías deben ser accesibles desde la celda actual: el espacio vacío no debe dividirse en dos partes
  • Debe haber una puerta accesible
  • Una configuración de celdas no se puede explorar más de una vez
  • No se puede omitir una celda que solo tiene una celda adyacente vacía

Prueba

Cuidado, el rompecabezas 7 está más allá del tiempo de espera para la ejecución de javascript en cualquier navegador (usando el solucionador Corto y Lento)

Mostrar fragmento de código

edc65
fuente