Nqueen문제 (백준 9663 N-Queen & 코드업 3520 체커도전 문제)

www.acmicpc.net/problem/9663

9663번: N-Queen

N-Queen 성공분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

10 초

128 MB

32140

17417

11439

53.788%

문제

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

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

입력

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

출력

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

예제 입력 1 복사

8

예제 출력 1 복사

92

#include <iostream>
using namespace std;

int board[16];
int cnt;

void	print_board(int n)
{
	for (int i = 0; i < n; i++)
		cout << board[i] << " ";
	cout << "\n";
}

int		is_attackable(int lev, int n)
{
	int nowy = board[lev];
	int nowx = lev;

	//print_board(n);
	for (int i = 0; i < lev; i++)
	{
		if (board[i] == nowy)
			return (1);
		if ((board[i] + i) == (nowy + nowx))
			return (1);
		if ((board[i] - i) == (nowy - nowx))
			return (1);
	}
	return (0);
}

void	nqueen(int lev, int n)
{

	if (lev == n)
	{
		cnt++;
		return ;
	}
	for (int i = 0; i < n; i++)
	{
		board[lev] = i;
		if (is_attackable(lev, n) == 0)
			nqueen(lev + 1, n);
	}
}

int main(void)
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
		board[i] = -1;
	cnt = 0;
	nqueen(0, n);
	cout << cnt;
}

www.codeup.kr/problem.php?id=3520

체커 도전 (N-Queen Problem)

문제 설명    내 문제집에 추가 내소스1

체스에서 퀸(queen)은 가로, 세로, 대각선에 같은 퀸을 배치하지 못한다.

각 체커는 각 행에 1개, 각 열에 1개씩 밖에 배치할 수 없다. 

6*6체커보드에서 6개의 체커들은 다음과 같이 퀸을 배치할 수 있다.

 

이 상태의 열 번호는 2 4 6 1 3 5로 나타낼 수 있다.

체스판의 크기가 N이 주어질 때, 퀸을 놓을 수 있는 모든 배치의 개수를 구하시오.

입력

체스판의 크기 N이 입력된다( 6 <= N <= 13 )

출력

처음 세 줄은 가능한 해법 3가지를 출력한다. 이때 열번호가 적은 순서부터 오름차순으로 세 가지만 출력한다.

네째 줄에 가능한 퀸의 배치 개수를 출력한다.

입력 예시   예시 복사

6

출력 예시

2 4 6 1 3 5

3 6 2 5 1 4

4 1 5 2 6 3

4

 

#include <iostream>
using namespace std;

int board[16];
int cnt;
int ptnum;

void	print_board(int n)
{
	for (int i = 0; i < n; i++)
		cout << board[i] + 1 << " ";
	cout << "\n";
}

int		is_attackable(int lev, int n)
{
	int nowy = board[lev];
	int nowx = lev;

	for (int i = 0; i < lev; i++)
	{
		if (board[i] == nowy)
			return (1);
		if ((board[i] + i) == (nowy + nowx))
			return (1);
		if ((board[i] - i) == (nowy - nowx))
			return (1);
	}
	return (0);
}

void	nqueen(int lev, int n)
{

	if (lev == n)
	{
		cnt++;
		if (ptnum-- > 0)
			print_board(n);
		return ;
	}
	for (int i = 0; i < n; i++)
	{
		board[lev] = i;
		if (is_attackable(lev, n) == 0)
			nqueen(lev + 1, n);
	}
}

int main(void)
{
	int n;
	cin >> n;

	ptnum = 3;
	cnt = 0;
	nqueen(0, n);
	cout << cnt;
}

 print board  function used here!!