1

所以我想出了这个实现来解决 8*8 棋盘的骑士之旅。但似乎它需要很长时间才能运行（以至于我不得不停止它）。但是，如果我用注释中写的数组替换 dx、dy 数组，程序就会像魔术一样工作并给出输出。他们说它巧妙地选择了数组，因此暴力算法很幸运能够快速找到解决方案。

但是首先是如何提出这个数组的，这个数组（dx，dy）是我从其他代码中得到的。所以谁能解释我为什么这段代码适用于这些数组（在评论中）而不是我的。

#include <cstdio>

using namespace std;

int dx[8] = {  1,  1, 2,  2,  -1, -1, -2, -2};
int dy[8] = {  2, -2, 1, -1,  2,  -2,  1, -1};

//int dx[8] = {  2, 1, -1, -2, -2, -1,  1,  2 };
//int dy[8] = {  1, 2,  2,  1, -1, -2, -2, -1 };

bool solve(bool arr[8][8],int x,int y,int moves){
    if(moves==0)return true;
    if(x<0 || y<0 || x>7 || y>7 || arr[x][y])return false;
    arr[x][y]=1;

    for(int i=0;i<8;i++)
        if(solve(arr,x+dx[i],y+dy[i],moves-1)){
            printf(" (%d,%d) ",x,y);
            return 1;
        }
    arr[x][y]=0;
    return false;
}

int main()
{
    bool arr[8][8];
    for(int i=0;i<8;i++)    for(int j=0;j<8;j++)    arr[i][j]=0;
    solve(arr,0,0,64);
    puts("");
}
4

2 回答 2

2

概括

注释掉的dx/dy数组比您的初始数组工作得更好的原因是因为它以不同的顺序执行深度优先搜索解决方案 - 选择一个考虑特定解决方案的顺序，因此能够找到解决比较快。

细节

深度优先搜索从树的根部开始，检查到叶子的每条路径。例如，这棵树的深度优先搜索将首先检查仅访问a节点 ( a -> a -> a) 的路径，然后稍微回溯并检查a -> a -> b，然后a -> a -> c，等等。

深度优先aaa

如果树很大并且没有从访问开始的解决方案，这可能会花费很多时间a，因为您必须浪费大量时间检查所有以开始的路径，a然后才能继续使用更好的路径。

如果您碰巧知道有一个以 开头的好解决方案d，您可以通过重新排序树的节点来加快速度，以便您首先检查以 开头的路径d：

ddd

马上，您已经删除了程序必须完成的 7/8 工作，因为您永远不必费心寻找以d!开头的路径。通过为其余节点选择良好的顺序，您可以获得类似的加速。

如果您查看程序的输出，您会看到这种情况：

(0,7)  (1,5)  (3,4)  (1,3)  (0,1)  (2,0)  (4,1)  (6,0)  (7,2)  (5,3)  (7,4)
(6,2)  (7,0)  (5,1)  (4,3)  (3,1)  (5,0)  (7,1)  (5,2)  (7,3)  (6,1)  (4,0)
(3,2)  (4,4)  (2,3)  (0,2)  (1,0)  (2,2)  (3,0)  (1,1)  (0,3)  (2,4)  (1,2)
(0,4)  (1,6)  (3,7)  (2,5)  (3,3)  (5,4)  (6,6)  (4,5)  (6,4)  (7,6)  (5,5)
(4,7)  (2,6)  (0,5)  (1,7)  (3,6)  (5,7)  (6,5)  (7,7)  (5,6)  (3,5)  (1,4)
(0,6)  (2,7)  (4,6)  (6,7)  (7,5)  (6,3)  (4,2)  (2,1)  (0,0)

第一步（从底部读取）是 from (0,0)to (2,1)，它对应于dx=2and dy=1-- 果然，在注释掉的dx/dy列表中，这是检查的第一种可能性。事实上，这个解决方案的前三步使用dx=2and dy=1，这实际上意味着你只需要搜索一个很小的子树而不是整个东西。

于 2014-02-02T16:12:42.303 回答
0

国际象棋中有八个有效的骑士移动：

骑士的动作

这两个数组列出了这八个动作。

两个版本的代码以不同的顺序尝试移动。碰巧一个版本比另一个更快地遇到一个有效的解决方案。

这里的所有都是它的。

于 2014-02-02T14:34:20.830 回答