Knight's Tour Problem

general
,
1

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;
}
2

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_backs 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});

:slightly_smiling_face:

1 Like