#백준_9663 N-Queen - Java 자바

# 유형 : 백트래킹

# 난이도 : 골드 V

 

 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p9663 {
    static int N,count;
    static int cols[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        cols = new int[16];
        batch(0);
        System.out.println(count);
    }
    
    public static boolean isPossible(int idx) {
        int tmp = 1;
        boolean rs = true;
        while(tmp<idx && rs) {
            // 같은 행이거나 또는 대각선의 관계를 가질 때 배치할 수 없다.
            if(cols[idx] == cols[tmp] || Math.abs(cols[idx]-cols[tmp]) == idx-tmp)
                rs = false;
            tmp++;
        }
        return rs;
    }
    
    public static void batch(int idx) {
        if(isPossible(idx)) {
            if(idx==N) {
                count++;
            }
            else {
                //행의 값을 넣어가며 배치가 가능한지 확인한다.
                for(int j=1; j<=N; j++) {
                    cols[idx + 1] = j;
                    batch(idx+1);
                }
            }
        }
    }
    
}