36. [ 20 ] An n ⇥ m maze is an n ⇥ m grid in which each cell is one of two things: a wall, or a blank. A maze is solvable if there exists a sequence of adjacent blank cells from the top left cell to the bottom right cell going through no walls. (In particular, the top left and bottom right cells must both be blank.) Let N be the number of solvable 5 ⇥ 5 mazes. Estimate N . 2 N E An estimate of E > 0 earns b 20 min , c points. E N Proposed by: John Michael Wu Answer: 1225194 The following code solves the problem in Python 3.

dfs that returns all paths with no adjacent vertices other than those consecutive in the path

def dfs(graph,start,end,path): if start==end: return [path] paths=[] for child in graph[start]: skip=False if child in path: continue for vert in graph[child]: if vert in path[:-1]: skip=True break if not skip: paths=paths+dfs(graph,child,end,path[:]+[child]) return paths

construct graph representing 5x5 grid

graph={} for a in range(5): for b in range(5): graph[(a,b)]=[] for a in range(4): for b in range(5): graph[(a,b)].append((a+1,b));graph[(a+1,b)].append((a,b)) graph[(b,a)].append((b,a+1));graph[(b,a+1)].append((b,a)) paths=dfs(graph,(0,0),(4,4),[(0,0)]) paths.sort(key=len) intpaths=[0]*len(paths)

convert paths to 25-bit binary integers

for i in range(len(paths)): for j in paths[i]: intpaths[i]+=2**(5j[0]+j[1]) mazes=0 for j in range(2**23): k=2j

disregard cases that are common and never valid

if k&8912896==8912896 or k&34==34 or k&4472832==4472832 or k&1092==1092: continue for path in intpaths:

cehck if case has empty spaces along whole path

if path&k==0: mazes+=1 break print(mazes) Alternatively, the following code solves the problem in Java SE 8. import java.util.*; public class guts36 { static int M = 5; static int N = 5; static long[] pow2 = new long[M * N]; static int[][] dir = new int[][] {new int[] {0, 1}, new int[] {1, 0}, new int[] {0, -1}, new int[] public static void main(String[] args) { pow2[0] = 1; for (int i = 1; i < pow2.length; i++) { pow2[i] = pow2[i - 1] * 2; } boolean[][] grid = new boolean[M][N]; grid[0][0] = true; grid[M - 1][N - 1] = true; int ans = 0; for (long c = 0; c < pow2[M * N - 2]; c++) { long d = c; for (int b = 0; b < M * N - 2; b++) { int i = (b + 1) / N; int j = (b + 1) % N; grid[i][j] = ((d & 1) > 0); d >>= 1; } if (check(grid)) { ans++; } } System.out.println("answer: " + ans); } static int[] add(int[] a, int[] b) { return new int[] {a[0] + b[0], a[1] + b[1]}; } static boolean get(boolean[][] g, int[] a) { return g[a[0]][a[1]]; } static void set(boolean[][] g, int[] a, boolean v) { g[a[0]][a[1]] = v; } static boolean valid(int[] a) { return (a[0] >= 0) && (a[1] >= 0) && (a[0] < M) && (a[1] < N); } static boolean check(boolean[][] grid) { Stack<int[]> q = new Stack<int[]>(); q.add(new int[] {0, 0}); boolean[][] reached = new boolean[M][N]; reached[0][0] = true; while (!q.isEmpty()) { int[] a = q.pop(); for (int[] d: dir) { int[] b = add(a, d); if (valid(b) && get(grid, b) && !get(reached, b)) { if (b[0] == M - 1 && b[1] == N - 1) { return true; } set(reached, b, true); q.add(b); } } } return false; } }