標準9663,N-Queen-BackTracking

import java.io.*;

public class Main_Promising {
	static int n;						// n x n 행렬, n개 퀸 (1 ~ 14)
	static int[] col;					// 각 행에 배치한 퀸의 열 위치
	static int count;					// 출력: 가능한 경우의 수

	static void solution(int depth) {
		if (depth == n) {				// 마지막 행까지 확인한 경우
			count++;
			return;
		}

		// 한 행 확인
		for (int i = 0; i < n; i++) {
			col[depth] = i;				// [depth][i] 에 퀸 배치
			if (isPromising(depth))		// 퀸 배치 후 promising 한 경우, 다음 행 탐색
				solution(depth + 1);
		}
	}

	/* 배치한 depth 행의 퀸이 promising 한지 판단 - 이전 윗 행들의 퀸과 비교 */
	static boolean isPromising(int depth) {
		for (int i = 0; i < depth; i++) {
			if (col[i] == col[depth])			// 같은 열인지 확인
				return false;
			if ((depth - i) == Math.abs(col[depth] - col[i]))		// 같은 대각선 상인지 확인
				return false;
		}

		return true;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);

		n = Integer.parseInt(br.readLine());
		col = new int[n];

		if (n == 1) {
			System.out.println(1);
			return;
		}
		else if (n == 2) {				// n = 2 인 경우, 퀸 배치 불가
			System.out.println(0);
			return;
		}

		solution(0);
		System.out.println(count);
	}
}