c++ - 递归N-骑士问题

Question

我正在尝试递归地解决 8x8 棋盘上的 n 位骑士问题。 n-骑士问题是 n- queens problem 的变体，其中皇后被骑士取代。没有一 block 可以占据另一 block 。

到目前为止我的代码:http://pastebin.com/TVza3jVU .

输入包括必须放置在棋盘上的马的数量。我的代码打印了很多正确的板

输出如下(示例):

0 0 0 0 0 0 0 0  0
0 0 0 0 0 0 0 0  1
0 0 0 0 0 0 0 0  2
0 0 0 0 0 0 0 0  3
0 0 0 0 0 0 0 0  4
0 0 0 0 0 0 0 0  5
0 0 0 0 0 0 1 0  6
1 1 0 1 0 1 0 0  7

0 1 2 3 4 5 6 7

nrBoards = 49

“1”代表骑士。

<小时/>

我的问题如下:

0 1 1 1 1 1 0 0  0
0 0 0 0 0 0 0 0  1
0 0 0 0 0 0 0 0  2
0 0 0 0 0 0 0 0  3
0 0 0 0 0 0 0 0  4
0 0 0 0 0 0 0 0  5
0 0 0 0 0 0 0 0  6
0 0 0 0 0 0 0 0  7

0 1 2 3 4 5 6 7

这是我的脚本将打印的最后一 block 板。它永远不会将骑士放在 [0][0] 上。我不明白为什么。它还会跳过一些配置。我的递归有问题吗？

Answer 1

从您链接的代码来看，似乎有一个问题出在您的 checkplace() 函数中。您不检查 x+2、x-2、y+2、y-2 等的边界是否在 0 到 7 的区间内或之外。

int checkPlace(int y, int x, chessboard boards) {
    if (boards.board[y - 2][x - 1] == 1) {
      return 0;
    }
    if (boards.board[y - 1][x - 2] == 1) {
      return 0;
    }
    if (boards.board[y - 2][x + 1] == 1) {
      return 0;
    }
    if (boards.board[y - 1][x + 2] == 1) {      
      return 0;
    }
    if (boards.board[y + 1][x + 2] == 1) {
      return 0;
    }
    if (boards.board[y + 1][x - 2] == 1) {      
      return 0;
    }
    if (boards.board[y + 2][x - 1] == 1) {
      return 0;
    }
    if (boards.board[y + 2][x + 1] == 1) {
      return 0;
    }
    return 1;
}

相反:

if ( x-1 >= 0 && y-2 >= 0 && boards.board[y - 2][x - 1] == 1) {

其他人也类似。