I wrote a code for The Knight's Tour Problem. It is running fine for 5 by 5 board but is stuck somewhere for 8 by 8 board. I am trying to resolve the issue since last 3 days. Seeking help here now, thanks! Here is the link for question : https://www.geeksforgeeks.org/the-knights-tour-problem-backtracking-1/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool isValid(ll x,ll y,vector<vector<int>> grid,ll n)
{
if(x<0 || y<0 || x>=n || y>=n || grid[x][y] != -1)
{
return 0;
}
return 1;
}
bool solve(vector<vector<vector<int>>>& ans,vector<vector<int>>& grid,ll curr_num,ll x,ll y,ll n,vector<int> xi,vector<int> yi)
{
if(curr_num>(n*n))
{
ans.push_back(grid);
return true;
}
for(ll i=0;i<8;i++)
{
ll nextx = x + xi[i];
ll nexty = y + yi[i];
if(isValid(nextx,nexty,grid,n))
{
grid[nextx][nexty] = curr_num;
if(solve(ans,grid,curr_num+1,nextx,nexty,n,xi,yi)==true)
{
return true;
}
grid[nextx][nexty] = -1;
}
}
return false;
}
int main()
{
ll n;
cin>>n;
vector<vector<int>> grid(n,vector<int> (n,-1));
vector<vector<vector<int>>> ans;
vector<int> xi = {1,1,-1,-1,-2,-2,2,2};
vector<int> yi = {-2,2,-2,2,1,-1,-1,1};
ll curr_num = 2;
grid[0][0] = 1;
ll x = 0;
ll y = 0;
ll distinct = n*n;
bool b = solve(ans,grid,curr_num,x,y,n,xi,yi);
//Printing the answer
for(auto& x : ans)
{
for(auto& y : x)
{
for(auto& z : y)
{
cout<<z<<" ";
}cout<<endl;
}cout<<endl;
}
return 0;
}
Your code looks like it is correct, just inefficient.
bool isValid(ll x,ll y,vector<vector<int>> grid,ll n)
This will create a copy of the board on every call, which means a heap allocation. You should use const vector<vector<int>> &grid. You should start of always using const ... & for all arguments that aren't fundamental types and then reconsider when the compiler complains about something being const.
Another thing you can optimize is
if(x<0 || y<0 || x>=n || y>=n || grid[x][y] != -1)
That simple condition causes 5 branches and kills the branch predictor. A slight improvement is to eliminate the lazy evaluation on the first 4 conditions:
if((x<0 | y<0 | x>=n | y>=n) || grid[x][y] != -1)
Although compilers might think they are smart and still make that 5 branches.
A better way is to add a border to the grid and marking all the border as already visited. Then gird[x][y] can never go outside the bounds.
But more importantly than just speeding up the code in general is pruning the search tree. At the moment you try out move after move until you can move no more. But if you can decide earlier that a move can not result in a solution and prune the whole branch there you can save a lot of time.
Consider this situation (it's easiest to see for a corner but it applies to all fields):
########
########
##1+2+++
##+++3++
##+K++++
##+++4++
###+5+++
The Knight (K) has 5 moves it can make and you try all of them. But if you don't take move 1 then that means there is only one field left from which to reach 1. Field 1 must be the last field in the path. So the first time you see such a situation you can set a flag have_last = true and try out all 5 moves. But the second time you see such a situation (have_last == true) you must take move 1 and can skip 2-5. To do this for more than corners you have to add a second grid where each field says how many other fields can still this field and update/backtrack this for each move too.
This will allow you to avoid making moves that leave fields unreachable and prune the search tree considerably. Testing each move becomes more expensive but as long as it reduces the number of tests you make more than the cost increases it is a win.
Note: Instead of have_last you can also only look for paths that create a loop. In that case have_last would be true from the start and you can optimize it. Are there ever other solutions?
Note2: You start in the corner having 2 moves. Those two result in paths that are mirror images of each other. You can search just one and then mirror the found solutions.