涉及国际象棋的图算法:k移动中的可能路径

Question

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

假设我在A8中有一个国王,并希望将其移至H1(仅允许移动).我怎样才能找出完成任何给定k移动的可能性(路径)的数量？(例如,如果我想用15次动作将国王从A8移动到H1,会有多少路径/可能性？)

一个简单的解决方案是将其视为图形问题,并使用任何标准路径查找算法将每个移动计算为成本1.因此,假设我想要将我的王从A8移动到H1以10个移动.我只想搜索总计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) 中完成此操作，即将移动分解为两组水平和垂直移动，然后将它们组合并乘以交错数。）

请参阅此相关问题和答案：没有方法在网格中行走 M 步