Untitled


#include <stdio.h>
#include <math.h>
#define MAXCANDIDATES 100
#define NMAX 100

typedef int data;
enum {FALSE, TRUE};

bool finished;
int  solution_count = 0;

int is_a_solution(int a[], int k, int n)
{
        return (k==n);
}

void construct_candidates(int a[], int k, int n, int c[], int* ncandidates)
{
          int i, j;            // 카운터 //
        bool legal_move;   // 이동 가능 여부 //

        *ncandidates = 0;
                // 열을 조사
        for(i=1; i<=n; i++)
        {
                        legal_move = true;
                        // 행을 조사
                        for(j=1; j<k; j++)
                        {
                                if( abs( (k) -j ) == abs( i - a[j] ) || i == a[j] ) // 대각선 방향 or 같은 열
                                {
                                        legal_move = false;
                                        break;
                                }
                        }
                        if( legal_move == true )
                        {
                                c[*ncandidates] = i;
                                *ncandidates = *ncandidates + 1;
                        }
                }
}

void process_solution(int a[], int k, int n)
{
        solution_count ++;

        printf("\n");
        for( int i=1 ; i<=n ; i++ )
        {
                for( int j=1 ; j<=n ; j++ )
                {
                        if( a[j] == i)
                                printf("Q");
                        else
                                printf(".");
                }
                printf("\n");
        }
        printf("\n");
}

void backtrack(int a[], int k, data input)
{
        int c[MAXCANDIDATES] = {0,};
        int ncandidates=0;
        int i=0;

        if( is_a_solution(a, k, input) )
        {
                process_solution(a, k, input);
        }
        else
        {
                k++;
                construct_candidates(a, k, input, c, &ncandidates);
                for( i=0 ; i<ncandidates ; i++)
                {
                        a[k] = c[i];
                        backtrack(a, k, input);
                        if( finished ) return;  // 일찍 종료함
                }
        }
}

void generate_subsets(int n)
{
        int a[NMAX];
        solution_count = 0;
        backtrack(a, 0, n);
        printf("n = %d solution_count = %d\n", n, solution_count);
}

int main(void)
{
        generate_subsets(4);

        return 0;
}