So, i have to calculate all possible paths between upper left corner and lower left corner of a grid. My problem comes from the fact that every square must be visited exactly once. Not less or more.
Right now i'm just brute forcing it with recursion. 7x7 grid takes ~30 seconds, but 8x8 takes +24h (didn't let it finish). I tried to solve the problem by checking if the new recursive method call was even able to connect to the finish point by following the edges and seeing if it meets with itself, or the finish line. I also tried "filling" the grid from the last inserted square. Both of them worked, but they were even slower than brute forcing.
I wanna discover this on my own, but some help would be appreciated. I would be happy with 10x10 grid being solvable. Am i even approaching this right (recursion and checking if this recursive branch can even reach the goal before doing new recursive method calls), or should i approach it with a dynamic programming or something else?
I'm skeptical that there's a closed-form formula. Dynamic programming will work, though. The high-level idea is to work row-at-a-time, remembering what's connected to what. On a 5x5 tour like
v>>>v
v^v<<
v^>>v
v^v<<
>^>>.,
we might examine the path fragments of the first two rows,
v>>>v
v^v<<,
and the interface that they present:
011--.
The vertices marked - do not connect outside. The vertex marked 0 is connected to the starting square. The vertices marked 1 are two ends of a path.
The edges incident to a row present a partition into intervals connected by edges internal to the row, where each interval looks like one of
|___| |___ ___| ___
| | | |
if nonempty and just | otherwise. Given an interface (state) and a row (letter), we can compute what the interface of the combination (if valid) should be.
I'm short on time and you don't want all of the details anyway, so let me just dump my Python 3 code implementing this.
#!/usr/bin/env python3
import collections
import itertools
if False:
def all_pairings(m, i):
assert isinstance(m, int)
assert m >= 0
assert isinstance(i, int)
assert i >= 0
if m == 0:
yield ()
else:
for k in range(m):
for p in all_pairings(k, i + 1):
for q in all_pairings(m - 1 - k, i + 1 + k):
yield (i,) + p + (i,) + q
def all_states(n):
assert isinstance(n, int)
assert n >= 0
for m in range(1, (n + 1) // 2 + 1):
for indexes in itertools.combinations(range(n), m * 2 - 1):
state = [None] * n
for k in range(m):
for p in all_pairings(k, 0):
for q in all_pairings(m - 1 - k, k + 1):
for v, i in zip(indexes, p + (k,) + q):
state[v] = i
yield tuple(state)
def connections_from_state(state):
return tuple(v for v, i in enumerate(state) if i is not None)
def all_partitions(n):
assert isinstance(n, int)
assert n >= 0
boundaries = [0, n]
for k in range(n):
for c in itertools.combinations(range(1, n), k):
boundaries[1:-1] = c
yield tuple(boundaries)
def all_letters(n):
assert isinstance(n, int)
assert n >= 0
for partition in all_partitions(n):
factors = []
for i in range(len(partition) - 1):
v = partition[i]
w = partition[i + 1] - 1
factor = [((v, False), (w, True))]
if v != w:
factor.append(((v, False), (w, False)))
factor.append(((v, True), (w, False)))
factor.append(((v, True), (w, True)))
factors.append(factor)
yield from itertools.product(*factors)
def inner_connections_from_letter(letter):
return tuple(x for ends in letter for x, outer_x in ends if not outer_x)
def outer_connections_from_letter(letter):
return tuple(x for ends in letter for x, outer_x in ends if outer_x)
def union_find(n):
return list(range(n))
def find(parent, v):
while parent[v] != v:
parent[v] = parent[parent[v]]
v = parent[v]
return v
def union(parent, v, w):
if v == w:
return True
v = find(parent, v)
w = find(parent, w)
if v < w:
parent[w] = v
return True
elif v == w:
return False
else:
parent[v] = w
return True
def transition(state, letter):
assert connections_from_state(state) == inner_connections_from_letter(letter)
n = len(state)
parent = union_find(n)
other_end = {}
for v, i in enumerate(state):
if i is not None and not union(parent, v, other_end.setdefault(i, v)):
return None
for (v, outer_v), (w, outer_w) in letter:
if not union(parent, v, w):
return None
next_state = [None] * n
label = {}
for v in outer_connections_from_letter(letter):
w = find(parent, v)
if w not in label:
label[w] = len(label)
next_state[v] = label[w]
return tuple(next_state)
def count_paths(n):
counts = collections.Counter({(0,) + (None,) * (n - 1): 1})
letters_from_inner_connections = collections.defaultdict(list)
for letter in all_letters(n):
letters_from_inner_connections[inner_connections_from_letter(letter)].append(letter)
for j in range(n):
next_counts = collections.Counter()
for state, count in counts.items():
for letter in letters_from_inner_connections[connections_from_state(state)]:
next_state = transition(state, letter)
if next_state is not None:
next_counts[next_state] += count
counts = next_counts
return counts[(None,) * (n - 1) + (0,)]
def slow_count_paths_rec(n, i, j, visited):
if len(visited) == n ** 2 and i == n - 1 and j == n - 1:
return 1
elif i < 0 or n <= i or j < 0 or n <= j or (i, j) in visited:
return 0
else:
visited.add((i, j))
total = 0
total += slow_count_paths_rec(n, i - 1, j, visited)
total += slow_count_paths_rec(n, i, j - 1, visited)
total += slow_count_paths_rec(n, i, j + 1, visited)
total += slow_count_paths_rec(n, i + 1, j, visited)
visited.remove((i, j))
return total
def slow_count_paths(n):
return slow_count_paths_rec(n, 0, 0, {(n - 1, n - 1)})
print(slow_count_paths(5))
print(count_paths(5))