n-皇后 ii

[编程题]n-皇后 ii

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

继续思考“n-queens”问题

这次我们不是输出皇后的排列情况，而是输出n皇后问题一共有多少种解法

注：n 皇后问题是在 n*n 棋盘上放置 n 个皇后，并且使它们互相不在对方的攻击范围之内的摆放方法；

注注：皇后的攻击范围是上、下、左、右、左上、左下、右下、右上共 8 个方向，且不限距离。

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

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)

Java

Northernwind

//暴力回溯，请勿模仿

import java.util.*;

public class Solution {
int count=0;
public int totalNQueens(int n) {
ArrayList<Integer> placed=new ArrayList<>();
backtrack(placed,n,0);
return count;
}
public void backtrack(ArrayList<Integer> placed,int n,int cur){
if(placed.size()==n){
count++;
}else{
for (int i = 0; i <n ; i++) {
boolean flag=true;
for (int j = 0; j <placed.size() ; j++) {
if (placed.get(j)==i||((i-placed.get(j))==cur-j)||((i-placed.get(j))==j-cur)){//判断是否合理
flag=false;
break;
}
}
if(flag){
placed.add(i);
backtrack(placed,n,cur+1);
placed.remove(placed.size()-1);
}
}
}
}
}

发表于 2018-04-08 11:34:40 回复(0)

Java

拾贰儿

public class Solution {

   int count = 0; 
    public int totalNQueens(int n) {
        int[] a = new int[n];
        helper(a,0,n);
        return count;
    }
    public void helper(int[] a,int k,int n){
        if(k >= n){
            count ++;
            return;
        }
        for(int i = 0;i<n ;i++){
            a[k] = i;
            if(check(a,k)){
                helper(a,k+1,n);
            }
        }
    }
    public boolean check(int[] a,int k){
        boolean flag = true;
        for(int i = 0;i<k;i++){
            if(Math.abs(a[i] - a[k]) == k - i || a[i] == a[k]) return false;
        }
        return flag;
    }
}

发表于 2017-10-27 10:36:31 回复(0)

Java

Holiday_12138

//应该还是要搜索吧？
public class Solution {
    int count = 0;
    public int totalNQueens(int n) {
        int[] cols = new int[n];
        int[] slash1 = new int[2*n-1];
        int[] slash2 = new int[2*n-1];
        DFS(n, 0, cols, slash1, slash2);
        return count;
    }

    public void DFS( int n, int cur, int cols[], int slash1[], int slash2[]) {
        if(cur == n) {
            count++;
        }
        for(int i=0; i<n; i++) {
            if(cols[i] != 1 && slash1[cur + i] != 1 && slash2[n-1-cur+i] != 1) {
                cols[i] = 1;
                slash1[cur + i] = 1;
                slash2[n-1-cur+i] = 1;
                DFS(n, cur+1, cols, slash1, slash2);
                cols[i] = 0;
                slash1[cur + i] = 0;
                slash2[n-1-cur+i] = 0;
            }
        }
    }
}

发表于 2017-06-19 13:52:34 回复(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)