N皇后问题II

快来打我* 2022-05-17 06:24 181阅读 0赞

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

求解：给定一个整数 n，返回 n 皇后不同的解决方案的数量。

前面我写过 n皇后问题算法，链接如下：

> n皇后问题：[https://blog.csdn.net/annotation\_yang/article/details/81462959][https_blog.csdn.net_annotation_yang_article_details_81462959]

n皇后问题II 的算法思想和n皇后问题是类似的，但是相对更加简单，不需要使用复杂的数据结构。可以先阅读我的其中一篇文章，然后去独立做另一个，不会做的话在看另一篇找思路，巩固算法思想。

示例如下：

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

具体算法如下：

class Solution { 
    
        private int res;
        private boolean[] col;
        private boolean[] dia1;
        private boolean[] dia2;
    
        public int totalNQueens(int n) {
            if(n < 1)
                return 1;
    
            col = new boolean[n];
            dia1 = new boolean[2*n-1];
            dia2 = new boolean[2*n-1];
    
            putQueue(n, 0);
            return res;
        }
    
        // n 皇后问题中，寻找第index行皇后所在位置
        private void putQueue(int n, int index){
    
            if(index == n){
                res ++;
                return ;     
            }
    
            for(int i=0; i<n; i++)
                if( !col[i] && !dia1[i+index] && !dia2[i-index+n-1]){
                    col[i] = true;
                    dia1[i+index] = true;
                    dia2[i-index+n-1] = true;
                    putQueue(n, index+1);
                    col[i] = false;
                    dia1[i+index] = false;
                    dia2[i-index+n-1] = false;
                }     
            return ;
        }
    }

[https_blog.csdn.net_annotation_yang_article_details_81462959]: https://blog.csdn.net/annotation_yang/article/details/81462959