Tips for applying Back Tracking or Complete Search.

Tips

Suppose that your Complete Search takes ~10 Seconds on worst-case and TL is 10 Seconds, and the judge gives TLE, then you should tweak the code instead of designing a new algorithm.

Tip 1: Filtering versus Generating:

Programs that examine lots of(if not all) candidate solutions and choose the ones that are correct are called filters.

Programs that build the solutions and prune out invalid partial solutions -> generators.

Usually, 'generator' programs are easier to implement when written recursively as it gives us greater flexibility for pruning the search space...

Tip 2: Prune Infeasible?Inferior Search Space Early

Most often, we may encounter a partial solution that will never lear to a full solution. We can keep a note of it and prune the search space there and explore other parts of the search space. As a rule of thumb, the earlier you can prune the search space, the better.

Tip 3: Utilize Symmetries

Some problems have symmetries, and this can be taken advantage of.

In Cp, this is usually not the best way (we want to minimize the bugs). If the gain obtained by dealing with symmetry is not significant in solving the problem, just ignore this tip.

Tip 4: Pre-Computation a.k.a. Pre-Calculation

Sometimes it is helpful to generate tables or other DS that accelerate the lookup of a result prior to the execution of the program itself. This is called Pre-Computation.

Tip 5: Optimizing your source code

1. Use C++ instead of Java. C++ gets implemented faster in C++ than in Java. Few judges give Java users extra time for this lag though.

2. User scanf/printf rather than cin/cout.

3. Access a 2D array in a row-major fashion(row by row) rather than in a column-major fashion. Multidimensional arrays are stored in row-major order in memory.

4. Bit manipulation on the built-in integer data types is more efficient than index manipulation in an array of booleans. If we need more than 64 bits, use the C++ STL bitset rather than vector<bool>.

5. Preer arrays over vectors if memory is not an issue. 

8. Declare most data structures(especially the bulky ones) by placing them in the global scope. And clear it as and when needed.

9. If there is an option to write code iteratively or recursively, choose the iterative version.

10. Array access costs. If you need to access A[i] many times, it may be good to store it in temp=A[i] and work with it instead.

11. Use macros or inline functions.

12. C-style character arrays are faster than string.

Tip 7:

Using better DS and Algo will beat all other tips.

Disclaimer: All my notes are based on the Competetive Programming 3 book.

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