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("");
}
See Question&Answers more detail:os