棋类图算法：k步内可行路径

Question

我正在尝试解决一个与国际象棋有关的算法问题。

假设我有一个国王在A8，想将其移动到H1（只使用允许的移动方式）。我该如何找出在恰好给定的k次移动中有多少种可能性（路径）？

例如：如果我想用15步将国王从A8移动到H1，那么有多少个路径/可能性？

一个简单的解决方案是将其视为图形问题，并使用任何标准的路径查找算法，将每次移动计为成本1。因此，假设我想在10步内将我的国王从A8移动到H1。我只需要搜索所有总和为10的路径。

我的问题是，是否有其他更聪明和高效的方法来解决这个问题？我还在想，是否有更“数学”和直接的方法来找到这个数字，而不是像“算法”和“蛮力”的方法？

- Proghero

---

在这里，我们需要非常小心整数溢出的问题。15 次移动将会导致 32 位的溢出，而 25 次移动将会导致 64 位的溢出。 - n. m.

Answer 1

您可以使用邻接矩阵。如果将这样的矩阵乘以自身，则可以得到从一个点到另一个点的路径数量。例如：

图形：完整的K3图：A<->B<->C<->A

矩阵:

[0 ; 1 ; 1]
[1 ; 0 ; 1]
[1 ; 1 ; 0]

长度为2的路径：M * M

。

[2 ; 1 ; 1]
[1 ; 2 ; 1]
[1 ; 1 ; 2]

长度为3将是M * M * M。

[2 ; 3 ; 3]
[3 ; 2 ; 3]
[3 ; 3 ; 2]

- Slomo

---

这种技术可能存在一个问题（我认为在教科书中看到过），对于大型图形，所需的内存将变为O（（行*列）^ 2），因此每次迭代的时间也会增加。但是，如果您有一个良好编写的稀疏矩阵库（也许是numpy？），那么它应该可以很好地推广。 - ninjagecko

你说得对。它不仅可以计算从A到B的路径，还可以计算从每个起点到每个终点在N步内的所有可能性。然而，在普通的8x8棋盘上，这应该不是一个主要问题。此外，它可以很好地并行化。 - Slomo

我认为没有办法绕过从起点到每个终点在N步中计算所有可能性的问题。（如果你在谈论饱和问题，那似乎是相当小的。）我只是在提到国际象棋棋盘不是一个完全图的问题，因此有着极大数量的0项。 - ninjagecko

Answer 2

这是一个简单的O(N^3)动态规划问题。

只需按以下方式分配一个三维数组：

令Z[x][y][k]为从棋盘上的位置(x,y)到达目的地所需的k步数。

基本情况如下：

foreach x in 0 to 7,
   foreach y in 0 to 7,
       Z[x][y][0] = 0 // forall x,y: 0 ways to reach H1 from
                      // anywhere else with 0 steps

Z[7][7][0] = 1 // 1 way to reach H1 from H1 with 0 steps

递归情况为：

foreach k in 1 to K,
   foreach x in 0 to 7,
      foreach y in 0 to 7,
          Z[x][y][k+1] = Z[x-1][y][k]
              + Z[x+1][y][k]
              + Z[x][y-1][k]
              + Z[x][y+1][k]
              + ...; // only include positions in
                     // the summation that are on the board
                     // and that a king can make

你的答案如下：

return Z[0][0][K]; // number of ways to reach H1(7,7) from A8(0,0) with K moves

（有一种更快的方法可以在O(n^2)内完成，它将移动分解为两组水平和垂直移动，然后将它们组合起来，并乘以交错数量。）

请参阅相关问题和答案：在方格中行走M步的方法数。

- Andrew Tomazos

---

小问题：我认为最外层的迭代应该是“foreach k in 0 to K-1”。 - kavinyao

Answer 3

.......E <-end
........
........
........
........
........
........
S....... <-start

不幸的是，您不能使用“任何标准路径查找算法”，因为您的路径可能不是最短路径。您必须专门使用考虑所有路径的朴素搜索（例如深度优先或广度优先搜索）。

然而，由于您不关心如何到达一个图块，您可以使用一种称为“动态规划”的技术。对于每个位置（i，j），到达该位置的方式数（称为ways_i，j（n））为：

ways_i，j（n）= ways_i-1，j（n-1）+ ways_i+1，j（n-1）+ ways_i，j-1（n-1）+ ways_i，j+1（n-1）+ ways_i+1，j+1（n-1）+ ways_i-1，j+1（n-1）+ ways_i+1，j-1（n-1）+ ways_i-1，j-1（n-1）

也就是说，国王可以在1步内从任何相邻的格子移动：

ways_i,j(n) = sum_{neighbors(i,j)}(ways_neighbor(n-1))

因此，例如在Python中：

SIZE = 8

cache = {}
def ways(pos, n):
    r,c = pos  # row,column
    if not (0<=r<SIZE and 0<=c<SIZE):
        # off edge of board: no ways to get here
        return 0
    elif n==0:
        # starting position: only one way to get here
        return 1 if (r,c)==(0,0) else 0
    else:
        args = (pos,n)
        if not args in cache:
            cache[args] = ways((r-1,c), n-1) + ways((r+1,c), n-1) + ways((r,c-1), n-1) + ways((r,c+1), n-1) + ways((r-1,c-1), n-1) + ways((r+1,c-1), n-1) + ways((r+1,c-1), n-1) + ways((r+1,c+1), n-1)
        return cache[args]

演示：

>>> ways((7,7), 15)
1074445298

上述技术被称为记忆化，相比动态规划更容易编写，因为您不需要真正考虑执行操作的顺序。随着我们执行一系列越来越大的查询，您可以看到缓存增长：

>>> cache
{}
>>> ways((1,0), 1)
1
>>> cache
{((1, 0), 1): 1}
>>> ways((1,1), 2)
2
>>> cache
{((0, 1), 1): 1, ((1, 2), 1): 0, ((1, 0), 1): 1, ((0, 0), 1): 0, ((2, 0), 1): 0, ((2, 1), 1): 0, ((1, 1), 2): 2, ((2, 2), 1): 0}
>>> ways((2,1), 3)
5
>>> cache
{((1, 2), 1): 0, ((2, 3), 1): 0, ((2, 0), 2): 1, ((1, 1), 1): 1, ((3, 1), 1): 0, ((4, 0), 1): 0, ((1, 0), 1): 1, ((3, 0), 1): 0, ((0, 0), 1): 0, ((2, 0), 1): 0, ((2, 1), 1): 0, ((4, 1), 1): 0, ((2, 2), 2): 1, ((3, 3), 1): 0, ((0, 1), 1): 1, ((3, 0), 2): 0, ((3, 2), 2): 0, ((3, 2), 1): 0, ((1, 0), 2): 1, ((4, 2), 1): 0, ((4, 3), 1): 0, ((3, 1), 2): 0, ((1, 1), 2): 2, ((2, 2), 1): 0, ((2, 1), 3): 5}

在Python中，还可以使用@cached或@memoized装饰器来避免编写整个代码块在最后的else:语句中。其他编程语言也有其他自动执行记忆化的方法。

以上是一种自顶向下的方法。它有时会产生非常大的堆栈（您的堆栈将随着n的增长而增长）。如果您想要超级高效地避免不必要的工作，可以采用自底向上的方法，模拟国王可能出现的所有位置，1步、2步、3步等：

SIZE = 8
def ways(n):
    grid = [[0 for row in range(8)] for col in range(8)]
    grid[0][0] = 1

    def inGrid(r,c):            
        return all(0<=coord<SIZE for coord in (r,c))
    def adjacentSum(pos, grid):
        r,c = pos
        total = 0
        for neighbor in [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)]:
            delta_r,delta_c = neighbor
            (r2,c2) = (r+delta_r,c+delta_c)
            if inGrid(r2,c2):
                total += grid[r2][c2]
        return total

    for _ in range(n):
        grid = [[adjacentSum((r,c), grid) for r in range(8)] for c in range(8)]
        # careful: grid must be replaced atomically, not element-by-element

    from pprint import pprint
    pprint(grid)
    return grid

演示：

>>> ways(0)
[[1, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]]

>>> ways(1)
[[0, 1, 0, 0, 0, 0, 0, 0],
 [1, 1, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]]

>>> ways(2)
[[3, 2, 2, 0, 0, 0, 0, 0],
 [2, 2, 2, 0, 0, 0, 0, 0],
 [2, 2, 1, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]]

>>> ways(3)
[[6,  11, 6, 4, 0, 0, 0, 0],
 [11, 16, 9, 5, 0, 0, 0, 0],
 [6,  9,  6, 3, 0, 0, 0, 0],
 [4,  5,  3, 1, 0, 0, 0, 0],
 [0,  0,  0, 0, 0, 0, 0, 0],
 [0,  0,  0, 0, 0, 0, 0, 0],
 [0,  0,  0, 0, 0, 0, 0, 0],
 [0,  0,  0, 0, 0, 0, 0, 0]]

>>> ways(4)
[[38, 48, 45, 20, 9,  0, 0, 0],
 [48, 64, 60, 28, 12, 0, 0, 0],
 [45, 60, 51, 24, 9,  0, 0, 0],
 [20, 28, 24, 12, 4,  0, 0, 0],
 [9,  12, 9,  4,  1,  0, 0, 0],
 [0,  0,  0,  0,  0,  0, 0, 0],
 [0,  0,  0,  0,  0,  0, 0, 0],
 [0,  0,  0,  0,  0,  0, 0, 0]]

- ninjagecko

---

国王的走法不是这样的。 - n. m.

@n.m.：哦，糟糕...已修复。幸运的是这只是一道作业题，如何将问题应用到国王的案例中仍然很明显。 - ninjagecko