retagged by
2,656 views

1 Answer

Best answer
1 votes
1 votes

One possible solution:

#include <bits/stdc++.h>
#define N 5
int pos[N];
int no_of_sol = 0;
bool is_ok(int current_row,int current_col) {
	for(int prev_col = 0; prev_col < current_col; prev_col++) {
		if(pos[prev_col] == current_row || 
			(abs(pos[prev_col] - current_row) == abs(prev_col - current_col)) ) {
			return false;
		}
	}
	return true;
}
void backtrack(int col) {
	if(col == N) {
		no_of_sol++;
		for(int r=0;r<N;r++) {
			for(int c=0;c<N;c++) {
				(pos[c] == r)?printf("#  "):printf(".  ");
			}
			printf("\n\n");
		}
		printf("-------------\n\n");
	}else {
		for(int row = 0;row < N;row++) {
			if(is_ok(row,col)) {
				pos[col] = row;
				backtrack(col+1);
			}
		}
	}
}
int main(void) {
	backtrack(0);
	printf("Total no of solutions with N = 5 is = %d\n",no_of_sol);
}

Output :

#  .  .  .  .  

.  .  .  #  .  

.  #  .  .  .  

.  .  .  .  #  

.  .  #  .  .  

-------------

#  .  .  .  .  

.  .  #  .  .  

.  .  .  .  #  

.  #  .  .  .  

.  .  .  #  .  

-------------

.  .  #  .  .  

#  .  .  .  .  

.  .  .  #  .  

.  #  .  .  .  

.  .  .  .  #  

-------------

.  .  .  #  .  

#  .  .  .  .  

.  .  #  .  .  

.  .  .  .  #  

.  #  .  .  .  

-------------

.  #  .  .  .  

.  .  .  #  .  

#  .  .  .  .  

.  .  #  .  .  

.  .  .  .  #  

-------------

.  .  .  .  #  

.  .  #  .  .  

#  .  .  .  .  

.  .  .  #  .  

.  #  .  .  .  

-------------

.  #  .  .  .  

.  .  .  .  #  

.  .  #  .  .  

#  .  .  .  .  

.  .  .  #  .  

-------------

.  .  .  .  #  

.  #  .  .  .  

.  .  .  #  .  

#  .  .  .  .  

.  .  #  .  .  

-------------

.  .  .  #  .  

.  #  .  .  .  

.  .  .  .  #  

.  .  #  .  .  

#  .  .  .  .  

-------------

.  .  #  .  .  

.  .  .  .  #  

.  #  .  .  .  

.  .  .  #  .  

#  .  .  .  .  

-------------

Total no of solutions with N = 5 is = 10


One more faster solution :

#include <bits/stdc++.h>
#define N 5
int no_of_sol = 0;
int all_placed = (1<<N)-1;
int pos[N];
void backtrack(int rwm,int rdm,int ldm,int col) {
	if(rwm == all_placed) {
		no_of_sol++;
		for(int r = 0;r<N;r++) {
			for(int c = 0;c<N;c++) {
				(pos[c] == r)?printf("#  "):printf(".  ");
			}
			printf("\n\n");
		}
		printf("------------\n\n");
		return;	
	}else {
		int mask = all_placed & (~(rwm|rdm|ldm));
		while(mask) {
			int m = mask & -mask;
			mask = mask - m;
			pos[col] = __builtin_ctz(m);
			backtrack(rwm|m,(rdm|m) << 1,(ldm|m) >> 1,col+1);
		}
	}
}	
int main(void) {
	backtrack(0,0,0,0);
	printf("Total no of solutions with N = 5 is = %d\n",no_of_sol);
}

selected by

Related questions

2 votes
2 votes
1 answer
1
admin asked Mar 31, 2020
4,339 views
Which type of algorithm is used to solve the "$8$ Queens" problem ?GreedyDynamicDivide and conquerBacktracking
1 votes
1 votes
0 answers
2
LavTheRawkstar asked Sep 9, 2018
644 views
Find all the possible solution for sum of subset problem for the instance m=35 and S=<1,2,5,7,8,10,15,20,25 using Backtracking.I am totally confused hence please provide ...
1 votes
1 votes
1 answer
3
durgesh94 asked Jun 15, 2016
1,737 views
Which of the following feature(s) is/are needed to implement top down parsingSource string marker Prediction making mechanismMatching and Backtracking me...
0 votes
0 votes
1 answer
4
ManojK asked Jun 1, 2016
488 views
The order in which alternative are tried in a backtracking parser affect the language accepted by the compiler or parser.Whether the given statement is valid? Explain wi...