[BOJ 9663] N-Queen (C++)

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

9663번: N-Queen

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

int board[16];
int answer = 0;

bool promising(int col, int row) { //board[col]=row
	for (int i = 1; i <= col - 1; i++) {
		if (board[i] == row || abs(col - i) == abs(row - board[i]))	
			return false;
	}
	return true;
}


void backtracking(int col, int cnt, int N) {
	if (cnt == N) {
		answer++;
		return;
	}
	for (int j = 1; j <= N; j++) {
		if (promising(col, j)) {
			board[col] = j;
			backtracking(col + 1, cnt + 1, N);
			board[col] = 0;
		}
	}
	
}

int main() {
	int N;
	memset(board, 0, sizeof(board));
	cin >> N;
	backtracking(1, 0, N);
	cout << answer << "\n";
	return 0;
}

backtracking 문제.

바로 그 유명한 N-Queens puzzle이다.

 

열 단위로 움직여간다.

한 열에 한 말만 놓을 수 있으므로, 1차원 배열로 풀이가능하다.

첫번째 열부터 놓아주면서, 끝 열까지(N번째 열) 이동하면서 유망성을 체크한 후 재귀로 탐색한다.

유망성을 체크할때는 1열부터 자기 이전 열까지 체크하면서, 같은 행에 위치한 말이 있는지 또는 동일 대각선상에 위치한 말이 있는지 체크한다.