// N reinas, hasta la primera solución: el retorno avisa que ya no hay que seguir buscando.
#include <stdio.h>

#define MAX_N 16

typedef struct {
    int n;
    int column_of_row[MAX_N];
    int column_used[MAX_N];
    int down_used[2 * MAX_N - 1];
    int up_used[2 * MAX_N - 1];
    long nodes;
} Queens;

static int can_place(const Queens *q, int row, int col) {
    return !q->column_used[col]
        && !q->down_used[row - col + q->n - 1]
        && !q->up_used[row + col];
}

static void mark(Queens *q, int row, int col, int value) {
    q->column_used[col] = value;
    q->down_used[row - col + q->n - 1] = value;
    q->up_used[row + col] = value;
}

// Devuelve 1 si encontró una solución, y la deja en column_of_row.
static int search(Queens *q, int row) {
    q->nodes++;
    if (row == q->n) {
        return 1;
    }
    for (int col = 0; col < q->n; col++) {
        if (can_place(q, row, col)) {
            mark(q, row, col, 1);
            q->column_of_row[row] = col;
            if (search(q, row + 1)) {
                return 1;
            }
            mark(q, row, col, 0);
        }
    }
    return 0;
}

static void print_board(const Queens *q) {
    for (int row = 0; row < q->n; row++) {
        for (int col = 0; col < q->n; col++) {
            if (q->column_of_row[row] == col) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
}

int main(int argc, char *argv[]) {
    int n;
    if (argc != 2 || sscanf(argv[1], "%d", &n) != 1 || n < 1 || n > MAX_N) {
        fprintf(stderr, "uso: %s n, con n entre 1 y %d\n", argv[0], MAX_N);
        return 1;
    }
    Queens q = {.n = n};
    if (search(&q, 0)) {
        print_board(&q);
    } else {
        printf("no hay solución\n");
    }
    printf("n = %d, primera solución: %ld nodos\n", n, q.nodes);
    return 0;
}