0

I wrote down the code for knight tour problem, I couldn't figure out what is the actual issue with the solution, it's running fine upto n=6, but after that it is taking a long time to run. It's showing correct output but taking a really long time as I put n=7 or n=8 or higher. Here's my code:

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

bool isSafe(vector<vector<int>> sol, int x, int y){
    int n=sol.size();
    return (x>=0 && x<n && y>=0 && y<n && sol[x][y]==-1);
}

bool findSolUtil(vector<vector<int>> &sol, vector<int> xMoves, vector<int> yMoves, int x, int y, int count){
    int n=sol.size(), i, next_x, next_y;
    if(count==n*n){
        return true;
    }
    for(i=0; i<8; i++){
        next_x = x+xMoves[i];
        next_y = y+yMoves[i];
        if(isSafe(sol, next_x, next_y)){
            sol[next_x][next_y] = count;
            if(findSolUtil(sol, xMoves, yMoves, next_x, next_y, count+1)){
                return true;
            }
            sol[next_x][next_y] = -1;
        }
    }
    return false;
}

void findSol(int n){
    vector<vector<int>> sol(n, vector<int>(n, -1));
    vector<int> xMoves = {2, 1, -1, -2, -2, -1, 1, 2};
    vector<int> yMoves = {1, 2, 2, 1, -1, -2, -2, -1};
    sol[0][0] = 0;
    cout << findSolUtil(sol, xMoves, yMoves, 0, 0, 1);
}

int main(){
    int n;
    cout << "Size of the board is nXn, enter n : ";
    cin >> n;
    findSol(n);
    return 0;
}
false
  • 10,264
  • 13
  • 101
  • 209
A.S.
  • 1
  • 1
  • 2
  • 2
    Might be better suited on [Code Review](https://codereview.stackexchange.com/) – ejderuby Jul 30 '19 at 15:29
  • Your algorithm is just brute-forcing a solution, so it won't be very fast for large problems. One minor thing you can easily improve is to pass `sol` to `isSafe` by const reference instead of by value. – chtz Jul 30 '19 at 16:19
  • @chtz I found this same solution in geeksforgeeks, they are using the same but with arrays and this is running really okay, I'm not able to find a difference between my solution and this -> https://www.geeksforgeeks.org/the-knights-tour-problem-backtracking-1/ – A.S. Aug 01 '19 at 06:24
  • The difference is that the linked solution passes the board via a pointer to `isSafe`, whereas your version always needs to copy it. As said before, just pass `sol` by const reference. – chtz Aug 01 '19 at 12:36
  • Btw: If your question is based on an external resource, it would be good style to at least reference that (in the question itself, not in the comments). – chtz Aug 01 '19 at 12:38
  • Does this answer your question? [Knight's tour backtrack implementation choosing the step array](https://stackoverflow.com/questions/21511683/knights-tour-backtrack-implementation-choosing-the-step-array) – tkruse Apr 07 '20 at 05:38

0 Answers0