<백준 알고리즘> 9663번: N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1

8

예제 출력 1

92

---

Solution

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

int abs(int N)
{
	return N<0?-N:N;
}

int queen(int *board,int current,int N)
{
	int count=0, *temp=calloc(N,sizeof(int));

	if(current==N)
	{
		free(temp);
		return 1;
	}

	for(int i=0;i<current;i++)
		temp[i]=board[i];

	for(int n=0;n<N;n++)
	{
		bool flag=true;

		for(int i=0;i<current;i++)
			if(board[i]==n || current-i==abs(n-board[i]))
			{
				flag=false;
				break;
			}

		if(flag)
		{
			temp[current]=n;
			count+=queen(temp,current+1,N);
		}
	}

	free(temp);
	return count;
}

int main(void)
{
	int N, *board=NULL;

	scanf("%d", &N);
	board=(int *)calloc(N,sizeof(int));

	printf("%d\n", queen(board,0,N));
	free(board);
	return 0;
}