[Algorithm] 체스 퀸 배치 구하기

서로를 공격할 수 없도록 퀸을 배치하는 경우의 수를 구하는 문제이다. 

 

백트랙킹 기법을 이용하여 불가능한 경우가 나오면 깊이 탐색을 포기하고 다른 가지를 탐색한다. 

 

퀸의 이동수

int n = 4;
int cnt = 0;
bool col[7] = { false };
bool diag1[7] = { false };
bool diag2[7] = { false };

n은 체스판의 크기, cnt는 경우의 수, col은 체스판의 열, diag1, diag2는 각각 왼쪽, 오른쪽 대각선을 의미한다. 

 

퀸은 같은 행과, 열을 모두 이동할 수 있으므로 체스판의 행과 열에는 하나의 퀸만 올 수 있다. 

 

void search(int y) {
	if (y == n) {
		cnt++;
		return;
	}
	for (int x = 0; x < n; x++) {
		if (col[x] || diag1[x + y] || diag2[x - y + n - 1]) {
			continue;
		}
		col[x] = diag1[x + y] = diag2[x - y + n - 1] = true;
		search(y + 1);
		col[x] = diag1[x + y] = diag2[x - y + n - 1] = false;
	}
}

search 함수를 재귀적으로 호출하면서 배치의 경우의 수를 구한다. 

	if (y == n) {
		cnt++;
		return;
	}

체스판의 끝 열에 도달하면 배치 경우의 수 하나를 찾은 것이므로 cnt를 하나 늘려주고 재귀호출을 종료한다. 

 

	for (int x = 0; x < n; x++) {
		if (col[x] || diag1[x + y] || diag2[x - y + n - 1]) {
			continue;
		}

해당 위치에 배치가 불가능하다면 continue하고, 

 

		col[x] = diag1[x + y] = diag2[x - y + n - 1] = true;
		search(y + 1);
		col[x] = diag1[x + y] = diag2[x - y + n - 1] = false;

배치가 가능하다면 그 배치로 인해서 배치가 불가능한 구역을 표시(true)해주고 

 

다음 행으로 옮겨가서 재귀함수를 호출한다. 

 

재귀함수 호출 이후에는 배치를 안한 시나리오(false로 바꿔줌)도 고려해서 반복문을 진행한다. 

 

int main() {
	search(0);
	cout << cnt;
	return cnt;
}