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))