Problem:
An maze is an 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 be the number of solvable mazes. Estimate .
An estimate of earns points.
Proposed by: John Michael Wu
Solution:
```python
# 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*:
intpaths* += 2 ** (5 * j[0] + j[1])
mazes = 0
for j in range(2 ** 23):
k = 2 * j
# 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:
# check 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.
```java
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[] {-1, 0}};
public static void main(String[] args) {
pow2[0] = 1;
for (int i = 1; i < pow2.length; i++) {
pow2* = 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*[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;
}
}
```