Löse diesen Alcazar für mich

39

Kürzlich habe ich ein Spiel namens Alcazar gespielt. Es ist ein Brettspiel, in dem du von einer Tür aus eintreten, alle Felder durchqueren und durch eine andere Tür austreten musst. Die einzigen Regeln sind:

  • Einmal eingeben, einmal verlassen;
  • Passiere alle Quadrate;
  • Fahren Sie nicht mehr als einmal durch ein Feld

Das Bild unten zeigt ein Beispiel für ein Alcazar-Brett und rechts das gelöste Rätsel (das ist natürlich ganz einfach):

Beispiel Alcazar Puzzle

Sie finden weitere Rätsel unter http://www.theincrediblecompany.com/try-alcazar und können das Spiel im PlayStore herunterladen (PS: Keine Werbung).

Mein Problem ist, dass ich das Spiel bis auf ein Level fast beendet habe. Ich kann einfach keinen Weg finden, es zu lösen. Die Herausforderung, die ich vorschlage, besteht darin, einen Algorithmus zu erstellen, der jedes normale 1 lösbare 2- Alcazar-Level löst .

Natürlich bitte ich niemanden, einen Bildinterpreter zu bauen, um das Bild zu lesen und das Rätsel zu lösen (oder bin ich das?). Also habe ich das obige Puzzle mit Box-Zeichen neu gezeichnet. Das Rätsel und seine Lösung wäre wie folgt:

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

In der oberen Tafel ▒befinden sich die zu füllenden Zellen.

Man kann beobachten, dass es zwischen den Zellen eine vertikale und horizontale Fuge gibt. Das liegt daran, dass ich zwischen den Zellen ein Leerzeichen einfügen musste, um die Wände hinzuzufügen. Dies bedeutet, dass die einzigen wichtigen Zellen die über, unter, links und rechts von jeder Zelle sind. Die Diagonalen konnten ohne Informationsverlust entfernt werden. In der folgenden Tabelle repräsentieren beispielsweise beide dasselbe Rätsel:

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

Dies gilt auch für die Lösungen. Das heißt, es ist nicht erforderlich, die Zellen zu verbinden:

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

Im obigen Beispiel bedeuten beide Lösungen dasselbe.

Ja, die Testfälle. Hier sind sie:

Puzzle 1

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

Puzzle 2

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

Puzzle 3

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

Rätsel 4

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

Puzzle 5

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

Puzzle 6

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

Puzzle 7

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

Puzzle 8 (Entschuldigung, ich habe wirklich keine Lösung für dieses Problem)

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

Eingang

Die Eingabe Ihres Codes kann eine beliebige Darstellung haben, sofern die folgenden Regeln eingehalten werden:

  1. Es muss eine grafische Eingabe sein. So ist es beispielsweise nicht möglich, eine Koordinatenliste zu lesen.

  2. Horizontale Wände, vertikale Wände und Türen müssen voneinander getrennt sein und aus einem sichtbaren Zeichen bestehen (keine leeren Zeichen).

  3. Die ▒können durch Leerzeichen ersetzt werden. Ich habe nur einen anderen Charakter verwendet, um sie hervorzuheben.

Ausgabe

Die Ausgabe kann auch eine beliebige Darstellung haben, sofern die folgenden Regeln eingehalten werden:

  1. Es muss eine grafische Ausgabe sein. Das heißt, man kann den Weg sehen, indem man ihn ansieht.

  2. Regel Nummer eins impliziert, dass die Pfadzeichen unterschiedlich sind. Das heißt, es werden mindestens 6 Pfadzeichen vorhanden sein. horizontal, vertikal und ecken.

  3. Damit die Antwort gültig ist, muss die Ausgabe dieselbe Karte sein wie die Eingabe (offensichtlich), wobei alle Zellen (in meiner Darstellung die ▒) ausgefüllt sind. Das Ausfüllen der Lücken zwischen den Zellen ist optional.

Wertung

Das ist Code-Golf , also gewinnt der kürzeste Code in Bytes.

1 Es gibt einige Alcazar-Level mit optionalen Zellen und Tunneln. Diese werden nicht berücksichtigt.

2 Es gibt einige Alcazar-Boards, die unmöglich sind.

code-golf ascii-art puzzle-solver Phelype Oleinik
quelle
2
Mein Programm findet keine Lösung für Puzzle 8. Sind Sie sicher, dass es lösbar ist? Vielleicht Tippfehler?
Edc65
1
@ edc65 das gleiche hier - keine Lösung für # 8
ngn

Antworten:

5

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

Bearbeiten: 55 Bytes dank @Felipe Nardi Batista gespeichert

Läuft nicht den letzten Testfall in 60 Sekunden auf TIO, sollte aber trotzdem korrekt funktionieren. Gibt eine Liste mit Koordinaten für den Pfad zurück. Etwa 400 der Bytes werden verwendet, um die Datenlisten von der E / A abzurufen.

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

Probieren Sie es online!

Halvard Hummel
quelle
@HalvardHummel Tut mir leid für die schlechte Formulierung der Herausforderung. Also schlage ich folgendes vor. Der Score wird berechnet, indem die Anzahl der Bytes mit der Laufzeit multipliziert wird, sodass sowohl die Laufzeit als auch die Anzahl der Bytes belohnt werden. Was denkst du?
Phelype Oleinik
1
@PhelypeOleinik Ich halte das nicht für ein sehr gutes Punktesystem. Es ist eine bessere Lösung, es auf Golf zu beschränken, aber wenn Sie wirklich nach einer Lösung suchen, bin ich sicher, dass dies geändert werden kann, um effizienter zu sein.
Caird Coinheringaahing
@cairdcoinheringaahing Ich verstehe, dass die eleganteste Lösung darin besteht, so zu bleiben, wie sie ist. Aber ein Algorithmus, der "Tage oder sogar Monate" benötigt, um ein 8x12-Puzzle-Brett zu lösen, ist irgendwie ineffizient, finden Sie nicht? So wie ich es sehe, sollte ein Algorithmus, der das Problem in kürzerer Zeit löst, belohnt werden, auch wenn er etwas länger ist.
Phelype Oleinik
3
@PhelypeOleinik Die "Effizienz" des Codes ist irrelevant. Sie haben uns aufgefordert, Kurzcode zu schreiben, und das ist die Grundlage für Ihre Herausforderung. Das Hinzufügen der Geschwindigkeit, mit der das Programm ausgeführt wird, macht die Sache nur unnötig kompliziert und kann auch für lächerliche Scores ausgenutzt werden. Benutzerdefinierte Bewertungssysteme funktionieren normalerweise nicht. Wenn Sie einen kurzen Code wünschen, stellen Sie eine Code-Golf-Frage. Wenn Sie schnellen Code möchten, stellen Sie eine Frage mit dem schnellsten Code. Der Versuch, sie miteinander zu mischen, ist keine gute Idee.
Text
In Ihrer exec(...)Zeichenfolge befinden sich fünf neue Zeilen, dargestellt als \n5 * 2 = 10 Byte. Die Verwendung einer Zeichenfolge in dreifachen Anführungszeichen würde 4 Bytes ( ...''...''...) hinzufügen, aber dann 5 Bytes entfernen, da tatsächliche neue Zeilenzeichen verwendet werden könnten. Insgesamt könnte dadurch ein Byte eingespart werden.
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

Probieren Sie es online!

Eingabe verwendet =#F7LJ<>^v.statt ═║╔╗╚╝╣╠╩╦▒, um in den klassischen Zeichensatz zu passen .

Alle Testfälle mit Ausnahme des letzten Durchgangs in wenigen Sekunden.

Der letzte Test dauert 47 Minuten auf meinem Computer und liefert keine Lösung.

Wenn der resultierende Pfad eine Tür in der Nähe einer Ecke verwendet, wird sie möglicherweise falsch gerendert (es ist, als ob sich die Spur gabelt und durch eine zusätzliche imaginäre Tür führt), aber sie ist immer noch erkennbar und eindeutig.

ngn
quelle
Sehr gut! Wenn ich fragen darf, welchen Ansatz verwendet Ihr Code, um zu lösen? Erschöpfende Suche oder etwas eleganteres? Außerdem habe ich, wie gesagt, das letzte Rätsel nicht von Hand gelöst. Es gibt keine klare Schritt-für-Schritt-Lösung und es ist auch beim Lösen von Hand ein Rätselraten erforderlich, um einige Antworten zu finden. Dieses Rätsel ist im Originalspiel enthalten, hat jedoch möglicherweise keine Lösung und sollte daher wahrscheinlich nicht berücksichtigt werden.
Phelype Oleinik
1
@PhelypeOleinik Ja, es ist eine ziemlich anspruchslose exhastive Suche. Der Grund dafür, dass vorhandene Lösungen schnell gefunden werden, ist, dass zuerst der wahrscheinlichere Fall geprüft wird (mit vs ohne eine bestimmte Kante im Diagramm - meine Heuristik ist das Minimum der Grade der beiden Scheitelpunkte, niedriger ist wahrscheinlicher). Der Grund, warum es im letzten Fall eine schreckliche Leistung erbringt, ist, dass es ohnehin alle Möglichkeiten testet und die Rekursion nur auf offensichtliche Widersprüche beschränkt. Es scheinen keine guten Hamilton-Pfad-Algorithmen bekannt zu sein, auch nicht für den Sonderfall von Graphen mit begrenztem Grad (≤ 4 Nachbarn).
18.
3

JavaScript (ES6), 274 Byte

Eingabe als mehrzeilige Zeichenfolge, wobei jede Zeile mit einem Zeilenumbruchzeichen abgeschlossen wird. Die Türen sind mit dem Buchstaben '2' gekennzeichnet

Ausgabe als mehrzeilige Zeichenfolge mit dem Pfad, der durch das Zeichen "1" gekennzeichnet ist, sehr leicht erkennbar.

Dies ist eine Tiefensuche , alle Wege versuchen , und wenn Backtracking stecken. Es ist überhaupt nicht effizient, kann aber Rätsel 1 .. 6 in weniger als 1 Minute lösen.

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

Weniger golfen

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

Im Test-Snippet gibt es eine Lösung, die ein DFS mit einigen Einschränkungen verwendet und das Rätsel 7 in weniger als einer Minute (auf meinem PC) löst. Puzzle 8 hat keine Lösung. Einschränkungen:

  • Alle leeren Zellen müssen von der aktuellen Zelle aus erreichbar sein - der leere Raum darf nicht in zwei Teile geteilt werden
  • Es muss eine erreichbare Tür geben
  • Eine Konfiguration von Zellen kann nicht mehrmals untersucht werden
  • Eine Zelle mit nur einer leeren benachbarten Zelle kann nicht übersprungen werden

Prüfung

Beachten Sie, dass das Zeitlimit für die Ausführung von Javascript in jedem Browser (mit dem Kurz- und Langsamlöser) bei Puzzle 7 überschritten ist.

Code-Snippet anzeigen

edc65
quelle