12
\$\begingroup\$

Given a WxH grid, how many possible mazes are there?

Things you know about the maze:

  1. The grid is exactly H squares high and W squares wide.
  2. There are three types of squares: Start, Finish, and Empty. Your maze must contain exactly 1 Start and 1 Finish, and all remaining squares are Empty.
  3. There are walls surrounding the entire maze.
  4. Walls can exist on the edge between any two squares, unless it breaks the below rule:
  5. There must exist a path from the Start square to the Finish square.

Therefore, given two numbers, W and H, you must return a single number representing the number of possible square/wall configurations. You are guaranteed that W*H > 1

For example, the 2x2 maze has exactly 100 different possible configurations.

This is a so the shortest answer wins!

\$\endgroup\$
  • \$\begingroup\$ Are there any constraints on size and/or runtime? Unless somebody finds an algorithm that can calculate the count efficiently (which looks tough), I expect that most solutions will have exponential runtime. Meaning, that they will implode at even moderate sizes. \$\endgroup\$ – Reto Koradi Jul 16 '15 at 20:41
  • \$\begingroup\$ @RetoKoradi no, no runtime constraints. I'm not sure if constraints would make the problem impossible or not. \$\endgroup\$ – Nathan Merrill Jul 16 '15 at 20:56
3
\$\begingroup\$

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

This is the golfed (and much more inefficient) version of the program I was using while discussing the problem with @Nathan. I can save a few bytes by replacing some space indents with tabs, but I'll save that for later.

The algorithm is simply generate every maze, then flood fill from the start, seeing if we pass the finish at some point or not.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.