// Problème des N-reines
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

void board_init(int n, bool board[n][n], bool val) {
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            board[i][j] = val;
        }
    }
}
// Copie les valeurs de la <board_in> dans <board>
void copy(int n, bool board_in[n][n], bool board[n][n]) {
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            board[i][j] = board_in[i][j];
        }
    }
}

// Retourne une copie du tableau <board> complété avec les positions
// prises sur la droite droite par une reine placée en <board(li,co)>
void prises_devant(
    int n, bool board_in[n][n], bool board[n][n], int li, int co) {
    copy(n, board_in, board);
    board[li][co] = false; // position de la reine
    for (int j=1;j<n-co;j++) {
        // horizontale et diagonales à droite de la reine
        if (j <= li) {
            board[li-j][co+j] = false;
        }
        board[li][co+j] = false;
        if (li+j < n) {
            board[li+j][co+j] = false;
        }
    }
}

// Calcule le nombre de solutions au problème des <N> reines
void nb_sol(int n, bool board_in[n][n], int co, int *ptr_cpt) {
    for (int li=0;li<n;li++) {
        if (board_in[li][co]) {
            if (co < n-1) {
                bool board[n][n];
                prises_devant(n, board_in, board, li, co);
                nb_sol(n, board, co+1, ptr_cpt);
            } else {
                *ptr_cpt = (*ptr_cpt)+1;
            }
        }
    }
}

void main() {
    int n = 8;
    // échiquier où placer les reines
    bool board[n][n];
    board_init(n, board, true);
    // compteur du nombre de solutions au problème des <N> reines
    int cpt = 0;
    nb_sol(n, board, 0, &cpt);
    printf("Nombre de solutions: %d\n", cpt);
}