mazes.py

# count 4x4 mazes (spanning trees) using Kirchoff's theorem

import numpy as np

# Vertices:
#  0  1  2  3
#  4  5  6  7
#  8  9 10 11
# 12 13 14 15

Q = [[0 for j in range(16)] for i in range(16)]

def edge(i, j) :
    Q[i][i] += 1
    Q[j][j] += 1
    Q[i][j] -= 1
    Q[j][i] -= 1

# add left-to-right edges
for i in range(4) : # rows
    for j in range(3) :
        edge(i * 4 + j, i * 4 + j + 1)
# add up-down edges
for i in range(4) : # columns
    for j in range(3) :
        edge(j * 4 + i, (j + 1) * 4 + i)

# drop first row and first column
Qstar = [[Q[i][j] for j in range(1,16)] for i in range(1,16)]

print np.linalg.det(Qstar), "mazes"