Résoudre cet Alcazar pour moi

39

Récemment, j'ai joué à un jeu appelé Alcazar. Il s’agit d’un jeu de société où l’objectif est d’entrer par une porte, de passer par toutes les places et de sortir par une autre porte. Les seules règles sont:

  • Entrez une fois, laissez une fois;
  • Traverser toutes les places;
  • Ne pas traverser une case plus d'une fois

L'image ci-dessous montre un exemple de carte Alcazar et, à sa droite, le puzzle résolu (bien sûr, c'est une tâche facile):

Exemple de puzzle alcazar

Vous pouvez trouver plus de puzzles sur http://www.theincrediblecompany.com/try-alcazar et télécharger le jeu sur PlayStore (PS: ce n'est pas une publicité).

Mon problème est que j'ai presque fini le jeu, sauf pour un niveau. Je ne peux tout simplement pas trouver un moyen de le résoudre. Le défi que je propose est donc de: créer un algorithme qui résout n’importe quel niveau d’alcazar résolu 1 normal 2 .

Bien sûr, je ne demande à personne de créer un interpréteur d'image pour lire l'image et résoudre le puzzle (ou suis-je?). J'ai donc redessiné le puzzle ci-dessus en utilisant des caractères de dessin de boîtes. Le puzzle et sa solution ressembleraient à ceci:

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

Dans le tableau ci-dessus, ▒sont les cellules à remplir.

On peut observer qu'il y a un gab vertical et horizontal entre les cellules. C'est parce que j'ai dû insérer un espace entre les cellules pour ajouter les murs. Cela signifie que les seules cellules importantes sont celles situées en haut, en bas, à gauche et à droite de chaque cellule. Les diagonales pourraient être supprimées sans perte d'information. Par exemple, dans le tableau ci-dessous, les deux représentent le même casse-tête:

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

Ceci est également valable pour les solutions. C'est-à-dire qu'il n'est pas nécessaire de connecter les cellules:

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

Dans l'exemple ci-dessus, les deux solutions ont la même signification.

Oui, les cas de test. Les voici:

Puzzle 1

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

Puzzle 2

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

Puzzle 3

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

puzzle 4

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

Puzzle 5

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

Puzzle 6

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

Puzzle 7

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

Puzzle 8 (Désolé, je n'ai vraiment pas la solution à celui-ci)

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

Contribution

Toute entrée de votre code peut avoir n'importe quelle représentation pourvu qu'elle suive ces règles:

  1. Ce doit être une entrée graphique. Il n'est donc pas possible de lire une liste de coordonnées, par exemple.

  2. Les murs horizontaux, les murs verticaux et les portes doivent être distincts et doivent comporter un caractère visible (aucun caractère vierge).

  3. Le ▒peut être remplacé par des blancs. Je viens d'utiliser un caractère différent pour les mettre en valeur.

Sortie

La sortie peut aussi avoir n'importe quelle représentation pourvu qu'elle suive ces règles:

  1. Ce doit être une sortie graphique. C'est-à-dire que l'on peut voir le chemin en le regardant.

  2. La règle numéro un implique que les caractères du chemin soient différents. C'est-à-dire qu'il y aura au moins 6 caractères de chemin; horizontal, vertical et coins.

  3. Pour que la réponse soit valide, la sortie doit être la même carte que l'entrée (évidemment) avec toutes les cellules (dans ma représentation, la ▒) remplies. Le remplissage des espaces entre les cellules est facultatif.

Notation

C'est le code-golf , donc le code le plus court en octets gagne.

1 Certains niveaux d’Alcazar comportent des cellules et des tunnels en option. Ceux-ci ne seront pas considérés.

2 Il y a des cartes de l'Alcazar qui sont impossibles.

code-golf ascii-art puzzle-solver Phelype Oleinik
la source
2
Mon programme ne trouve pas de solution pour puzzle 8. Êtes-vous sûr que le problème est résolu? Peut-être une faute de frappe?
Edc65
1
@ edc65 idem ici - pas de solution pour # 8
ngn le

Réponses:

5

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

Edit: 55 octets sauvegardés grâce à @Felipe Nardi Batista

N'exécute pas le dernier test en 60 secondes sur TIO, mais devrait néanmoins fonctionner correctement. Retourne une liste de coordonnées pour le chemin. Quelque 400 octets sont utilisés pour obtenir les listes de données à partir des 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))

Essayez-le en ligne!

Halvard Hummel
la source
@HalvardHummel Eh bien, désolé pour la mauvaise formulation du défi. Je propose donc ce qui suit. Le score doit être calculé en multipliant le nombre d'octets par le temps d'exécution. Ainsi, le temps d'exécution et le nombre d'octets seront récompensés. Qu'est-ce que tu penses?
Phelype Oleinik
1
@PhelypeOleinik Je ne pense pas que ce soit un très bon système de notation. Rester dans le golf mixte est une meilleure solution, mais si vous cherchez vraiment une solution, je suis sûr que cela peut être modifié pour être plus efficace.
Caird coinheringaahing
@cairdcoinheringaahing Je comprends que la solution la plus élégante est de rester en l'état. Mais un algorithme qui prend "des jours, voire des mois" pour résoudre un tableau de casse-tête 8x12 est en quelque sorte inefficace, vous ne pensez pas? À mon avis, un algorithme qui résout le problème en moins de temps devrait être récompensé, même s'il est un peu plus long.
Phelype Oleinik
3
@PhelypeOleinik L'efficacité du code n'est pas pertinente. Vous nous avez mis au défi d’écrire un code court, et c’est la base de votre défi. Ajouter la vitesse à laquelle le programme s'exécute ne fait que compliquer les choses inutilement et peut également être exploité pour des scores ridicules. Les systèmes de notation personnalisés ne tendent pas à s'arranger. Si vous voulez un code court, posez une question code-golf. Si vous voulez un code rapide, posez la question la plus rapide. Essayer de les mélanger n'est pas une bonne idée.
LyricLy
Dans votre exec(...)chaîne, il y a cinq nouvelles lignes, représentées par \n5 * 2 = 10 octets. L'utilisation d'une chaîne à trois guillemets ajouterait 4 octets ( ...''...''...), mais supprimerait 5 octets, car les caractères de nouvelle ligne réels pourraient être utilisés. Au total, cela pourrait économiser un octet.
Jonathan Frech
5

APL (Dyalog Classic) , 319 octets

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

Essayez-le en ligne!

L'entrée utilise =#F7LJ<>^v.au lieu de ═║╔╗╚╝╣╠╩╦▒afin de s'adapter au jeu de caractères classique .

Tous les cas de test, à l'exception du dernier, passent en quelques secondes.

Le dernier test dure 47 minutes sur mon ordinateur et ne donne aucune solution.

Lorsque le chemin résultant utilise une porte proche d'un coin, il se peut que le rendu soit incorrect (c'est comme si le sentier bifurquait et passait à travers une porte imaginaire supplémentaire), mais cela reste discernable et sans ambiguïté.

ngn
la source
Très bien! Si je puis me permettre, quelle approche votre code utilise-t-il pour résoudre? Recherche exhaustive ou quelque chose de plus élégant? En outre, comme je l'ai dit, je n'ai pas résolu le dernier casse-tête à la main. Il n'a pas de solution claire étape par étape et nécessite, même en cas de résolution manuelle, une approximation pour trouver des réponses. Ce casse-tête est inclus dans le jeu d'origine, mais il peut ne pas avoir de solution, donc ne devrait probablement pas être pris en compte.
Phelype Oleinik
1
@PhelypeOleinik Oui, il s'agit d'une recherche d'exécutivité peu sophistiquée. La raison pour laquelle il trouve rapidement les solutions existantes est qu’il essaie d’abord le cas le plus probable (avec vs sans une certaine arête dans le graphique - mon heuristique correspond au minimum des degrés des deux sommets, le plus bas est le plus probable). La raison pour laquelle il fonctionne horriblement dans le dernier cas est qu'il teste de toute façon toutes les possibilités et élimine la récursivité uniquement sur des contradictions évidentes. Il ne semble pas que l'on connaisse de bons algorithmes de chemin hamiltonien, même dans le cas particulier des graphes à degré lié (≤4 voisins).
ngn
3

JavaScript (ES6), 274 octets

Entrée sous forme de chaîne multiligne, chaque ligne se terminant par un caractère de nouvelle ligne. Les portes sont marquées avec le caractère '2'

Sortie en tant que chaîne multiligne avec le chemin marqué par le caractère '1', très facilement discernable.

Il s’agit d’une recherche approfondie en premier lieu , qui tente tous les chemins et le backtraking en cas de blocage. Ce n'est pas efficace du tout, mais peut résoudre les énigmes 1 .. 6 en moins de 1 minute.

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

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

À l'intérieur de l'extrait de test, il existe une solution utilisant un système DFS avec une contrainte qui résout l'énigme 7 en moins d'une minute (sur mon PC). Puzzle 8 n'a pas de solution. Contraintes:

  • Toutes les cellules vides doivent être accessibles à partir de la cellule en cours - l'espace vide ne doit pas être divisé en deux parties
  • Il doit y avoir une porte accessible
  • Une configuration de cellules ne peut pas être explorée plus d'une fois
  • Impossible de sauter une cellule qui n'a qu'une seule cellule vide adjacente

Tester

Attention, puzzle 7 dépasse de beaucoup le délai d'attente de l'exécution de javascript dans tous les navigateurs (à l'aide des solutions courtes et lentes)

Afficher l'extrait de code

edc65
la source