Resolva este Alcazar para mim

39

Recentemente, eu tenho jogado um jogo chamado Alcazar. É um jogo de tabuleiro onde seu objetivo é entrar por uma porta, passar por todos os quadrados e sair por outra porta. As únicas regras são:

  • Entre uma vez, saia uma vez;
  • Passe por todos os quadrados;
  • Não passe por um quadrado mais de uma vez

A imagem abaixo mostra um exemplo de um quadro do Alcazar e, à direita, o quebra-cabeça resolvido (é claro que é fácil):

Sample Alcazar Puzzle

Você pode encontrar mais quebra-cabeças em http://www.theincrediblecompany.com/try-alcazar e baixar o jogo na PlayStore (PS: Não é um anúncio).

Meu problema é que quase terminei o jogo, exceto um nível. Simplesmente não consigo encontrar uma maneira de resolvê-lo. Portanto, o desafio que proponho é: criar um algoritmo que resolva qualquer nível normal de 1 Alcazar 2 solucionável .

Obviamente, não estou pedindo a ninguém que construa um intérprete de imagem para ler a imagem e resolver o quebra-cabeça (ou estou?). Então desenhei o quebra-cabeça acima usando caracteres de desenho de caixa. O quebra-cabeça e sua solução seriam assim:

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

No quadro acima, ▒estão as células a serem preenchidas.

Pode-se observar que existe um gabarito vertical e horizontal entre as células. Isso ocorre porque eu tive que inserir um espaço entre as células para adicionar as paredes. Isso significa que as únicas células importantes são as acima, abaixo, à esquerda e à direita de cada célula. As diagonais podem ser removidas sem perda de informações. Por exemplo, no quadro abaixo, ambos representam o mesmo quebra-cabeça:

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

Isso também é válido para as soluções. Ou seja, não é necessário conectar as células:

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

No exemplo acima, ambas as soluções significam o mesmo.

Sim, os casos de teste. Aqui estão eles:

Quebra-cabeça 1

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

Puzzle 2

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

Puzzle 3

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

quebra-cabeça 4

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

Quebra-cabeça 5

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

Puzzle 6

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

Quebra-cabeça 7

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

Quebra-cabeça 8 (Desculpe, eu realmente não tenho a solução para este)

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

Entrada

A entrada do seu código pode ter qualquer representação, desde que siga estas regras:

  1. Deve ser uma entrada gráfica. Portanto, não é possível ler uma lista de coordenadas, por exemplo.

  2. Paredes horizontais, paredes verticais e portas devem ser distintas e devem ser feitas de um caractere visível (sem caracteres em branco).

  3. O ▒pode ser substituído por espaços em branco. Eu apenas usei um personagem diferente para destacá-los.

Saída

A saída também pode ter qualquer representação, desde que siga estas regras:

  1. Deve ser uma saída gráfica. Ou seja, pode-se ver o caminho olhando para ele.

  2. A regra número um implica que os caracteres do caminho sejam diferentes. Ou seja, haverá pelo menos 6 caracteres de caminho; horizontal, vertical e cantos.

  3. Para que a resposta seja válida, a saída deve ser a mesma placa que a entrada (obviamente) com todas as células (na minha representação, as ▒) preenchidas. Preencher as lacunas entre as células é opcional.

Pontuação

Isso é código-golfe , então o código mais curto em bytes vence.

1 Existem alguns níveis do Alcazar que possuem células e túneis opcionais. Estes não serão considerados.

2 Existem alguns painéis do Alcazar que são impossíveis.

code-golf ascii-art puzzle-solver Phelype Oleinik
fonte
2
Meu programa não encontra uma solução para o quebra-cabeça 8. Tem certeza de que é solucionável? Talvez algum erro de digitação?
Edc65 17/09/19
1
@ edc65 mesmo aqui - não há solução para # 8
NGN

Respostas:

5

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

Edit: Salvo 55 bytes graças a @Felipe Nardi Batista

Não executa o último caso de teste em 60 segundos no TIO, mas deve funcionar corretamente. Retorna uma lista de coordenadas para o caminho. Cerca de 400 bytes são usados ​​para obter as listas de dados da 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))

Experimente online!

Halvard Hummel
fonte
@ HalvardHummel Bem, desculpe pela formulação ruim do desafio. Então, proponho o seguinte. A pontuação deve ser calculada multiplicando a contagem de bytes pelo tempo de execução, para que o tempo de execução e a contagem de bytes sejam recompensados. O que você acha?
Phelype Oleinik 14/09
1
@PhelypeOleinik Não acho que seja um sistema de pontuação muito bom. Mantê-lo no golfe é uma solução melhor, mas se você estiver realmente procurando uma solução, tenho certeza de que isso pode ser modificado para ser mais eficiente.
caird coinheringaahing
@cairdcoinheringaahing Entendo que a solução mais elegante é manter como está. Mas um algoritmo que leva "dias ou até meses" para resolver uma placa de quebra-cabeça de 8x12 é de alguma forma ineficiente, você não acha? Na minha opinião, um algoritmo que resolve o problema em menos tempo deve ser recompensado, mesmo que seja um pouco mais longo.
Phelype Oleinik 15/09
3
@PhelypeOleinik A "eficiência" do código é irrelevante. Você nos desafiou a escrever um código curto, e essa é a base do seu desafio. Adicionar a velocidade na qual o programa é executado apenas complica as coisas desnecessariamente e também pode ser explorado por pontuações ridículas. Os sistemas de pontuação personalizados não costumam dar certo. Se você deseja um código curto, faça uma pergunta sobre código de golfe. Se você deseja um código rápido, faça uma pergunta sobre o código mais rápido. Tentar misturá-los não é uma boa ideia.
precisa saber é o seguinte
Na sua exec(...)sequência, há cinco novas linhas, representadas como \n5 * 2 = 10 bytes. O uso de uma sequência de aspas triplas adicionaria 4 bytes ( ...''...''...), mas removeria 5 bytes, pois poderiam ser usados ​​caracteres de nova linha reais. No total, isso poderia economizar um 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

Experimente online!

A entrada usa em =#F7LJ<>^v.vez de ═║╔╗╚╝╣╠╩╦▒para caber no conjunto de caracteres clássico .

Todos os casos de teste, exceto o último, passam em alguns segundos.

O último teste leva 47 minutos no meu computador e não gera solução.

Quando o caminho resultante usa uma porta perto de um canto, ele pode ser renderizado incorretamente (é como se a trilha bifurcava e passasse por uma porta imaginária extra), mas ainda é discernível e inequívoca.

ngn
fonte
Muito bom! Se eu perguntar, qual abordagem seu código usa para resolver? Pesquisa exaustiva ou algo mais elegante? Além disso, como eu disse, não resolvi o último quebra-cabeça manualmente. Não possui uma solução passo a passo clara e requer, mesmo ao resolver manualmente, uma adivinhação para encontrar algumas respostas. Este quebra-cabeça está incluído no jogo original, mas pode não ter uma solução, portanto, provavelmente não deve ser levado em consideração.
Phelype Oleinik
1
@PhelypeOleinik Sim, é uma pesquisa exaustiva e pouco sofisticada. A razão pela qual encontra rapidamente as soluções existentes é que ele tenta o caso mais provável primeiro (com vs sem uma certa aresta no gráfico - minha heurística é o mínimo dos graus dos dois vértices, menor é o mais provável). A razão pela qual ele tem um desempenho horrível no último caso é que ele testa todas as possibilidades de qualquer maneira e remove a recursão apenas em contradições óbvias. Parece não haver bons algoritmos de caminho hamiltoniano, mesmo para o caso especial de gráficos de grau delimitado (≤4 vizinhos).
NGN
3

JavaScript (ES6), 274 bytes

Entrada como uma cadeia de linhas múltiplas, cada linha terminada com um caractere de nova linha. As portas estão marcadas com o caractere '2'

Saída como uma sequência de múltiplas linhas com o caminho marcado pelo caractere '1', facilmente discernível.

Esta é uma pesquisa em profundidade , tentando todos os caminhos e retrocedendo quando travada. Não é nada eficiente, mas pode resolver quebra-cabeças 1 .. 6 em 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 golfe

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 do snippet de teste, há uma solução usando um DFS com alguma restrição que resolve o quebra-cabeça 7 em menos de um minuto (no meu PC). O enigma 8 não tem solução. Restrições:

  • Todas as células vazias devem ser alcançáveis ​​a partir da célula atual - o espaço vazio não deve ser dividido em duas partes
  • Deve haver uma porta acessível
  • Uma configuração de células não pode ser explorada mais de uma vez
  • Não é possível ignorar uma célula que possui apenas uma célula adjacente vazia

Teste

Cuidado, o quebra-cabeça 7 está muito além do tempo limite para execução de javascript em qualquer navegador (usando o solucionador de problemas Short e Slow)

Mostrar snippet de código

edc65
fonte