Nombre de labyrinthes valides

12

Compte tenu d'une WxHgrille, combien y a-t-il de labyrinthes possibles?

Ce que vous savez sur le labyrinthe:

  1. La grille a exactement des Hcarrés de haut et des Wcarrés de large.
  2. Il existe trois types de carrés: Début, Fin et Vide. Votre labyrinthe doit contenir exactement 1 début et 1 fin, et tous les carrés restants sont vides.
  3. Il y a des murs qui entourent tout le labyrinthe.
  4. Les murs peuvent exister sur le bord entre deux carrés quelconques, sauf s'il enfreint la règle ci-dessous:
  5. Il doit exister un chemin entre le carré de départ et le carré d'arrivée.

Par conséquent, étant donné deux nombres, Wet H, vous devez renvoyer un seul nombre représentant le nombre de configurations carré / mur possibles. Vous avez la garantie queW*H > 1

Par exemple, le 2x2labyrinthe a exactement 100différentes configurations possibles.

Ceci est un code-golf, donc la réponse la plus courte l'emporte!

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
la source
Existe-t-il des contraintes de taille et / ou d'exécution? À moins que quelqu'un ne trouve un algorithme capable de calculer le nombre efficacement (ce qui semble difficile), je m'attends à ce que la plupart des solutions aient un temps d'exécution exponentiel. Cela signifie qu'ils vont imploser à des tailles même modérées.
Reto Koradi
@RetoKoradi non, pas de contraintes d'exécution. Je ne sais pas si des contraintes rendraient le problème impossible ou non.
Nathan Merrill

Réponses:

3

Python 2, 329 310 octets

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

Ceci est la version golfée (et beaucoup plus inefficace) du programme que j'utilisais en discutant du problème avec @Nathan. Je peux enregistrer quelques octets en remplaçant certains retraits d'espace par des tabulations, mais je le garderai pour plus tard.

L'algorithme consiste simplement à générer chaque labyrinthe, puis à remplir le remplissage dès le début, pour voir si nous passons l'arrivée à un moment donné ou non.

Sp3000
la source