public class _52 {
    static class Solution1 {
        public int totalNQueens(int n) {
            // 9 * 9 = 81;
            //一行一行地放,
            boolean[][] chessboard = new boolean[n][n];
            return dfs(chessboard, 0, n);
        }

        public int dfs(boolean[][] chessboard, int step, int num) {
            if (num == 0) return 1;
            if (step >= chessboard.length * chessboard.length) return 0;
            int i = step / chessboard.length;
            int j = step % chessboard.length;
            int res = dfs(chessboard, step + 1, num);
            if (test(chessboard, i, j)) {
                chessboard[i][j] = true;
                res += dfs(chessboard, step + 1, num - 1);
                chessboard[i][j] = false;
            }
            return res;

        }

        private boolean test(boolean[][] chessboard, int i, int j) {
            //皇后的攻击范围八方
            int[][] dirs = {
                    {-1, -1},
                    {1, 1},
                    {1, -1},
                    {-1, 1},
                    {0, 1},
                    {0, -1},
                    {1, 0},
                    {-1, 0}
            };
            if (chessboard[i][j]) return false;
            int n = chessboard.length;
            for (int[] dir : dirs) {
                int r = i + dir[0];
                int c = j + dir[1];
                for (; r < n && c < n && r >= 0 && c >= 0; r += dir[0], c += dir[1]) {
                    if (chessboard[r][c]) return false;
                }
            }
            return true;
        }
    }

    static class Solution2 {
        //按照行来摆，只需要记录列和对角线能不能被攻击到
        boolean[] col;
        boolean[] x1;//45度对角线
        boolean[] x2;//-45度对角线
        int count = 0;

        public int totalNQueens(int n) {
            col = new boolean[n];
            x1 = new boolean[n * 2];
            x2 = new boolean[n * 2];
            return dfs(0, n);
        }

        public int dfs(int i, int n) {
            if (i == n) {
                return 1;
            }
            int res = 0;
            for (int j = 0; j < n; j++) {
                if (col[j] || x1[i + j] || x2[i - j + n]) continue;
                col[j] = true;
                x1[i + j] = true;
                x2[i - j + n] = true;
                res += dfs(i + 1, n);
                col[j] = false;
                x1[i + j] = false;
                x2[i - j + n] = false;
            }
            return res;
        }
    }

}