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

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

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

一个简单的解决方案是将其视为图形问题并使用任何标准
路径寻找算法将每个移动计算为有成本1.因此,假设我想将我的王从A8移动到H1以10个移动.我只想搜索总计10的所有路径.

我的问题是,如果还有其他更聪明有效的方法吗？
我也想知道,如果有更多的“数学”和直接找到这个数字而不是那么“算法”和“蛮力似的”？

这是一个直接的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