n-皇后 ii__牛客网

JacobGo！

跟N-Queen类似，但是该题只要返回解的个数即可，相对来说简单一点。

详细的解答可以参考N-Queen问题

链接：https://www.nowcoder.com/questionTerminal/c77ac599d0764433a5946610a7626768?toCommentId=1439159

public class Solution {
    
    private int res;

    private boolean[] col;
    private boolean[] dia1;
    private boolean[] dia2;

    public int totalNQueens(int n) {
        if (n == 0)
            return res;
        col = new boolean[n];
        dia1 = new boolean[2 * n - 1];
        dia2 = new boolean[2 * n - 1];

        putQueen(n, 0);

        return res;
    }

    private void putQueen(int n, int index) {
        if (index == n) {
            res++;
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]) {
                col[i] = true;
                dia1[index + i] = true;
                dia2[index - i + n - 1] = true;

                putQueen(n, index + 1);

                col[i] = false;
                dia1[index + i] = false;
                dia2[index - i + n - 1] = false;
            }
        }
    }
}

发表于 2018-06-10 11:27:15 回复(0)

C/C++

卷积神经网络哦

经典的回溯法

题目没说最大n能给多少但是1s限制内回溯法极限通常在n=11 所以开一个13大的数组绝对够了。。。

从第一行开始往下放，cur代表当前行数每次放的时候只需要注意当前列、当前主、副对角线是否被占用即可。

vis[0][i]表示第i列是否被占
vis[1][i+j]表示副对角线是否被占

vis[2][i-j+n]表示主对角线是否被占

这样可以在O(1)时间内判断某个位置是否能放皇后

    int vis[3][2 * 13], res;
    void dfs(int cur, int n){
        if(cur == n) {res++; return;}
        for(int i = 0; i < n; i++){
            if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n]){
                vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1;
                dfs(cur+1, n);
                vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0;
            }
        }
    }
    int totalNQueens(int n) {
        memset(vis, 0, sizeof(vis));
        res = 0;
        search(0, n);
        return res;
    }

编辑于 2019-07-05 20:31:13 回复(2)

C/C++

nbgao

class Solution {
public:
	int count = 0;
	int x[9];
    int totalNQueens(int n) {
        backtrack(1,n);
        return count;
    }
    
    void backtrack(int t,int n)
    {
    	if(t>n)
    		count++;
    	else{
    		for(int i=1;i<=n;i++)
    		{
    			x[t] = i;
    			if(place(t))
    				backtrack(t+1,n);
			}
		}
	}
	bool place(int t)
	{
		for(int i=1;i<t;i++)
			if(abs(x[t]-x[i]) == abs(t-i) || x[t] == x[i])
				return false;
		return true;
	}
};

发表于 2017-08-04 01:44:00 回复(1)

...王嘉廉睿

public class Solution {
    int sum=0; 
    int[] x;
    public int totalNQueens(int n) {  
        x = new int[n+1];
        backtrack(1,n);//回溯算法开始，第一个皇后放下
        return sum;
    }
    void backtrack(int t,int num){
        if(t>num) //num为皇后的数目
            sum++;//sum为所有的可行的解
        else{
            for(int i = 1;i<=num;i++){//每个皇后都遍历所有点,O(n2)
            	x[t] = i;//寻找这个皇后可以放置的所有点
                if(place(t)) 
                    backtrack(t+1,num);//如果成立，进入下一级递归，放下一个皇后
            }    			//如果不成立，放其他位置，若都无法放，跳回上级递归  
        }
    }
    boolean place(int k){
        for(int j = 1;j<k;j++)
            if(Math.abs(x[k] - x[j]) == Math.abs(k-j)||x[j] == x[k])
            	return false;
        return true;
    }
}

发表于 2016-10-25 15:01:20 回复(1)

潘多拉Boot

class Solution {
public:
    int totalNQueens(int n) {
        int res=0;
        vector<string> cur(n, string(n, '.')); // 初始化棋盘，所有的位置都没有摆放皇后
        dfs(cur, n, 0,res);
        return res;
    }
    void dfs(vector<string> &cur, int &n, int row,int &res) {
        if (row == n) { // 当当前行数超出了棋盘，则把这次搜索的结果放入res中。
           res++;
            return;
        }
        for (int j = 0; j < n; j++) {
            if (isValid(cur, n, row, j)) { // 判断在(row, j)处是否可以放一个皇后
                cur[row][j] = 'Q'; // 如果可以，则放一个皇后
                dfs(cur, n, row + 1,res); // 继续在下一行找一个位置放皇后
                cur[row][j] = '.'; // 因为需要找到所有可能的情况，所以必然需要对每一行进行回退。去判断这一行的下一列是否可以放皇后。
            }
        }
    }
    bool isValid(vector<string> &cur, int &n, int row, int col) {
                                                           //因为是一行放一个皇后，所以不用检查行
        // 检查列
        for (int i = 0; i < row; i++) {
            if (cur[i][col] == 'Q') {
                return false;
            }
        }
        // 检查反斜线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (cur[i][j] == 'Q') {
                return false;
            }
        }
        // 检查斜线
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (cur[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
};

发表于 2018-05-07 12:17:02 回复(0)

C++

勇敢牛牛，不怕困难！

class Solution {
public:
  int totalNQueens(int n) {
    ans_ = cols_ = diag1_ = diag2_ = 0;
    DFS(0, n);
    return ans_;
  }
  
private:
  int ans_, cols_, diag1_, diag2_;
  
  bool available(int x, int y, int n) {
    return !(cols_ & 1 << x || 
             diag1_ & 1 << (x + y) || 
             diag2_ & 1 << (n - 1 + x - y));
  }
  
  void DFS(int y, int n) {
    if (y == n) {
      ++ans_;
      return;
    }
    for (int x = 0; x < n; ++x) {
      if (not available(x, y, n)) continue; 
      cols_ |= 1 << x;
      diag1_ |= 1 << (x + y);
      diag2_ |= 1 << (n - 1 + x - y);
      
      DFS(y + 1, n);
      
      cols_ -= 1 << x;
      diag1_ -= 1 << (x + y);
      diag2_ -= 1 << (n - 1 + (x - y));
    }
  }
};

发表于 2021-10-07 11:40:43 回复(0)

llch__

    int count;
    public int totalNQueens(int n) {
        count = 0;
        boolean col[] = new boolean[n+1];    //列
        boolean tip1[] = new boolean[n*2+1]; //右对角斜线 2~2n
        boolean tip2[] = new boolean[n*2+1]; //左对角斜线 2~2n
        nQueens(n, 1, col, tip1, tip2);
        return count;
    }
    public void nQueens(int n, int cou, boolean col[], boolean tip1[], boolean tip2[]){
        if(cou > n){
            count++;
            return;
        }
        for(int i=1; i<=n; i++){
            if(!col[i] && !tip1[cou+i] && !tip2[n-cou+1+i]){
                col[i] = true;
                tip1[cou+i] = true;
                tip2[n-cou+1+i] = true;
                nQueens(n, cou+1, col, tip1, tip2);
                col[i] = false;
                tip1[cou+i] = false;
                tip2[n-cou+1+i] = false;
            }
        }
    }

发表于 2018-07-28 15:58:46 回复(0)

xinshouhuangfang

class Solution {
public:
    void f(int &cnt, int a[], int n, int level){
        if(level==n){cnt++;return;}
        for(int i=0;i<n;i++){
            int j=0;
            for(;j<level;j++){
                if(a[j]==i || level-j==i-a[j] || j-level==i-a[j])break;
            }
            if(j==level){
                a[level]=i;
                f(cnt,a,n,level+1);
            }
        }
    }
    int totalNQueens(int n) {
        int a[n];
        int cnt=0;
        f(cnt, a,n,0);
        return cnt;
    }
};

发表于 2018-07-26 00:27:37 回复(0)

微软内推小王子

class Solution(object):
    def solve(self, n, i, m, l0, l1, l2):
        if i == n:
            return [m[:]]
        res = []
        for j in range(n):
            if j not in l0 and i + j not in l1 and j - i not in l2:
                m.append(j)
                l0[j] = 1
                l1[i + j] = 1
                l2[j - i] = 1
                res.extend(self.solve(n, i + 1, m, l0, l1, l2))
                m.pop()
                l0.pop(j)
                l1.pop(i + j)
                l2.pop(j - i)
        return res

    def totalNQueens(self, n):
        res = self.solve(n, 0, [], {}, {}, {})
        return len(res)

发表于 2017-10-07 19:14:29 回复(0)

Java

城市里的养猫者

/**
 * don't need to actually place the queen,
 * instead, for each row, try to place without violation on
 * col/ diagonal1/ diagnol2.
 * trick: to detect whether 2 positions sit on the same diagnol:
 * if delta(col, row) equals, same diagnol1;
 * if sum(col, row) equals, same diagnal2.
 */
private final Set<Integer> occupiedCols = new HashSet<Integer>();
private final Set<Integer> occupiedDiag1s = new HashSet<Integer>();
private final Set<Integer> occupiedDiag2s = new HashSet<Integer>();
public int totalNQueens(int n) {
    
    return totalNQueensHelper(0, 0, n);
}

}
private int totalNQueensHelper(int row, int count, int n) {
    
    for (int col = 0; col < n; col++) {
        
        if (occupiedCols.contains(col))
            
            continue;
        
        int diag1 = row - col;
        
        if (occupiedDiag1s.contains(diag1))
            
            continue;
        
        int diag2 = row + col;
        
        if (occupiedDiag2s.contains(diag2))
            
            continue;
        
        // we can now place a queen here
        if (row == n-1)
            
            count++;
        
        else {
            occupiedCols.add(col);
            occupiedDiag1s.add(diag1);
            occupiedDiag2s.add(diag2);
            
            occupiedCols.add(col);
            occupiedDiag1s.add(diag1);
            occupiedDiag2s.add(diag2);
            count = totalNQueensHelper(row+1, count, n);
            
            // recover
            occupiedCols.remove(col);
            occupiedDiag1s.remove(diag1);
            occupiedDiag2s.remove(diag2);
        }
    }
    
    return count;
}
}

发表于 2017-03-12 12:45:17 回复(0)

C/C++

华科不平凡

回溯法，以行为基准进行回溯，如果当前行列摆放皇后与之前的冲突，则不继续回溯，否则，继续下一行的回溯。

代码如下：

//
// Created by jt on 2020/9/29.
//
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param n int整型
     * @return int整型
     */
    int totalNQueens(int n) {
        // write code here
        int res = 0;
        vector<int> vec;
        backtrack(vec, res, n);
        return res;
    }

    void backtrack(vector<int> &vec, int &res, int n) {
        if (vec.size() == n) { ++res; return; }
        for (int col = 0; col < n; ++col) {
            vec.push_back(col);
            if(!detectConflict(vec)) backtrack(vec, res, n);
            vec.pop_back();
        }
    }

    bool detectConflict(vector<int> &vec) {
        int curRow = vec.size() - 1, curCol = vec[curRow];
        for (int row = 0; row < curRow; ++row) {
            if (curCol == vec[row]) return true;
            if (curRow - row == abs(curCol - vec[row])) return true;
        }
        return false;
    }
};

发表于 2020-09-29 17:32:46 回复(0)

Java

牛客89636334号

参考了讨论区的代码~

    public int totalNQueens (int n) {
        // write code here
        int res = 0;
        int[] col = new int[n];  //一行只有一个，只需要记录该列皇后位置
        int[] leftLine = new int[2 * n - 1]; //从左往右方向的对角线，当同一个对角线和相同
        int[] rightLine = new int[2 * n - 1]; //从右往左方向的对角线,同一个线r1-r2==l1-l2,或者保证索引为正数是(n-1)-(r1-l1)==(n-1)-(r2-l2)

        res = queen(0, n, res, col, leftLine, rightLine);
        return res;
        
    }
        public  int queen(int restCol, int n, int res, int[] col, int[] leftLine, int[] rightLine) {
        if (restCol == n) {
            res++;
            return res;
        }
        for (int restRaw = 0; restRaw < n; restRaw++) {
            if (col[restRaw] == 0 && leftLine[restRaw + restCol] == 0 && rightLine[n - 1 - restRaw + restCol] == 0) {
                col[restRaw] = 1;
                leftLine[restRaw + restCol] = 1;
                rightLine[n - 1 - restRaw + restCol] = 1;

                res = queen(restCol + 1, n, res, col, leftLine, rightLine);

                col[restRaw] = 0;
                leftLine[restRaw + restCol] = 0;
                rightLine[n - 1 - restRaw + restCol] = 0;
            }
        }
        return res;
    }

发表于 2020-09-23 18:53:13 回复(0)

Charon2333

class Solution:

    res = 0
    def totalNQueens(self , n):
        self.row = [0]*n
        self.dig1 = [0]*(2*n-1)
        self.dig2 = [0]*(2*n-1)
        self.dfs(n,0)
        return self.res

    def dfs(self,n,step):
        if n == step:
            self.res += 1
            return
        for i in range(n):
            if not self.row[i] and not self.dig1[step - i] and not self.dig2[i+step]:
                self.row[i],self.dig1[step - i],self.dig2[i+step] = 1,1,1
                self.dfs(n,step+1)
                self.row[i],self.dig1[step - i],self.dig2[i+step] = 0,0,0

发表于 2020-07-28 22:40:09 回复(0)

iMi丶

    int[] xMark;
    int result = 0;
    public int totalNQueens (int n) {
        // write code here
        if(n == 0){
            return 0;
        }
        //该数据用于记录每一列对应的皇后所在行
        xMark = new int[n];
        
        putQueen(0,n);
        return result;
    }
    
    public void putQueen(int cur,int queenNums){
        //遍历到尾
        if(cur == queenNums){
            result++;
        }else{
            //这里循环用于遍历cur列皇后放置在某一行的情况
            for(int i = 0;i < queenNums;i++){
                //将当前位置填入
                xMark[cur] = i;
                //如果该列能放置，即行/列/正反斜线都符合
                if(place(cur)){
                    //放入成功，进入下一遍历
                    putQueen(cur+1,queenNums);
                }
                //回溯，回溯想法是将xMark[cur]赋值为下一行下标
            }
        }
    }
    
    public boolean place(int cur){
        //这里只用到cur，因为后面的未放置，比较不了
        for(int i = 0;i < cur;i++){
            //第一个==，用于判断正反斜线是否有皇后，利用y2-y1/x2-x1 斜率等于正负1的思想
            //第二个等号用于判断是否出现在同一行
            //两个条件是或关系
            if(Math.abs(xMark[cur] - xMark[i]) == Math.abs(cur - i)
               || xMark[cur] == xMark[i]){
                return false;
            }
        }
        return true;
    }

发表于 2020-07-17 09:14:43 回复(0)

kkk大人

思路：回溯法

因为每一行、每一列必定有一个Queen，对于第 i 行只需判断Queen可放在哪一列

需要判定该列、该正对角线、该负对角线是否被占用

col = new boolean[n];

dia1 = new boolean[2*n-1];

dia2 = new boolean[2*n-1];

对于同一条负对角线的规律：i + j = 固定的数 [0, 2*n-1]

对于同一条正对角线的规律：j - i + n - 1 = 固定的数 [0, 2*n-1]

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    private boolean[] col,dia1,dia2;
    private int res;
    
    public int totalNQueens (int n) {
        // write code here
        col = new boolean[n];
        dia1 = new boolean[2*n-1];
        dia2 = new boolean[2*n-1];        
        
        Queen(0,n);
        return res;
    }
   
    
    void Queen(int k,int n)
    {
        //k表示候选的列数
        if(k==n)  
        {
            res++;
        }
        else
        {
            for(int i=0;i<n;i++)  //第i行
            {
                if(!col[i] && !dia1[i+k] && !dia2[k-i+n-1])
                {
                    col[i]=true;
                    dia1[i+k]=true;
                    dia2[k-i+n-1]=true;
                    
                    Queen(k+1,n);
                    
                    col[i]=false;
                    dia1[i+k]=false;
                    dia2[k-i+n-1]=false;
                }
            }
        }
    }
    
}

发表于 2020-07-12 20:35:06 回复(0)

ponmmains

import java.util.*;

public class Solution {
public int totalNQueens(int n) {
this.n = n;
colArr = new int[n];
getNQueens(0);
return cnt;
}

private int cnt = 0;
private int n;
private int[] colArr;

private void getNQueens(int row) {

if (row == n) {
cnt++;
return;
}

boolean[] flagArr = new boolean[n];
for (int i = 0; i < row; i++) {
flagArr[colArr[i]] = true;
int val = row - i + colArr[i];
if (val >= 0 && val < n)
flagArr[val] = true;
val = i - row + colArr[i];
if (val >= 0 && val < n)
flagArr[val] = true;
}

for (int i = 0; i < n; i++)
if (!flagArr[i]) {
colArr[row] = i;
getNQueens(row + 1);
}
}
}

发表于 2020-05-04 15:58:25 回复(0)

Aiky

创建两个坐标系，一个左上为起点，一个左下为起点，这样用一个值可以确定是哪一斜道

int ans;
    vector<bool>f1, f2, f3;
    void dfs(int n, int I) {
        if (I == n) {
            ans++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!f1[i] && !f2[I + i] && !f3[i + n - I - 1]) {
                f1[i] = 1, f2[I + i] = 1, f3[i + n - I - 1] = 1;
                dfs(n, I + 1);
                f1[i] = 0, f2[I + i] = 0, f3[i + n - I - 1] = 0;
            }
        }
    }
    int totalNQueens(int n) {
        if (n <= 1)return n;
        for (int i = 0; i < n; i++)f1.push_back(0);
        for (int i = 0; i < n + n; i++)f2.push_back(0), f3.push_back(0);

        ans = 0;
        dfs(n, 0);
        return ans;
    }

发表于 2020-03-14 13:33:48 回复(0)

徒手撕代码白手套offer

bool isValid(vector<string> &temp, int row, int col, int &n) {
		for (int i = row - 1; i >= 0; --i) {
			if (temp[i][col] == 'Q') return false;
		}
		for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
			if (temp[i][j] == 'Q') return false;
		}
		for (int i = row - 1, j = col + 1; i >= 0 && j<n; --i, ++j) {
			if (temp[i][j] == 'Q') return false;
		}
		return true;
	}
	void dfs(int &cnt, vector<string> &temp, int row, int &n) {
		if (row == n) {
			cnt++;
			return;
		}
		for (int j = 0; j<n; ++j) {
			if (isValid(temp, row, j, n)) {
				temp[row][j] = 'Q';
				dfs(cnt, temp, row + 1, n);
				temp[row][j] = '.';
			}
		}
	}
    int totalNQueens(int n) {
        int cnt=0;
        vector<string> temp(n, string(n, '.'));
        dfs(cnt, temp, 0, n);
        return cnt;
    }

发表于 2020-03-05 11:51:10 回复(0)

bug生产者

class Solution {
public:
    int arr[100];
    int ans;
    Solution():ans(0){}
    int totalNQueens(int n) {
        for(int i=0;i<n;i++)
         	   getans(n,0,i);
        return ans;
    }
    void getans(int n,int nowrow,int nowcol){
    	
        if(nowrow==n-1&&check(arr,nowrow,nowcol)){
        	ans++;
        }
        else{
        		if(check(arr,nowrow,nowcol)){
					arr[nowrow]=nowcol;
					for(int i=0;i<n;i++)
        				getans(n,nowrow+1,i);
        		}
		}
    }
    bool check(int arr[],int nowrow,int nowcol){
        for(int i=0;i<nowrow;i++){
            if(nowcol==arr[i]||abs(nowrow-i)==abs(nowcol-arr[i]))
                return false;
        }
        return true;
    }
};

发表于 2020-02-15 22:32:05 回复(0)

C/C++

ltaoj

class Solution {
public:
    int totalNQueens(int n) {
        int res = 0;
        vector<int> temp(n);
        solveNQueens(res, temp, 0, n);
        return res;
    }
    
    
    void solveNQueens(int &res, vector<int> &temp, int row, int n) {
        if (row == n) {
            res++;
            return;
        }
        for (int i = 0;i < n;i++) {
            temp[row] = i;
            if (canPlaceQueen(temp, row)) {
                solveNQueens(res, temp, row + 1, n);
            }
        }
    }
    
    bool canPlaceQueen(vector<int> &temp, int row) {
        for (int i = 0;i < row;i++) {
            if (temp[i] == temp[row] || abs(temp[i] - temp[row]) == abs(row - i)) {
                return false;
            }
        }
        return true;
    }
};

发表于 2019-12-04 00:23:17 回复(0)

n-皇后 ii

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题