Brute Force/Complete Search/ recursive backtracking: the eight queens example

Back Tracking or Brute Force

I stopped writing for a few days, but now I am back. So let us get the job started.

In Brute force, we traverse the entire search space.

In a programming competition, a contestant should keep brute force as his last option.

I found this example interesting:

Statement:

In chess (with an 8 × 8 board), it is possible to place eight

queens on the board such that no two queens attack each other. Determine all such possible

arrangements given the position of one of the queens (i.e. coordinate (a, b) must contain a

queen). Output the possibilities in a lexicographical (sorted) order.

The most naive solution:

Enumerate all combinations of 8 different cells out of 8*8=64 possible cells, this is $^6^4C8$ ~ 4B, thus it is not even worth trying.

Better but naive solution:

Each queen can only occupy one column, so we can put exactly one queen in each column. There are $8^8$ possibilities now. (8*8*...) ~17M

Better:

No two queen can share the same column or the same row. This makes it an 8!~40K problem. This will get accepted.

Yet Better:

They can't even share the same diagonal. This makes it far less than 8! And we will be able to easily make it.

Implementation:

This tutorial is based on CP3 book, so is my code:

#include <bits.stdc++.h>
	using namespace std;
	int row[8];
	bool place(int r, int c){
	for (int prev = 0; prev < c; prev++) // check previously placed queens
	if (row[prev] == r || (abs(row[prev] - r) == abs(prev - c)))
	return false; // share same row or same diagonal -> infeasible
	return true;
	}
	void backtrack(int c){
	if(c==8&&row[b]==a){
	for (int j = 1; j < 8; j++) printf(" %d", row[j] + 1);
	printf("\n");
	}
	for(int r=0;r<8;r++){
	if(canPlace(r, c)){
	row[c] = r;
	backtrack(c+1);
	}
	}//iterating for all rows in this column
	}
	int main(int argc, char const *argv[]) {
	int T;
	cin>>T;
	while (T--) {
	int a, b;
	a--; b--;
	memset(chess, 0, sizeof(chess));
	printf("SOLN COLUMN\n");
	backtrack(0);
	}
	return 0;
	}