Knight's Tours

Problem Statement (Wikipedia Link):

On a NxN chess board, find all legal Knight's Tours.

Fig., a valid Knight's Tour demo on N=5 chess board, courtesy of Wikipedia

Analysis:
Same as N-Queens problem, Knight's Tour is a classic problem that can be solved using backtracking. As other backtracking problems, the time complexity is exponential.

I have run a N=5 case, there are in total 304 possible solutions.

Note that the backtracking is not the optimal solution for the problem. See the wiki page here for other better algorithms, such as Divide and Conquer and Neural Networks (here).

Code:

// Main function
int numSols;
bool knightTour(int n, vector<vector<int>>& out) {
    int xmove[8]={-2,-2,-1,-1,1,1,2,2};
    int ymove[8]={1,-1,2,-2,2,-2,1,-1};

    // initialization
    for (int i=0; i<n; i++)
        out.push_back(vector<int> (n, -1));

    // start at upper left corner
    numSols=0;
    out[0][0]=0;
    return recur(0, 0, n, 1, xmove, ymove, out);
}

bool recur(int x, int y, int n, int visited, int xmove[], int ymove[], vector<vector<int>>& out) {
    if (visited>=n*n) {
        numSols++;
        printTour(n, out);
    }
    else { // try next move
        for (int i=0; i<8; i++) {
            if (isValid(x+xmove[i], y+ymove[i], n, out)) {
                out[x+xmove[i]][y+ymove[i]]=visited;
                if (recur(x+xmove[i], y+ymove[i], n, visited+1, xmove, ymove, out))
                    return true;
                else
                    out[x+xmove[i]][y+ymove[i]]=-1;
            }
        }
    }
    return true;
}

bool isValid(int x, int y, int n, vector<vector<int>> out) {
    if (x>=0 && x<n && y>=0 && y<n && out[x][y]==-1) return true;
    return false;
}

void printTour(int n, vector<vector<int>> out) {
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cout<<out[i][j]<<"\t";
        }
        cout<<endl;
    }
    cout<<"\n";
}