BOJ 9663

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

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

import java.io.BufferedReader;
import java.io.InputStreamReader;


public class Main {
    static int answer,N;
    static int[] arr;
    static boolean []used;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        used = new boolean[N];
        nQueens(0);
        System.out.println(answer);
    }

    private static void nQueens(int idx){
        if(idx==N){
            answer++;
            return;
        }

        for(int i =0; i<N; i++){
            if(used[i])continue;//사용한 숫자면 컨티뉴

            boolean flag=false;
            for(int j=0; j<idx; j++){
                if(Math.abs(arr[j]-i)==idx-j){
                    flag=true;
                    break;
                }
            }
            //flag가 true면 기울기가 같아서 같은 대각선상에 위치
            if(flag)continue;

            used[i]=true;
            arr[idx]=i;
            nQueens(idx+1);
            used[i]=false;
        }
    }

}