#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#define N 8
void printSolution(int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%d ", board[i][j]);
}
printf("\n");
}
}
bool isSafe(int board[N][N], int row, int col) {
int i, j;
// Check this row on left side
for (i = 0; i < col; i++)
if (board[row][i])
return false;
// Check upper diagonal on left side
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
Check lower diagonal on left side
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;
return true;
}
bool solveNQueensUtil(int board[N][N], int col) {
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQueensUtil(board, col + 1) == true)
return true;
board[i][col] = 0;
}
}
return false;
}
void solveNQueens() {
int board[N][N] = {0};
if (solveNQueensUtil(board, 0) == false) {
printf("Solution does not exist\n");
} else {
printSolution(board);
}
}
int main() {
clock_t start, end;
double cpu_time_used;
start = clock();
solveNQueens();
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("\nRunning time: %f seconds\n", cpu_time_used);
return 0;
}
Output:
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
Running time: 0.000088 seconds
