N-Queen

import java.util.Scanner;

public class Main {
	static int[][] arr;
	static int N;

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

		N = sc.nextInt();

		arr = new int[N][N];
		checks = new boolean[N];

		int cnt = 0;
		ham(cnt);
		System.out.println(count);
	}

	static int count = 0;
	static boolean[] checks;

	static void ham(int cnt) {
		if (cnt == N) {
			count++;
			return;
		}
		for (int i = 0; i < N; i++) {
			if (checks[i])
				continue;
			boolean check = true;
			for (int k = 0; k < 8; k++) {

				int nr = cnt;
				int nc = i;
				while (true) {
					nr += dr[k];
					nc += dc[k];
					if (nr < 0 || nc < 0 || nr >= N || nc >= N)
						break;
					if (arr[nr][nc] == 1) {
						check = false;
						break;
					}
				}
			}
			if (check) {
				checks[i] = true;
				arr[cnt][i] = 1;
				ham(cnt + 1);
				checks[i] = false;
				arr[cnt][i] = 0;
			}
		}
	}

	static int[] dr = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] dc = { -1, 0, 1, -1, 1, -1, 0, 1 };
}