骑士的巡回路线实现选择步长数组 [英] Knight's tour backtrack implementation choosing the step array

问题描述

因此，我想出了此解决方案，用于解决8 * 8棋盘的骑士巡回赛. 但是似乎要花很长时间才能运行(以至于我不得不停止它).但是，如果我用注释中写的那个替换dx，dy数组，程序将像魔术一样工作并给出输出.他们说，它是明智地选择阵列的方法，因此蛮力算法很幸运能够快速找到解决方案.

So I came up with this implementation for solving knights tour for a 8*8 chess board. But seems like it is taking a long time running (so long that I have to stop it). But if I replace the dx, dy arrays with the one written in comments and the program works like magic and gives the output. They say that it is cleverly choosing the array, so that the bruteforce algo is lucky to find the solution quickly.

但是首先如何提出这个数组，我是从其他代码中得到的这个数组(dx，dy).因此，谁能解释我为什么此代码为何对那些数组有效(在注释中)而不对我的有效?

But how does one come up with this array at first place, this array (dx,dy) I got from some other code. So can anyone explain me why does this code work with those arrays (in comment) and not mine.

#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("");
}

推荐答案

摘要

带注释的dx/dy数组比初始数组更好的原因是因为它以不同的顺序执行深度优先搜索，这是在考虑特定解决方案的情况下选择的顺序，以及因此能够相对快速地找到该解决方案.

Summary

The reason the commented-out dx/dy array works better than your initial array is because it performs the depth-first search for a solution in a different order -- an order that was chosen with a specific solution in mind and which therefore is able to find that solution relatively quickly.

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

Depth-first search starts at the root of a tree and examines every path to a leaf. For example, a depth-first search of this tree would first examine the path that visits only a nodes (a -> a -> a) then it would backtrack slightly and examine a -> a -> b, then a -> a -> c, etc.

如果树很大，并且没有任何解决方法以访问a开头，这可能会花费很多时间，因为您必须浪费很多时间，检查所有路径从a开始，然后再继续寻找更好的路径.

This can take a lot of time if the tree is large and there are no solutions that start by visiting a, because you have to waste a lot of time examining all of the paths that start with a before you can move on to better paths.

如果您偶然发现有一个很好的解决方案以d开头，则可以通过重新排序树的节点来加快速度，从而可以通过检查以d开头的路径开始:

If you happen to know that there is a good solution that starts with d, you can speed things up a little by re-ordering the nodes of your tree such that you start by examining paths that begin with d:

马上就删除了程序必须完成的工作的7/8的工作，因为您不必费心搜索以d以外的东西开头的路径！通过为其余节点选择一个良好的顺序，您可以获得类似的加速效果.

Right off the bat you've removed 7/8ths of the work your program has to do, because you never have to bother searching for paths that start with something other than d! By choosing a good ordering for the rest of the nodes, you can get similar speedups.

如果您查看程序的输出，就可以看到这种情况:

You can see this happening if you look at the output of your program:

(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)

第一个步骤(从底部开始读取)是从(0,0)到(2,1)，它对应于dx=2和dy=1-并且确实在注释掉的dx/dy列表中，这是首先要检查的可能性.实际上，此解决方案的前三步使用dx=2和dy=1，这实际上意味着您只需要搜索很小的小子树而不是整个事情.

The first move (reading from the bottom) is from (0,0) to (2,1), which corresponds to dx=2 and dy=1 -- and sure enough, in the commented-out dx/dy list, that's the first possibility that is examined. In fact, the first three moves of this solution use dx=2 and dy=1, which effectively means you only have to search a tiny little sub-tree instead of the whole thing.

这篇关于骑士的巡回路线实现选择步长数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！