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

Baxter

My tip is to step through the code with a debugger, keeping track of variable values. – Comedy

"If the tour starting at 0,0 is foudn so quickly, then it might either be pure chance, or the arrays xMove and yMove were cleverly initialized, such that a solution for (0,0) is found quickly.", found this while googling from #18073758 – Baxter

So the person who wrote that doesn't actually know that the values were cleverly chosen. – Bullfrog

That shows the importance of heuristic. – Shaky

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.

Anthropopathy

The problem is actually symmetrical and has multiple solutions. So for a solution that starts with dx=2 and dy=1, there will be another solution that starts with dx=1 and dy=2 (which are the first values used by the uncommented code). I think the improvement has more to do with the second item in the list, and its relation to the first item. – Bullfrog

Sure, that's fair. I guess the takeaway is that the ordering of the deltas -- especially the first few ones -- is a heuristic that can be tuned to find a specific solution quickly. – Anthropopathy

Answer 2

There are eight valid knight's moves in chess:

The two arrays list those eight moves.

The two versions of the code try the moves in different order. It so happens that one version comes across a valid solution much quicker than the other.

That's all there is to it.

Brokenhearted

dude you didnt answer my question, why does it happen, with this array, I also tried some other combinations but they were not working – Baxter

@Jignesh: No need to be rude, especially towards those who are trying to help you. – Brokenhearted

rude? hey I was just stating my question more clearly, sorry if you felt so – Baxter