algorithm - 涉及国际象棋的图算法 : possible paths in k moves

Question

我正在尝试解决涉及国际象棋的算法问题。

假设我在 A8 中有一个国王，并且想将其移动到 H1(仅允许移动)。 我怎样才能找出有多少种可能性(路径)可以准确地进行任何给定的 k 步移动？ (例如，如果我想用 15 步将国王从 A8 移动到 H1，有多少种路径/可能性？)

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

我的问题是，是否还有其他更聪明、更有效的方法来做到这一点？ 我也想知道，是否可以有更“数学”和更直接的方法来找到这个数字，而不是那么“算法”和“类似蛮力”？

Answer 1

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

简单地分配一个 3D 数组如下:

令 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) 中有一种更快的方法可以将移动分解为两组水平和垂直移动，然后将它们组合并乘以交错次数。)

查看此相关问答:No of ways to walk M steps in a grid