문제

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

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

입력

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

출력

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

풀이

해당 문제는 다른 사람의 풀이를 참고하였다.

퀸이 이동하는 위치를 먼저 파악해야한다. -> 상,하,좌,우, 대각선

문제에서 NxN 체스판에 N개의 퀸이 놓일 수 있는 경우의 수를 구하는 문제이다.

따라서 퀸이 이동하는 범위에 다른 퀸이 있으면 안되는 것이다.

함수를 재귀적으로 호출하면서 경우의 수를 구하면 되는데, 반환되는 조건이 N개를 다 채웠을 때 반환하며 그 외에는 재귀적으로 호출하면 된다.

호출할 때 조건은 퀸의 이동 범위를 제외하여 다른 퀸을 놓을 수 있을 때만 호출하면 된다.

즉, 퀸을 놓을수 있는지 판별하는 함수가 필요하다.

일차원 배열을 사용하여 배열의 인덱스는 열 배열의 값(요소)는 행을 의미하여 선언한다.

해당 열(col) 값을 받아서 배열에 해당 열의 행이 존재하는지 먼저 판단한다. 존재하면 false 리턴 존재 하지 않으면 대각선 범위에도 놓일 수 있는지 판별한다. 대각선 범위에 들어오면 false 그 나머지는 true로 반환한다.

소스

import java.util.*;

public class Main {
	public static int[] arr;
	public static int n;
	public static int count = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		arr = new int[n];

		nQueen(0);
		System.out.println(count);

	}

	public static void nQueen(int depth) {
		if (depth == n) {
			count += 1;
			return;
		}

		for (int i = 0; i < n; i++) {
			arr[depth] = i;

			if (possible(depth)) {
				nQueen(depth + 1);
			}
		}
	}

	public static boolean possible(int col) {
		for (int i = 0; i < col; i++) {
			if (arr[col] == arr[i]) {

				return false;
			} else if (Math.abs(col - i) == Math.abs(arr[col] - arr[i])) {
				return false;
			}
		}

		return true;
	}
}