n皇后问题__牛客网

但求八月九月好运！

//不明白为什么超时！！
class Queens {
public:
    int res=0;
    bool check(int row,int col,vector<int>flag){
        int temp;
        for(int i=0;i<row;++i){
            temp=flag[i];
            if(temp==col) return false;
            if(abs(row-i)==abs(col-temp)) return false;
        }
        return true;
    }
    void dfs(int depth,vector<int>pos,int n){
        if(depth==n){
            ++res;
            return ;
        }
        for(int i=0;i<n;++i){
            if(check(depth,i,pos)){
                pos[depth]=i;
                dfs(depth+1,pos,n);
            }
        }
    }
    int nQueens(int n) {
        vector<int>pos(n);
        fill(pos.begin(),pos.end(),0);
        dfs(0,pos,n);
        return res;
    }
};

发表于 2019-08-31 21:29:24 回复(1)

张佃鹏

class Queens {
public:
    int nQueens(int n) {
        // write code here
        int count=0;
        int *a=new int[n+1];
        Queens1(a,1,n,count);
        return count;
        
    }
    void Queens1(int a[],int i,int n,int &count){
        if(i>n){
            count++;
            return ;
        }
        for(int j=1;j<=n;j++){
            a[i]=j;
            if(Place(a,i))
                Queens1(a,i+1,n,count);
        }
    }
    bool Place(int *a,int i){
        for(int j=1;j<i;j++)
            if((a[j]==a[i])||(a[j]-a[i]==(j-i))||(a[j]-a[i]==i-j))
            return 0;
       return 1;
    }
};

发表于 2015-08-06 21:53:14 回复(9)

AKG

思路：运用数组cols[n]保存第n行的皇后位置。

public class Queens {  
    public static int nQueens(int n) {  
        int[] cols = new int[n];  
        int[] num = { 0 };  
        for (int i = 0; i < n; i++) {  
            cols[0] = i;//第一行皇后的位置  
            getCount(cols, 1, num);  
              
        }  
        return num[0];  
    }  
//除了第一行外，每行赋值皇后的位置，并判断位置是否合理，若能成功赋值最后一行
//位置,方法数+1；

    public static void getCount(int[] cols, int row, int[] num) {  
        if (row == (cols.length)) {  
            num[0]++;  
            return;  
        }  
        for (int i = 0; i < cols.length; i++) {  
            if (checkValid(cols, row, i)) {  
                cols[row] = i;  
                getCount(cols, row + 1, num);  
            }  
        }  
  
    }  
// 判断插入的皇后位置是否合理  
    private static boolean checkValid(int[] cols, int row, int col) {  
        for (int i = 0; i < row; i++) {  
            int temp = cols[i];  
            if (temp == col)  
                return false;  
            if (Math.abs(row - i) == Math.abs(temp - col))  
                return false;  
        }  
        return true;  
    }
}

编辑于 2016-08-13 17:17:58 回复(5)

SoyLee

使用了非递归的方法，运用回溯

import java.util.*;

public class Queens {
    public int nQueens(int n) {
        // write code here
		if(n<=0)
			return 0;
		int[] pos = new int[n];
		for (int i=0;i<n;i++)
			pos[i] = Integer.MIN_VALUE;
		int res = 0;
		int i=0,j=0; //i进行行扫描，j进行列扫描
		while (i<n){ //对每行进行扫描
			while(j<n){ //对每列进行扫描
				if (NoClash(i, j, pos)){//如果此位置可以放置一个皇后
					pos[i] = j;
					
					j=0;                //下一行从第一列开始探索
					break;
				}
				else {                  //如果此列不能够放置一个皇后
					j++;
				}
			}
			if (pos[i] == Integer.MIN_VALUE){  //如果此行没有解，进行回溯
				if(i == 0)            //i是第一行了，说明没有解了
					break;
				i--;                  //回到上一行
				j = pos[i]+1;         //j从上一行的原位置+1开始搜索
				pos[i] = Integer.MIN_VALUE;          //清除第i行的皇后
				continue;
			}//if
			else{                     //此行有解
				if(i==n-1){            //在最后的一行找到了位置，即找到了解
					res++;
					j = pos[i] + 1;
					pos[i] = Integer.MIN_VALUE;
					continue;
				}//if
			}
			i++;                //进行下一行探索
		}//while
		return res;
    }
	
	boolean NoClash (int row, int col,int[] chessboard){ //判断皇后是否产生冲突，没有冲突返回true
		for(int i=0;i<chessboard.length;i++){
			if(chessboard[i] == col|| Math.abs(i-row)==Math.abs(chessboard[i]-col)){
				return false;
			}
		} 
		return true;
	}//Clash
}

发表于 2017-06-20 13:51:23 回复(0)

henuacm天仔

用深度搜索，用三个数组col，dpos，dneg分别来表示在列上、在往左下方斜的对角线和右下斜的对角线是否有其他皇后，而dfs的i则表示在第i行放皇后。

class Queens {
public:
    int cnt=0,N;
    bool col[15],dpos[30],dneg[30];
    int nQueens(int n) {
        // write code here
        N=n;
        dfs(0);
        return cnt;
    }
    void dfs(int i)
    {
        if(i==N&&i!=0)//到达最后一行，注意0是特殊数据
        {
            cnt++;//计数
            return;
        }
        for(int j=0;j<N;j++)//在这一行的每一列放皇后
        {
            if(col[j]||dpos[i+j]||dneg[i-j+N-1])continue;//有别的皇后能攻击到就忽略这个位置
            col[j]=dpos[i+j]=dneg[i-j+N-1]=1;//占领这些相应的列和左下对角线和右下对角线
            dfs(i+1);//到下一行
            col[j]=dpos[i+j]=dneg[i-j+N-1]=0;//拿掉这行的皇后，取消相应的占领
        }
    }//运行到这说明该行放置皇后失败，不计数返回
};

发表于 2020-08-18 16:28:31 回复(0)

GreatGeek

import java.util.*;

public class Queens {
    public int nQueens(int n) {
        int[] row = new int[n];
        return process(row,n,0);
    }

    public int process(int[] row,int n, int rowNum){
        int sum = 0;
        if(rowNum==n){
            return 1;
        }
        for(int j=0;j<n;j++){
            if(isValid(row,rowNum,j)){
                row[rowNum]=j;
                sum +=process(row,n,rowNum+1);
            }
        }
        return sum;
    }

    public boolean isValid(int[] row,int x,int y){
        for(int rowNum=0;rowNum<x;rowNum++){
            int col = row[rowNum];
            if(col==y) return false;
            if(Math.abs(rowNum-x)==Math.abs(col-y)) return false;
        }
        return true;
    }
}

发表于 2020-04-29 11:23:52 回复(0)

C/C++

nbgao

class Queens {
public:     int cnt = 0;      bool F(int r, int *cols){         for(int i=0;i<r;i++)             if(cols[i]==cols[r] || abs(cols[i]-cols[r])==abs(i-r))                 return false;         return true;     }
    void DFS(int r, int n, int *cols){
        if(r==n)
            cnt++;
        else{
            for(int i=0;i<n;i++){
                cols[r] = i+1;
                if(F(r,cols))
                    DFS(r+1,n,cols);             }         }     }
    int nQueens(int n) {
        int cols[n],r=0;
        for(int i=0;i<n;i++)
            cols[i] = 0;
        DFS(r,n,cols);
        return cnt;
    }
};

发表于 2019-03-03 02:31:55 回复(0)

C/C++

改造人类offer收割机2号

int nQueens(int n) {
		int ans = 0;
		vector<int> chessBorad(n + 1);
		count(chessBorad, 1, n, ans);
		return ans;
	}
	void count(vector<int> &chessBorad, int row, int n, int &ans) {
		if (row > n) {
			ans++;
			return;
		}
		for (int col = 1; col <= n; col++) {
			chessBorad[row] = col;	//row是行，判断(row,chessBorad[row](== col))位置可否放旗子
			if (place(chessBorad, row)) {	//如果可以放置，就进行下一行的放置，不能就将row行棋子放到下一列
				count(chessBorad, row + 1, n, ans);
			}
		}
	}
	bool place(vector<int> &chessBorad, int currentRow) {
		for (int previousRow = 1; previousRow < currentRow; previousRow++) {	//枚举已放置的前previousRow行，看这一行能否放置
			if (chessBorad[previousRow] == chessBorad[currentRow] || //同一列
				chessBorad[previousRow] - chessBorad[currentRow] == previousRow - currentRow ||	//右对角线
				chessBorad[previousRow] - chessBorad[currentRow] == currentRow - previousRow) {	//左对角线
				return false;	//如果在同一列，右对角线，左对角线则不能放置
			}
		}
		return true;
	}

发表于 2017-06-29 21:22:53 回复(0)

C/C++

牛客9863708号

class Queens {
public:
    
    int total = 0;
    
    int nQueens(int n) {
        
        int temp[n]; // 下标为行，值为列值
        for(int i=0; i<n; i++){
            temp[i] = 0;
        }
        
        int cur = 0;
        calc(n, cur, temp);
        
        return total;
    }
    
    // 
    void calc(int n, int cur, int temp[]){
        
        if(n == cur){
            total++;
        }else{
            for(int i=0; i<n; i++){ // 每一次都可能去每一行
                temp[cur] = i+1;
                if(judge(cur, temp)){
                    calc(n, cur+1, temp); // 这里有回溯的思想
                }
            }
        }
    }
    
    // 判断是否在两条对角线上，是否在同一列中
    bool judge(int cur, int temp[]){
        for(int i=0; i<cur; i++){
            if(temp[i] == temp[cur] || (temp[i]-temp[cur])==(i-cur) || (temp[i]-temp[cur])==(cur-i)){
                return false;
            }
        }
        return true;
    }
};

发表于 2017-05-27 21:23:39 回复(0)

Java

江南消夏

import java.util.*;

public class Queens {
    public int nQueens(int n) {
        if (n<0) return 0;
        // write code here
        int[] record = new int[n];
        return process(0, record, n);
        
    }
    
    private int process(int i, int[] record, int n){
        if (i == n)
            return 1;
        
        int res = 0;
        
        for (int j=0; j<n; j++){
            if (isValid(record, i, j)){
                record[i] = j;
                res += process(i+1, record, n);
            }
        }
        return res;
    }
    
    private boolean isValid(int[] record, int i, int j){
        for (int k=0; k<i; k++){
            // 若在同一列或者对角线则返回false
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(k - i)) return false;
        }
        return true;
    }
}

发表于 2017-01-01 03:50:24 回复(0)

Aurora1

//开辟一维数组记录摆放皇后的位置:
    public int nQueens(int n) {
        this.n = n;
        A = new int[n];
        return f(0);
    }

    int cnt, n, A[];

    int f(int i) {
        if (i >= n) {
            return cnt++;
        }
        for (int j = 0; j < n; j++) {
            A[i] = j;
            if (check(i,j)) {
                f(i+1);
            }
        }
        return cnt;
    }

    boolean check(int x, int y) {
        for (int i = 0; i < x; i++) {
            if (A[i] == y || x- i == Math.abs(y-A[i])) //检查同列和对角线
                return false;
        }
        return true;
    } 

//开辟二维数组记录棋盘,采用回溯法:
    public int nQueens(int n) {
        this.n = n;
        A = new boolean[n][n];
        f(0);
        return cnt;
    }

    int cnt = 0, n;
    boolean A[][];

    void f(int i) {
        if (i >= n) {
            cnt++;
            return;
        }
        for (int j = 0; j < n; j++) {
            A[i][j] = true;
            if (check(i,j)) {
                f(i+1);
            }
            A[i][j] = false;
        }
    }
    //啰嗦一点,需要向四个方向扫描
    boolean check(int x, int y) {
        for (int i = 0; i < n; i++) {
            if (i != x && A[i][y] == true) {
                return false;
            }
        }
        for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) {
            if (A[i][j] == true)
                return false;
        }
        for (int i = x - 1, j = y + 1; i >= 0 && j < n; i--, j++) {
            if (A[i][j] == true)
                return false;
        }
        for (int i = x + 1, j = y - 1; i < n && j >= 0; i++, j--) {
            if (A[i][j] == true)
                return false;
        }
        for (int i = x + 1, j = y + 1; i < n && j < n; i++, j++) {
            if (A[i][j] == true)
                return false;
        }
        return true;
    }

编辑于 2016-09-07 12:05:42 回复(0)

忆水寒

class Queens {
public:
    
    int nQueens(int n) {
        // write code here
        if(n<=0) return 0;
        int* arr=new int[n];
        for(int i=0;i<n;i++)
            arr[i]=i;
        int g_number=0;
        helper(arr,n,0,g_number);
        return g_number;
    }
    void helper(int column[],int length,int index,int& g_number)
    {
        if(index==length)
        {
            if(checkVaild(column,length))
                  g_number++;
        }
        else
        {
            for(int i=index;i<length;i++)
            {
                swap(column[index],column[i]);
                helper(column,length,index+1,g_number);
                swap(column[index],column[i]);
            }
        }
    }
    bool checkVaild(int column[],int length)
    {
        int i,j;
        for(i=0;i<length;i++)
        {
            for(j=i+1;j<length;j++)
            {
                if((i-j==column[i]-column[j])||(j-i==column[i]-column[j]))
                    return false;
            }
        }
        return true;
    }
};

发表于 2016-08-17 21:41:13 回复(1)

简单的快乐

import java.util.*;

public class Queens {

public int nQueens(int n) {

/**

*

* 用一个n长的一维数组来存储数据，下标就是行号，这样就保证了行唯一，然后值就是列中的左边，容易判断

* 最后是判断正负对角线，|row-i|=|col-a[i]| 这样就是元素在一条对角线上

*

*/

//1，使用回溯递归法

int result[]=new int[1];//计数的,下标从1开始，免得麻烦

int value[]=new int[n+1];//值表示列的索引，默认都是0则没有

findQueens(1,n,value,result);

return result[0];

}

/**

* 行号和结果

* @param i

* @param count

*/

public void findQueens(int i,int n,int []value, int[] result) {

int []temp=new int[n+1];//保存值

if(i>n){//一次遍历结束

result[0]++;

/**

* 打印所有的值

*/

/*

for(int i1=1;i1<=n;i1++){

System.out.print(value[i1]);

}

System.out.println("一次查找结束");//打印列位置索引

*/

return;

}

//否则遍历回溯

for(int j=1;j<=n;j++){

value[i]=j;//一维数组存储

if(checkPlace(value, i)){

findQueens(i+1, n, value, result);//继续下一行查找

}

public boolean checkPlace(int []value,int index){

/**

* 检查当前位置是否可放

*/

for(int i=1;i<index;i++){

if(value[i]==value[index]||Math.abs(value[i]-value[index])==Math.abs(i-index))

return false;

}

return true;

}

发表于 2016-06-28 14:50:04 回复(0)

shi_kai

#include <stdio.h>

#include<string.h>

class Queens {

public:

int cnt,n,k;

int vis[3][100];

int num[20]={0}; //={1,0,0,2,10,4,40,92,352,724};

void dfs(int cur,int m)

{

int i;

if(cur==m)

cnt++;

else

for(i=0;i<m;i++)

{

if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+m])

{

vis[0][i]=vis[1][cur+i]=vis[2][cur-i+m]=1;

dfs(cur+1,m);

vis[0][i]=vis[1][cur+i]=vis[2][cur-i+m]=0;

}

int nQueens(int n) {

// write code here

if(num[n]) return num[n];//优化，对于已经找过的点记录值

memset(vis,0,sizeof(vis));//标记

cnt=0;

dfs(0,n);//深搜

num[n]=cnt;//记录，防止重复找

return num[n];

}

};

思路是dfs深搜。

这是vis的标记，来自我的博客：http://www.cnblogs.com/yuyixingkong/p/3251050.html 看不懂可以来我博客提问

发表于 2015-08-18 01:07:35 回复(1)

Cavs

记录每个皇后摆放的位置，每放一个检测是否有冲突

class Queens {
public:
    typedef pair<double, double> Pair;
    int res;

    bool checkAttack(int x, int y, vector<Pair>& place)
    {
        if (place.empty()) return false;
        for (auto& pr : place)
        {
            if (x == pr.first || y == pr.second || abs(x - pr.first) == abs(y - pr.second))
                return true;
        }

        return false;
    }

    void DFS(int n, int level, vector<Pair>& place)
    {
        if (level >= n) ++res;
        for (int i = 0; i < n; ++i)
        {
            if (!checkAttack(level, i, place))
            {
                place.emplace_back(level, i);
                DFS(n, level + 1, place);
                place.pop_back();
            }
        }
    }

    int nQueens(int n) 
    {
        res = 0;
        vector<Pair> place;
        place.reserve(n);
        DFS(n, 0, place);
        return res;
    }
};

发表于 2017-06-28 20:29:32 回复(0)

Python

Yannyezixin

回溯法解8皇后问题：从一条路往前走，能进则进，不能进则退回来，换条路再试

# -*- coding:utf-8 -*-
class Queens:
    def nQueens(self, n):
        result = [0] * n
        results = []
        n_row = 0
        while n_row < n:
            pos = self.findLegalPosition(result, n_row, n)
            # print pos
            if pos is not None:
                result[n_row] = pos
                if n_row == n - 1:
                    results.append(result[:])

            if pos is None or n_row == n - 1:
                while 1:
                    n_row -= 1
                    if n_row < 0:
                        print results
                        return len(results)

                    pos = self.findLegalPosition(result, n_row, n, back_tracing=True)
                    if pos:
                        result[n_row] = pos
                        break
            n_row += 1

    def findLegalPosition(self, arr, n_row, n, back_tracing=False):
        start = 0
        if back_tracing:
            start = arr[n_row] + 1
        for col in range(start, n):
            ok = True
            for row in range(n_row):
                if arr[row] == col:
                    ok = False
                    break
                if n_row - row == abs(col - arr[row]):
                    ok = False
                    break
            if ok:
                return col
        return None

PS：由于Python语言本身的原因和题目的AC时间限制，该题目解法是正确的但是超时

发表于 2016-08-07 13:10:14 回复(0)

枪舞燎原

这个题目是有问题的，皇后问题是不再一条斜线与反斜线，不是对角线

发表于 2016-05-06 10:33:48 回复(5)

C++

好菜啊我

/*
思路：回溯法 深度搜素

n皇后要求：
1.同一行只有一个皇后
判断是否在同一 行：(x1,y1)(x2,y2) 当 x1 == x2 说明在同一 行

2.同一列只有一个皇后
判断是否在同一 列：(x1,y1)(x2,y2) 当 y1 == y2 说明在同一 列

3.同一 撇 只有一个皇后
判断是否在同一 撇：(x1,y1)(x2,y2) 当 x1+y1 == x2+y2 说明在同一 撇

4.同一 捺 只有一个皇后
判断是否在同一 捺：(x1,y1)(x2,y2) 当 x1-y1 == x2-y2 说明在同一 撇


解题方法：
1.遍历数组的每个位置，把当前位置和已知符合要求的坐标进行比较。
2.如果合法：添加当前坐标。否则，放弃该坐标。
3.如果遍历完一行都没有一个合法位置，该策略废弃，回退。

*/

class Queens {
public:
    int result=0;
    //判断该位置是否合法
    bool IsLegal(vector<pair<int,int>>& way,int x,int y){
        for(int i=0;i<way.size();i++){
            //判断是否在同一行 或 同一列
            if((way[i].first == x) || (way[i].second==y)){
                return false;
            }
            //判断是否在统一 捺
            if((way[i].first-way[i].second)==(x-y)){
                return false;
            }
            //判断是否在同一 撇
            if((way[i].first+way[i].second)==(x+y)){
                return false;
            }
        }
        return true;
    }
    //递归搜索函数
    // n：总的皇后数量 index 当前行号
    void DFS(int n,int index,vector<pair<int,int>> way){
        //搜索完毕
        if(n == index){
            return;
        }

        for(int j=0;j<n;j++){
            vector<pair<int,int>> temp = way;
            //判断该位置是否合法
            bool isl = IsLegal(temp,index,j);

            if(isl){
                //位置合法，添加
                temp.push_back(make_pair(index,j));
                
                if(temp.size()==n){
                    //已经存储了n个皇后，该条路径搜索完毕
                    result++;
                    //腾出位置供本行下一个位置使用
                    temp.pop_back();
                }else{
                    //搜索的皇后数量不足，去下一行继续搜索
                    DFS(n,index+1,temp);

                    //腾出位置供本行下一个位置使用
                    temp.pop_back();
                }
            }
        }
    }

    int nQueens(int n) {
        if(n<=1){
            return n;
        }
        vector<pair<int,int>> way;

        DFS(n,0,way);

        return result;

    }
};

发表于 2023-04-11 19:55:46 回复(0)

Java

codewind

import java.util.*;

public class Queens {
    public int nQueens(int n) {
        Op op = new Op();
        op.dfs(0,n);
        return op.result;
    }
    
    
    static class Op{
        boolean[] cols = new boolean[66];
        boolean[] diag = new boolean[66];
        boolean[] cdiag = new boolean[66];
        int result ;
        void dfs(int row,int n) {
            if(row == n) {
                ++result;
                return;
            }
            //尝试
            for(int i=0;i< n;++i) {
                if(cols[i]==false && diag[i+row+n] ==false && cdiag[i-row + n]==false) {
                    //这个列可以放
                     cols[i] = true;
                     diag[i+row+n] = true;
                     cdiag[i-row +n] = true;
                     dfs(row+1,n);
                    
                     cols[i] = false;
                     diag[i+row+n] = false;
                     cdiag[i-row +n] = false;
                    
                    
                }
            }
        }
    }
}

发表于 2020-11-19 14:31:35 回复(0)

TankWitch

class Queens {
public:
    int nQueens(int n) {
        // write code here
        memset(queen, 0, sizeof(queen) );
        int i = 1;
        queen[1] = 0;
        while (i >= 1) {
            queen[i] += 1;
            while (queen[i] <= n && !couldPlace(i) ) {
                ++queen[i];
            }
            if (queen[i] <= n) {
                if (i == n) {
                    ++methods;
                } else {
                    ++i;
                    queen[i] = 0;
                }
            } else {
                --i;
            }
        }
        return methods;
    }
private:
    bool couldPlace(int i) {
        for (int j = 1; j < i; ++j) {
            if (queen[j] == queen[i] ||
                abs(j - i) == abs(queen[j] - queen[i]) ) {
                    return false;
            }
        }
        return true;
    }
    static const int N = 16;
    int queen[N] = {0};
    int methods = 0;
};

发表于 2020-07-19 10:10:11 回复(0)

南少201911241210480

class Queens {
    int count=0;
public:
    int nQueens(int n) {
        // write code here
        nqueen(0,n,0,0,0);
        return count;
    }
    void nqueen(int row,int n,int straight_line,int r_line,int l_line)
    {  //左斜线，右斜线，直线进行判断
        if(row==n)
        {
            count++;
        }
        else
        {
            int bit=(straight_line|r_line|l_line)&((1<<n)-1)^((1<<n)-1);//bit中1就是可以放，0是不可以
            while(bit)
            {
                int b=bit&-bit;//取最右边的第一个1
                nqueen(row+1,n,straight_line|b,(r_line|b)>>1,(l_line|b)<<1);
                bit&=(bit-1);//把最右边的最后一个1变成0，防止重复
            }
        }
    }看不懂可以留言，我给链接
};

发表于 2020-04-06 18:40:51 回复(0)

n皇后问题

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题