algorithm - All possible moves on a n*n grid -

algorithm - All possible moves on a n*n grid -

so, have calculate possible paths between upper left corner , lower left corner of grid. problem comes fact every square must visited once. not less or more.

right i'm brute forcing recursion. 7x7 grid takes ~30 seconds, 8x8 takes +24h (didn't allow finish). tried solve problem checking if new recursive method phone call able connect finish point next edges , seeing if meets itself, or finish line. tried "filling" grid lastly inserted square. both of them worked, slower brute forcing.

i wanna find on own, help appreciated. happy 10x10 grid beingness solvable. approaching right (recursion , checking if recursive branch can reach goal before doing new recursive method calls), or should approach dynamic programming or else?

i'm skeptical there's closed-form formula. dynamic programming work, though. high-level thought work row-at-a-time, remembering what's connected what. on 5x5 tour like

v>>>v v^v<< v^>>v v^v<< >^>>.,

we might examine path fragments of first 2 rows,

v>>>v v^v<<,

and interface present:

011--.

the vertices marked - not connect outside. vertex marked 0 connected starting square. vertices marked 1 2 ends of path.

the edges incident row nowadays partition intervals connected edges internal row, each interval looks 1 of

|___| |___ ___| ___ | | | |

if nonempty , | otherwise. given interface (state) , row (letter), can compute interface of combination (if valid) should be.

i'm short on time , don't want of details anyway, allow me dump 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 >= 0 if m == 0: yield () else: k in range(m): p in all_pairings(k, + 1): q in all_pairings(m - 1 - k, + 1 + k): yield (i,) + p + (i,) + q def all_states(n): assert isinstance(n, int) assert n >= 0 m in range(1, (n + 1) // 2 + 1): indexes in itertools.combinations(range(n), m * 2 - 1): state = [none] * n k in range(m): p in all_pairings(k, 0): q in all_pairings(m - 1 - k, k + 1): v, in zip(indexes, p + (k,) + q): state[v] = yield tuple(state) def connections_from_state(state): homecoming tuple(v v, in enumerate(state) if not none) def all_partitions(n): assert isinstance(n, int) assert n >= 0 boundaries = [0, n] k in range(n): 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 partition in all_partitions(n): factors = [] 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 itertools.product(*factors) def inner_connections_from_letter(letter): homecoming tuple(x ends in letter x, outer_x in ends if not outer_x) def outer_connections_from_letter(letter): homecoming tuple(x ends in letter x, outer_x in ends if outer_x) def union_find(n): homecoming list(range(n)) def find(parent, v): while parent[v] != v: parent[v] = parent[parent[v]] v = parent[v] homecoming v def union(parent, v, w): if v == w: homecoming true v = find(parent, v) w = find(parent, w) if v < w: parent[w] = v homecoming true elif v == w: homecoming false else: parent[v] = w homecoming true def transition(state, letter): assert connections_from_state(state) == inner_connections_from_letter(letter) n = len(state) parent = union_find(n) other_end = {} v, in enumerate(state): if not none , not union(parent, v, other_end.setdefault(i, v)): homecoming none (v, outer_v), (w, outer_w) in letter: if not union(parent, v, w): homecoming none next_state = [none] * n label = {} 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] homecoming tuple(next_state) def count_paths(n): counts = collections.counter({(0,) + (none,) * (n - 1): 1}) letters_from_inner_connections = collections.defaultdict(list) letter in all_letters(n): letters_from_inner_connections[inner_connections_from_letter(letter)].append(letter) j in range(n): next_counts = collections.counter() state, count in counts.items(): letter in letters_from_inner_connections[connections_from_state(state)]: next_state = transition(state, letter) if next_state not none: next_counts[next_state] += count counts = next_counts homecoming counts[(none,) * (n - 1) + (0,)] def slow_count_paths_rec(n, i, j, visited): if len(visited) == n ** 2 , == n - 1 , j == n - 1: homecoming 1 elif < 0 or n <= or j < 0 or n <= j or (i, j) in visited: homecoming 0 else: visited.add((i, j)) total = 0 total += slow_count_paths_rec(n, - 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, + 1, j, visited) visited.remove((i, j)) homecoming total def slow_count_paths(n): homecoming slow_count_paths_rec(n, 0, 0, {(n - 1, n - 1)}) print(slow_count_paths(5)) print(count_paths(5))

algorithm path-finding