#include <stdio.h>
#include <conio.h>

int board[10][10], n;
int isSafe(int row, int col) {
    int i, j;
    for (i = 0; i < col; i++)
        if (board[row][i])
            return 0;
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j])
            return 0;
    for (i = row, j = col; i < n && j >= 0; i++, j--)
        if (board[i][j])
            return 0;
    return 1;
}
int solveNQ(int col) {
    int i;
    if (col >= n)  
        return 1;
    for ( i = 0; i < n; i++) {
        if (isSafe(i, col)) {
            board[i][col] = 1;  
            if (solveNQ(col + 1))
                return 1;      
            board[i][col] = 0;  
        }
    }
    return 0;
}
void main() {
    int i,j;
    clrscr();
    printf("Enter number of queens: ");
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            board[i][j] = 0;
    if (solveNQ(0) == 0) {
        printf("No solution exists\n");
        return 0;
    }
    printf("Solution:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)
            printf("%d ", board[i][j]);
        printf("\n");
    }
    getch();
}