c++ - Knight's tour backtrack implementation choosing the step array

Question

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.

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

Answer 1

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.

Details

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.

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.

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:

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)

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.