n * n网格上所有可能的移动

Question

因此，我必须计算网格左上角和左下角之间的所有可能路径。我的问题来自于每个广场都只能访问一次。不少于或多于。

现在我只是强迫它与递归。 7x7网格需要约30秒，但8x8需要+ 24小时（没有让它完成）。我尝试通过检查新的递归方法调用是否能够通过跟随边缘并查看它是否与自身或终点线相遇来连接到终点来解决问题。我也试着从最后一个插入的方格中“填充”网格。他们两人都工作，但他们甚至比暴力强制要慢。

我想自己发现这一点，但一些帮助将不胜感激。我会很高兴10x10网格是可以解决的。我甚至会接近这个权利（递归和检查这个递归分支是否可以在执行新的递归方法调用之前达到目标），还是应该用动态编程或其他方法来处理它？

Answer 1

我怀疑有一个封闭的公式。但动态编程将起作用。高层次的想法是一次一行地工作，记住与什么有关的东西。在一个5x5的旅游像

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

我们不妨审视前两行的路径片段，

v>>>v 
v^v<<, 

和接口，他们提出：

011--. 

顶点标志着-做没有连接外部。标记为0的顶点连接到起始方块。标记为1的顶点是路径的两端。

边缘入射到行呈现一个分区到由该行，其中每个间隔看起来像之一

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

如果非空，只是|否则边缘内部连接间隔。给定一个接口（状态）和一个行（字母），我们可以计算组合的接口（如果有效）应该是什么。

我时间不多，你不想要所有的细节，所以我只需转储我的Python 3代码即可实现此功能。

#!/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))