# Knight's Tour Problem

Can anyone spot what’s wrong in this knight’s tour problem? I’m not getting the output. Many thanks!

``````#include <bits/stdc++.h>
#define vi vector<int>
#define dvi vector<vi>
using namespace std;

void peek (vector<vi>& a) {
for(vi i:a) {
for(int j:i) cout << j << " ";
cout << endl;
}
cout << endl;
}

bool left (dvi& board, int n) {
for(vi i:board) {
for(int j:i) {
if(j==0) return true;
}
}
return false;
}

dvi options (dvi& board, int n, int i, int j) {
dvi opt;
opt.push_back({i-2,j+1});
opt.push_back({i-2,j-1});
opt.push_back({i+2,j+1});
opt.push_back({i+2,j-1});
opt.push_back({i-1,j+2});
opt.push_back({i-1,j-2});
opt.push_back({i+1,j+2});
opt.push_back({i+1,j-2});
return opt;
}

bool solve (dvi& board, int n, int c, int i, int j) {
if(!left(board,n)) {
peek(board);
return true;
}
else {
dvi opt=options(board,n,i,j);
for(int k=0;k<opt.size();k++) {
int ii=opt[k][0];
int jj=opt[k][1];
if(ii>-1&&ii<n&&jj>-1&&jj<n&&board[ii][jj]==0) {
board[ii][jj]=c;
if(solve(board,n,c+1,ii,jj)) return true;
board[ii][jj]=0;
}
}
}
return true;
}

int main () {
dvi board(8,vi(8,0));
board[0][0]=1;
solve(board,8,2,0,0);
return 0;
}``````

Only one thing is wrong in your program, the last statement of function `solve` must be `return false;`. To get the output (in a bearable amount of time) you might have to reorder the `push_back`s like this:

``````opt.push_back({i+2,j+1});
opt.push_back({i+1,j+2});
opt.push_back({i-1,j+2});
opt.push_back({i-2,j+1});
opt.push_back({i-2,j-1});
opt.push_back({i-1,j-2});
opt.push_back({i+1,j-2});
opt.push_back({i+2,j-1});
``````

1 Like