パドック法による8クイーン

#include < stdio.h >
#include < stdlib.h >
#include < string.h >

#define SUCCESS 1
#define FAIL 0

#define FREE 1
#define NOT_FREE 0

#define N 8

int pos[N];

int col[N];

int down[2 * N - 1];

int up[2 * N - 1];

void init_board()
{
    int i;
    for (i = 0; i < N; i++)
        pos[i] = -1;
    for (i = 0; i < N; i++)
        col[i] = FREE;
    for(i = 0; i < 2 * N - 1; i++)
        down[i] = FREE;
    for (i = 0; i< 2 * N -1; i++)
        up[i] = FREE;
}
void print_queens()
{
    int i, j;
    
    for(i = 0; i < N; i++){
        for(j = 0; j < N; j++){
            if(pos[i] == j)
                printf("Q ");
            else
                printf(". ");
        }
        printf("\n");
    }
    printf("\n");
}

int try(int a)
{
    int b;
    
    for (b = 0; b < N; b++){
        pos[a] = b;
        col[b] = NOT_FREE;
        up[a + b] = NOT_FREE;
        down[a - b + (N-1)] = NOT_FREE;
        
        if(a + 1 >= N)
            return SUCCESS;
        else {
            if(try(a + 1) == SUCCESS)
                return SUCCESS;
            else {
                pos[a] = -1;
                col[b] = FREE;
                up[a + b] = FREE;
                down[a-b + (N-1)] = FREE;
            }
        }
    }

return FAIL;
}

main()
{
    init_board();
    
    if(try(0) == SUCCESS)
        print_queens();
    else
        printf("Sorry, but there is no solution.\n");
}