力扣LeetCode #52 N皇后II（TotalNQueens）

- 题目描述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数 n，返回 n 皇后不同的解决方案的数量。

提示： 皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一或 N-1 步，可进可退。

- 示例

输入: 4 输出: 2 解释: 4 皇后问题存在如下两个不同的解法。 [ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”], ["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”] ]

- 思路分析

解法思路见。这道题对比51来说相对更简单，因为不用考虑将矩阵输出。

- JAVA实现

class Solution {
          
   
    public int totalNQueens(int n) {
          
   
        int[][] matrix = new int[n+1][n+1];
        int[] columns = new int[n+1];
        int[] slopes_btm = new int[2*n];   //1~2n-1对应从左下到右上的斜线
        int[] slopes_up = new int[2*n];   //1~2n-1对应从左上到右下的斜线
        for(int i=0;i<2*n;i++) {
          
   
            slopes_btm[i] = 0;
            slopes_up[i] = 0;
        }
        for(int i=0;i<n+1;i++) {
          
   
            columns[i] = 0;
            for(int j=0;j<n+1;j++) {
          
   
                matrix[i][j] = 0;
            }
        }
        return Queen(matrix, columns, slopes_btm, slopes_up, 1, 0);   //k:准备放第k个，还没有放
    }

    public int Queen(int[][] matrix, int[] columns, int[] slopes_btm, int[] slopes_up, int k, int ans) {
          
   
        if(k==matrix.length) {
          
   
            return ans+1;
        }
        else {
          
   
            int n = matrix.length-1;
            for(int j=1;j<n+1;j++) {
          
   
                if(columns[j] == 0) {
          
   
                    int slop_btm = 0, slop_up = 0;
                    slop_btm = k>=j ? n-(k-j) : n+j-k;
                    slop_up = k+j-1;
                    if(slopes_btm[slop_btm] == 0 && slopes_up[slop_up] == 0) {
          
     //说明找到一个满足的位置
                        columns[j] = 1;
                        slopes_btm[slop_btm] = 1;
                        slopes_up[slop_up] = 1;
                        matrix[k][j] = 1;
                        ans = Queen(matrix, columns, slopes_btm, slopes_up, k+1, ans);
                        columns[j] = 0;
                        slopes_btm[slop_btm] = 0;
                        slopes_up[slop_up] = 0;
                        matrix[k][j] = 0;
                    }
                }
            }
        }
        return ans;
    }
}