// N reinas sin poda: pone una reina en cada fila, en cualquier columna, y solo revisa al final.
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 9

// Revisa cada par de reinas: 1 si ninguna ataca a otra.
static int all_safe(const int *column_of_row, int n) {
    for (int a = 0; a < n; a++) {
        for (int b = a + 1; b < n; b++) {
            int same_column = column_of_row[a] == column_of_row[b];
            int same_diagonal = abs(column_of_row[a] - column_of_row[b]) == b - a;
            if (same_column || same_diagonal) {
                return 0;
            }
        }
    }
    return 1;
}

static long search(int *column_of_row, int n, int row, long *nodes) {
    (*nodes)++;
    if (row == n) {
        return all_safe(column_of_row, n);
    }
    long solutions = 0;
    for (int col = 0; col < n; col++) {
        column_of_row[row] = col;
        solutions += search(column_of_row, n, row + 1, nodes);
    }
    return solutions;
}

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;
    }
    int column_of_row[MAX_N];
    long nodes = 0;
    long solutions = search(column_of_row, n, 0, &nodes);
    printf("n = %d, sin poda: %ld soluciones, %ld nodos\n", n, solutions, nodes);
    return 0;
}