NC39 题解 | #N皇后问题#

题意分析

• 经典模板题，n皇后问题。给你一张nxn的棋盘。需要往这个棋盘里面放一些棋子。然后需要保证这n个棋子之间不同同行同列和同正反斜线。

• 也就是下图中在同一条线上面的不能同时放置棋子。

思路分析

• 好了，我们现在知道题目意思了，我们可以来说说怎么解这题。首先，我们需要知道如何判断两个位置是否满足题目条件。同一行同一列我们知道可以可以使用两个数组来标识。但是如何处理正对角线和反对角线的情况呢？我们根据上面的图可以知道，对于正和反对角线的情况。这两种线的斜率分别为1和-1.假设有两个点在正斜线上，那么，反斜线同理。所以我们可以将每个点放入一个数组里面。但是对于正斜线的情况，我们发现可能存在负数的情况，为了防止负数的产生，我们可以给这个和加上一个n保证这个数为正数。

• 知道怎么判断之后，我们来说一下怎么遍历所有的情况，那就是回溯算法。我们对这个棋盘进行dfs，我们以x坐标作为dfs的起点，一层一层向下进行递归处理，当我们到了某一层的时候，我们枚举这一层放置的位置的y坐标，如果满足条件，则向下进行递归，然后进行回溯即可。

• DFS回溯的话可以结合我的这张图进行理解。
  

写法一 C++版

• 代码如下
  • 我们需要枚举出n个棋子的所有的排列。所以空间复杂度为O(n!)
  • bool数组需要存储坐标的和，最大需要开到2n，所以空间复杂度为O(n)

class Solution {
public:
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    bool col[16],row[16],pos[30],neg[30];
    int ans=0;
    void dfs(int x,int n){ // x表示此时的横坐标的位置
      //  std::cout<<x<<endl;
        if(x==n+1){
            // 可以成功到达边界，答案累加1
            ans++;
            return;
        }
        for(int i=1;i<=n;i++){  // 枚举纵坐标
            // 如果选的这个位置在同一行，同一列，同一正斜线和同一反斜线，那么就不符合
            //std::cout<<col[i]<<row[x]<<pos[i-x+n]<<neg[i+x]<<endl;
            if(col[i]||row[x]||pos[i-x+n]||neg[i+x]) continue;
            // 此时在(x,i)位置放一个皇后
            col[i]=row[x]=pos[i-x+n]=neg[i+x]=true;
            dfs(x+1,n);
            // 进行回溯
            col[i]=row[x]=pos[i-x+n]=neg[i+x]=false;
        }
    }
    int Nqueen(int n) {
        // write code here
        memset(pos,false,sizeof(pos));
        memset(neg,false,sizeof(neg));
        memset(row,false,sizeof(row));
        memset(col,false,sizeof(col));
        dfs(1,n);
        return ans;
    }
};

写法二 Go语言版

• 代码如下
  • 我们需要枚举出n个棋子的所有的排列。所以空间复杂度为O(n!)
  • bool数组需要存储坐标的和，最大需要开到2n，所以空间复杂度为O(n)

package main

/**
 * 
 * @param n int整型 the n
 * @return int整型
*/

var ans int

func dfs(x, n int,col,row,neg,pos []bool){
    if(x==n){ // x表示此时的横坐标的位置
        ans+=1
        return
    }
    for i:= 1;i<=n;i++ { // 枚举纵坐标
        // 如果选的这个位置在同一行，同一列，同一正斜线和同一反斜线，那么就不符合
        if(col[i]||row[x]||pos[i-x+n]||neg[i+x]) {
            continue
        }else{
            col[i]=true
            row[x]=true
            pos[i-x+n]=true
            neg[i+x]=true
            // 此时在(x,i)位置放一个皇后
            dfs(x+1,n,col,row,neg,pos)
            // 进行回溯
            col[i]=false
            row[x]=false
            pos[i-x+n]=false
            neg[i+x]=false
        }
    }
}
func Nqueen( n int ) int {
    // write code here
    row := make([]bool,n+1)
    col := make([]bool,n+1)
    pos := make([]bool,2*n+1)
    neg := make([]bool,2*n+1)
    dfs(0,n,col,row,neg,pos)
    return ans;
}