Anzahl gültiger Labyrinthe

12

WxHWie viele mögliche Labyrinthe gibt es in einem vorgegebenen Raster?

Dinge, die Sie über das Labyrinth wissen:

  1. Das Raster ist genau Hquadrathoch und Wquadratweit.
  2. Es gibt drei Arten von Quadraten: Start, Ziel und Leer. Ihr Labyrinth muss genau 1 Start und 1 Ziel enthalten, und alle verbleibenden Felder sind leer.
  3. Das gesamte Labyrinth ist von Mauern umgeben.
  4. Wände können an der Kante zwischen zwei beliebigen Feldern vorhanden sein, es sei denn, dies verstößt gegen die folgende Regel:
  5. Es muss einen Pfad vom Startfeld zum Zielfeld geben.

Aus diesem Grund müssen Sie bei zwei gegebenen Zahlen Wund Heine einzelne Zahl zurückgeben, die die Anzahl der möglichen Quadrat- / Wandkonfigurationen darstellt. Das ist Ihnen garantiertW*H > 1

Zum Beispiel hat das 2x2Labyrinth genau 100verschiedene mögliche Konfigurationen.

Dies ist ein Code-Golf, also gewinnt die kürzeste Antwort!

code-golf maze code-golf string whitespace code-golf arithmetic code-golf pyth code-golf game code-golf string code-challenge code-challenge ascii-art compression king-of-the-hill c c++ java code-challenge math optimization code-challenge math code-golf kolmogorov-complexity code-golf string Nathan Merrill
quelle
Gibt es Einschränkungen hinsichtlich Größe und / oder Laufzeit? Ich gehe davon aus, dass die meisten Lösungen eine exponentielle Laufzeit haben werden, es sei denn, jemand findet einen Algorithmus, der die Zählung effizient berechnet (was schwierig aussieht). Das bedeutet, dass sie auch bei moderaten Größen implodieren.
Reto Koradi
@RetoKoradi nein, keine Laufzeitbeschränkungen. Ich bin nicht sicher, ob Einschränkungen das Problem unmöglich machen würden oder nicht.
Nathan Merrill

Antworten:

3

Python 2, 329 310 Bytes

from itertools import*
w,h=input()
R=range(w*h)
p=product
n=0
Z=[(x,y)for x,y in p(R,R)if abs(x%w-y%w)+abs(x/w-y/w)<2]
for s,f,W in p(R,R,p(*[((),z)for z in Z if z[0]<z[1]])):
 V={s};C=[s];v=0
 while C:
  c=C.pop();v|=c==f!=s;V|={c}
  for o,q in Z:C+=(c==o)*len({q,(o,q),(q,o)}-(V|set(W)))/3*[q] 
 n+=v
print n

Dies ist die Golf-Version (und viel ineffizienter) des Programms, das ich verwendet habe, als ich das Problem mit @ Nathan besprochen habe. Ich kann ein paar Bytes sparen, indem ich einige Leerzeichen durch Tabulatoren ersetze, aber ich werde das für später speichern.

Der Algorithmus generiert einfach jedes Labyrinth und füllt es dann von Anfang an, um zu sehen, ob wir irgendwann das Ziel erreichen oder nicht.

Sp3000
quelle