#include <stdio.h>
#include <stdbool.h>
#define N 4
void printSolution(int board[N][N]) {
static int count = 1;
printf("Solution %d:\n", count++);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf("%c ", board[i][j] ? 'Q' : '.');
printf("\n");
}printf("\n");
}
bool isSafe(int board[N][N], int row, int col) {
for (int i = 0; i < col; i++)
if (board[row][i])
return false;
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
for (int i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;
return true;
}
bool solveNQUtil(int board[N][N], int col) {
if (col >= N) {
printSolution(board);
return true;
}
bool res = false;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
res = solveNQUtil(board, col + 1) || res;board[i][col] = 0;
} }
return res;
}
void solveNQ() {
int board[N][N] = {0};
if (!solveNQUtil(board, 0))
printf("Solution does not exist");
}
int main() {
solveNQ();
return 0;
}