Problem in Knight tour problem

When i am using this order for next knight’s position
int X[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int Y[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
I am getting the right answer but when I am using the order in the code below it is giving TLE.
Please help. I am following this tutorial link

Code:

my code
#include<bits/stdc++.h>
using namespace std;

int N = 8;

int X[8] = {1,-1,1,-1,2,2,-2,-2};
int Y[8] = {2,2,-2,-2,1,-1,1,-1};

int arr[8][8];

bool issafe(int x,int y) {
	if(x >= 0 and x < N and y >= 0 and y < N) {
		if(arr[x][y]==0) return true;
	}
	return false;
}

bool solve(int r,int c,int cnt) {
	if(cnt == (N*N)+1) {
		return true;
	}

	for(int i=0;i<8;i++) {
		int xpo,ypo;
		xpo = r+X[i];
		ypo = c+Y[i];
		if(issafe(xpo,ypo)) {
			arr[xpo][ypo] = cnt;
			if(solve(xpo,ypo,cnt+1)) {
				return true;
			} else {
				arr[xpo][ypo] = 0;
			}
		}
	}

	return false;
}

void tour() {
	for(int i=0;i<N;i++) {
		for(int j=0;j<N;j++) {
			arr[i][j] = 0;
		}
	}

	arr[0][0] = 1;

	if(solve(0,0,2)) {
		cout<<"SoLVeD"<<endl;

		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				cout<<arr[i][j]<<" ";
			}
			cout<<endl;
		}
	} else {
		cout<<"NOt";
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				cout<<arr[i][j]<<" ";
			}
			cout<<endl;
		}
	}
}

int main() {
	tour();
	return 0;
}

See, both codes are correct. Second one will also give result but it will take large time because of its combination.
You may see this for faster implementation https://www.geeksforgeeks.org/warnsdorffs-algorithm-knights-tour-problem/

how to know which combination is faster? is there any way as there can be many combinations

You will never get such question in any contest. In contests, you will get only those questions whose worst case time will be less than the given time limit. These type of questions are only for practice in backtracking. I think we can not know which combination is faster. It is luck.

3 Likes

Even I encountered the same problem once.

2 Likes

Do you even know what is its time complexity. Don’t just write anything

3 Likes