[Backtracking 예제] 백준 9663 N-Queens

문제 

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

---

N*N 배열을 만들 필요없이, 크기가 N인 일차원 배열을 만든 후 각 열에 몇번째 행에 퀸이 있는지를 저장한다.

 

#include <iostream>
#define MAX 15
using namespace std;
int N;
int map[MAX];
int ans = 0;
bool promising(int i) {//i번째 퀸과 1~i-1번째 퀸과 비교한다
	int k = 1;//i번째 퀸을 배치하기 전의 퀸 
	bool check = true;

	while (k<i && check)
	{
		if (map[i] == map[k] || abs(map[i] - map[k]) == i - k)
			check = false; 
		//이전의 k퀸과 현재 i퀸이 조건에 맞지 않는 경우, while(check)조건으로바로빠져나간다.
	
		k++;
	}
	return check;
}



int queens(int i) {//queens(i)  :  i번째 퀸을 배치했다 
	int j = 0;

	if (promising(i)) {
		if (i == N)//이제 N행까지 다 배치한 상황
			ans++;
		else {
			for (j = 1; j <= N; j++) {
				map[i + 1] = j;//i+1 행에서 1~N 중 하나에 배치를 한다.
				queens(i + 1);//그다음 행을 배치한다
			}
		}
	}


	return 0;
}

int main() {
	cin >> N;
	queens(0);
	cout << ans;
	return 0;
}