edited by
1,057 views
0 votes
0 votes

Write a recursive backtracking solution for placing $3$ rooks in $6^*6$ chess board.

  1. Naive backtracking.
  2. Try using bitmask to speed it up.
edited by

1 Answer

Best answer
0 votes
0 votes
#include <bits/stdc++.h>
using namespace std;
unsigned int mask;
const int M = 2;
const int N = 5;
int no_of_sol = 0;
int all_placed = (1<<N)-1;
int pos[N];
void backtrack(int col_mask,int rwm,int col) {
  if(col == M) {
    no_of_sol++;
		for(int r = 0;r<N;r++) {
			for(int c = 0;c<N;c++) {
				(pos[c] == r && mask&(1<<c))?printf("#  "):printf(".  ");
			}
			printf("\n\n");
		}
		printf("-------------\n\n");
		return;	
	}else {
		if(col_mask) {
			int col_pos = __builtin_ctz(col_mask);
			int mask = all_placed & (~(rwm)); 
			// mask tells us which positions 
			// are free now to place rooks to place in this col
			while(mask) {
				int m = mask & -mask;
				mask = mask - m;
				pos[col_pos] = __builtin_ctz(m); 	
				// pos[] is an helper array
				// to display results
				col_mask = col_mask & (~(1<<col_pos));
				backtrack(col_mask,rwm|m,col+1);
			}
		}
	}
}
// solve() creates the k column subsets out N columns
// when a subset is ready ( or the mask is ready )
// we call backtrack() to choose the rows to place 
void solve(int n,int k,int idx,int cnt) {
	if(cnt == (n-k)) {
		// column subset mask is ready
		// or we have selected k column
		// now row selection will be controlled by row_mask
		// and the exact positions will be handled in the backtrack() function
		backtrack(mask,0,0);
		/*backtrack(column_subset,row_mask,no_of_rooks_placed);*/
		return;
	}else if(idx >= 0) {
		// subset mask creating
		for(int i=idx;i>=0;i--) {
			mask &= ~(1<<i);
			solve(n,k,i - 1,cnt+1);
			mask |= (1<<i);
		}
	}
}
int main() {
	int n = N,k = M;
	for(int i=0;i<n;i++) mask |= (1<<i);
	solve(n,k,n-1,0);
	printf("%d\n",no_of_sol);
}

OutputFile

 
selected by

Related questions

1 votes
1 votes
2 answers
2
A_i_$_h asked Sep 12, 2017
854 views
number of rectangles in a chess board that are not sqaurea)1296b)1092c)1096d)1292
3 votes
3 votes
2 answers
3