我要招人

去企业版

首页 > 试题广场 >

n皇后问题

[编程题]n皇后问题

热度指数：8385 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

已知正整数n，即在一个nxn的棋盘上放置n个棋子，使每行每列和每条对角线上都只有一个棋子，返回有多少种摆法方法。保证n小于等于15。

例如当输入4时，对应的返回值为2，

对应的两种四皇后摆位如下图所示：

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

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)

Java

Caffeine

//思路递归的方法

当

if(i>=n){

return cnt++;

}

完成时候便开始计数增加

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

A[i] = j; 对第i行完全遍历

每一次遍历成功就会对

if(check(i,j))

f(i+1);

下一行进行测试。

import java.util.*;

public class Queens {

int nQueens(int n) {

// write code here

this.n = n;

A = new int[n];

cnt = 0;

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 i,int j){

for(int k = 0;k<i;k++){

if(A[k] == j ||Math.abs(i - k) == Math.abs(j - A[k]))

return false;

}

return true;

}

发表于 2017-03-27 22:28:59 回复(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)