// ERROR A PROPÓSITO: se quita la reina de la columna, pero sus diagonales quedan marcadas.
#include <stdio.h>

#define MAX_N 16

typedef struct {
    int n;
    int column_used[MAX_N];
    int down_used[2 * MAX_N - 1];   // diagonal que baja: row - col + n - 1 es constante
    int up_used[2 * MAX_N - 1];     // diagonal que sube: row + col es constante
    long solutions;
    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];
}

// Pone una reina con value = 1 y la quita con value = 0.
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;
}

static void search(Queens *q, int row) {
    q->nodes++;
    if (row == q->n) {
        q->solutions++;
        return;
    }
    for (int col = 0; col < q->n; col++) {
        if (can_place(q, row, col)) {
            mark(q, row, col, 1);       // elegir
            search(q, row + 1);         // explorar
            q->column_used[col] = 0;    // deshace solo una parte
        }
    }
}

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};
    search(&q, 0);
    printf("n = %d, con poda: %ld soluciones, %ld nodos\n", n, q.solutions, q.nodes);
    return 0;
}