nqueen 알고리즘

#include <stdio.h>

#include <math.h>

int queenArr[16];

int N;

int cnt = 0;

int promising(int level){

for (int i = 1; i < level; i++){

//이전에 놓인 퀸과 같은 열에 있을 경우

if (queenArr[i] == queenArr[level])

return 0;

//이전에 놓인 퀸과 같은 대각선에 있을 경우

if (abs(i - level) == abs(queenArr[i] - queenArr[level]))

return 0;

}

return 1;

}

void queen(int level)

{

if (!promising(level)){ //promising 하지 않는다면 종료

return;

}

else if (N == level){//queen을 N개 전부 넣었다면

cnt++;

//퀸이 놓인 위치 출력

for (int i = 1; i <= N; i++){

printf(" %d", queenArr[i]);

}

printf("\n");

}

else{//모든 행에 퀸을 놓는다.

for (int i = 1; i <= N; i++){

queenArr[level + 1] = i;

queen(level + 1);

}

}

}

int main()

{

printf("N : ");

scanf("%d", &N);

queen(0);

printf("%d : %d\n", N, cnt);

return 0;

}