// Escribe el árbol de búsqueda de 4 reinas: cada línea es una reina puesta, con su sangría.
#include <stdio.h>

#define N 4

typedef struct {
    int column_used[N];
    int down_used[2 * N - 1];
    int up_used[2 * 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 + 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 + N - 1] = value;
    q->up_used[row + col] = value;
}

static void print_indent(int row) {
    for (int i = 0; i < row; i++) {
        printf("  ");
    }
}

static void search(Queens *q, int row) {
    q->nodes++;
    if (row == N) {
        print_indent(row);
        printf("solución\n");
        return;
    }
    int tried = 0;
    for (int col = 0; col < N; col++) {
        if (can_place(q, row, col)) {
            tried = 1;
            print_indent(row);
            printf("fila %d, columna %d\n", row, col);
            mark(q, row, col, 1);
            search(q, row + 1);
            mark(q, row, col, 0);
        }
    }
    if (!tried) {
        print_indent(row);
        printf("sin lugar en la fila %d: se vuelve\n", row);
    }
}

int main(void) {
    Queens q = {.nodes = 0};
    search(&q, 0);
    printf("nodos: %ld\n", q.nodes);
    return 0;
}