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