骑士之旅- 给定 n 步，骑士在 n 步中有多少种选择可以从 (1,1) 移动到 (8,8)？

Question

我一直在努力提高我在 C 中的递归技能，并且遇到了这个问题。我试图解决它，但代码似乎无法正常工作。例如，骑士有 108 个选项可以在 6 次移动中从 (1,1) 移动到 (8,8)，而在我的代码中结果完全不同。问题是在 8x8 棋盘中，有多少种方法可以将马从 (1,1) 移动到 (8,8) n 步（n 由用户给出）。这是我的代码：

#include <stdio.h>
#define SIZE 8
//x,y coordinates of the knight.
int knightsTour(int x, int y, int num);
void main() {
int n;
int result;
    do {
        scanf(" %d", &n);
        result = knightsTour(1,1,n);
        printf("%d\n", result);
    } while (n > 0);
}
int knightsTour(int x,int y,int num) {
int result = 0;
int i, j;
if (num == 0) {
    return 0;
}
if (((x > 8) || (y > 8))||((x == 8) && (y == 8))) {
    return 0;
}
for (i = 1; i <= SIZE; i++) {
    for (j = 1; j <= SIZE; j++) {
        if ((i != y) && (j != x) && ((i != y + j) && (j != x + i)) && ((i != y + j) && (j != x - i))
            && ((i != y - j) && (j != x + i)) && ((i != y - j) && (j != x - i))) {
            result += knightsTour(i, j, num - 1) + 1;
        }
    }
}
return result;
}

Answer 1

您的代码有几个问题：

调用 recursivev 函数时，您无条件地将结果加一。你应该只计算 6 次移动后落在 h8 上的路径，只有在你跳到新位置后才能检查。
当你想找到可能的走法时，检查棋盘上的所有方格是一种浪费。你知道骑士的等级，所以你也知道八种可能的动作。你必须小心不要跳下棋盘。在函数的开头更容易验证rank和file是否有效

一种方法是以下递归方法：

军衔和档案有效吗？如果不是，return 0.
我们达到了想要的步数了吗？如果是，return如果当前方块是 h8，则为 1，否则为 0。
Return 骑士从当前位置开始八步可能的步数少一步所能走的有效步数的总和。这里不需要检查，因为在函数开始时会检查着法的有效性。

综合起来：

#include <stdio.h>

#define SIZE 8

int knightsTour(int x, int y, int num)
{
    if (x < 1 || x > SIZE) return 0;
    if (y < 1 || y > SIZE) return 0;

    if (num == 0) return (x == SIZE && y == SIZE);

    return knightsTour(x + 2, y + 1, num - 1)
         + knightsTour(x + 1, y + 2, num - 1)
         + knightsTour(x - 1, y + 2, num - 1)
         + knightsTour(x - 2, y + 1, num - 1)
         + knightsTour(x - 2, y - 1, num - 1)
         + knightsTour(x - 1, y - 2, num - 1)
         + knightsTour(x + 1, y - 2, num - 1)
         + knightsTour(x + 2, y - 1, num - 1);
}

int main(void)
{
    int result = knightsTour(1, 1, 6);

    printf("%d\n", result);
    return 0;
}

这段代码很简单，它确定了 108 种可能的着法。

骑士之旅- 给定 n 步，骑士在 n 步中有多少种选择可以从 (1,1) 移动到 (8,8)？

Knight's tour- given n moves, in how many options can a knight move from (1,1) to (8,8) in n moves?

c

recursion

knights-tour