rust 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2024-12-02 09:33:23

impl Solution {
    pub fn total_n_queens(n: i32) -> i32 {
        fn dfs(r: usize, col: &mut [bool], diag1: &mut [bool], diag2: &mut [bool], ans: &mut i32) {
            let n = col.len();
            if r == n {
                *ans += 1; // 找到一个合法方案
                return;
            }
            for c in 0..n {
                let rc = n + r - c - 1;
                if !col[c] && !diag1[r + c] && !diag2[rc] {
                    col[c] = true;
                    diag1[r + c] = true;
                    diag2[rc] = true;
                    dfs(r + 1, col, diag1, diag2, ans);
                    col[c] = false;
                    diag1[r + c] = false;
                    diag2[rc] = false; // 恢复现场
                }
            }
        }

        let n = n as usize;
        let mut ans = 0;
        let mut col = vec![false; n];
        let mut diag1 = vec![false; n * 2 - 1];
        let mut diag2 = vec![false; n * 2 - 1];
        dfs(0, &mut col, &mut diag1, &mut diag2, &mut ans);
        ans
    }
}

javascript 解法, 执行用时: 4 ms, 内存消耗: 49.8 MB, 提交时间: 2024-12-02 09:33:09

/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function(n) {
    let ans = 0;
    const col = Array(n).fill(false);
    const diag1 = Array(n * 2 - 1).fill(false);
    const diag2 = Array(n * 2 - 1).fill(false);
    function dfs(r) {
        if (r === n) {
            ans++; // 找到一个合法方案
            return;
        }
        for (let c = 0; c < n; c++) {
            const rc = r - c + n - 1;
            if (!col[c] && !diag1[r + c] && !diag2[rc]) {
                col[c] = diag1[r + c] = diag2[rc] = true;
                dfs(r + 1);
                col[c] = diag1[r + c] = diag2[rc] = false; // 恢复现场
            }
        }
    }
    dfs(0);
    return ans;
};

cpp 解法, 执行用时: 0 ms, 内存消耗: 8.1 MB, 提交时间: 2024-12-02 09:32:57

class Solution {
public:
    int totalNQueens(int n) {
        int ans = 0;
        vector<int> col(n), diag1(n * 2 - 1), diag2(n * 2 - 1);
        auto dfs = [&](auto&& dfs, int r) {
            if (r == n) {
                ans++; // 找到一个合法方案
                return;
            }
            for (int c = 0; c < n; c++) {
                int rc = r - c + n - 1;
                if (!col[c] && !diag1[r + c] && !diag2[rc]) {
                    col[c] = diag1[r + c] = diag2[rc] = true;
                    dfs(dfs, r + 1);
                    col[c] = diag1[r + c] = diag2[rc] = false; // 恢复现场
                }
            }
        };
        dfs(dfs, 0);
        return ans;
    }
};

java 解法, 执行用时: 0 ms, 内存消耗: 39.4 MB, 提交时间: 2024-12-02 09:32:44

class Solution {
    private int ans;

    public int totalNQueens(int n) {
        boolean[] col = new boolean[n];
        boolean[] diag1 = new boolean[n * 2 - 1];
        boolean[] diag2 = new boolean[n * 2 - 1];
        dfs(0, col, diag1, diag2);
        return ans;
    }

    private void dfs(int r, boolean[] col, boolean[] diag1, boolean[] diag2) {
        int n = col.length;
        if (r == n) {
            ans++; // 找到一个合法方案
            return;
        }
        for (int c = 0; c < n; c++) {
            int rc = r - c + n - 1;
            if (!col[c] && !diag1[r + c] && !diag2[rc]) {
                col[c] = diag1[r + c] = diag2[rc] = true;
                dfs(r + 1, col, diag1, diag2);
                col[c] = diag1[r + c] = diag2[rc] = false; // 恢复现场
            }
        }
    }
}

python3 解法, 执行用时: 44 ms, 内存消耗: 15 MB, 提交时间: 2023-03-21 10:10:58

class Solution:
    def totalNQueens(self, n: int) -> int:
        def backtrack(r):
            if r == n:
                result.append(1)
                return
            for i in range(n):
                if i in columns or r - i in diagonal1 or r + i in diagonal2:
                    continue
                #当前列及正反对角线都没有皇后时；再进行放置皇后
                columns.append(i)           #将放置皇后的列添加到用来存放已放置过皇后的数组中
                diagonal1.append(r - i)     #将放置皇后所在的反对角线坐标的值添加到用来存放相应的数组里记录
                diagonal2.append(r + i)     #将放置皇后所在的正对角线坐标的值添加到用来存放相应的数组里记录
                backtrack(r + 1)            #对下一行进行放置
                columns.pop()               #回溯，将之前添加的pop出
                diagonal1.pop()             #回溯，将之前添加的pop出
                diagonal2.pop()             #回溯，将之前添加的pop出
        result = []
        columns, diagonal1, diagonal2 = [], [], []
        row = ["."] * n
        backtrack(0)
        return len(result)

python3 解法, 执行用时: 44 ms, 内存消耗: 15 MB, 提交时间: 2023-03-21 10:10:35

class Solution:
    def totalNQueens(self, n: int) -> int:
        res=0
        def backtrack(i,col,pos,neg):
            nonlocal res
            if i==n:
                res+=1
                return 
            #其中1表示可以被选
            pre=((1<<n)-1)&(~(col | pos | neg))
          
            while pre:
                cur=pre & (-pre)
                backtrack(i+1,col | cur , (pos | cur)>>1,(neg | cur)<<1)
                pre&=pre-1
            
        backtrack(0,0,0,0)
        return res

python3 解法, 执行用时: 40 ms, 内存消耗: 15 MB, 提交时间: 2023-03-21 10:10:26

class Solution:
    def totalNQueens(self, n: int) -> int:
        res=0
        def backtrack(index,col,pos,neg):
            nonlocal res
            if index==n:
                res+=1
                return 
            #获取可供选择的状态位，1为不可选，0为可选
            pre=col | pos | neg
            for i in range(n):
                cur=1<<i
                if cur&pre==0:
                    backtrack(index+1,col | cur , (pos | cur)>>1,(neg | cur)<<1)
            
        backtrack(0,0,0,0)
        return res

python3 解法, 执行用时: 48 ms, 内存消耗: 15 MB, 提交时间: 2023-03-21 10:10:12

class Solution:
    def totalNQueens(self, n: int) -> int:
        col=set()
        pos=set()
        neg=set()
        res=0
        def backtrack(i):
            nonlocal res
            if i==n:
                res+=1
                return 
            for j in range(n):
                if j not in col and i-j not in pos and i+j not in neg:
                    #做选择
                    col.add(j)
                    pos.add(i-j)
                    neg.add(i+j)
                    #递归进入下一行
                    backtrack(i+1)
                    #撤销选择
                    col.remove(j)
                    pos.remove(i-j)
                    neg.remove(i+j)
        
        backtrack(0)
        return res

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-03-21 10:05:18

var count int
func totalNQueens(n int) int {
    count = 0
    dfs(n, 0, 0, 0, 0)
    return count
}

func dfs(n, row, col, pie, na int){
    if row >= n{
        count++
        return 
    }
    
    bits := (^(col | pie | na)) & ((1<<uint(n))-1)  //获取所有可填空位
    for bits != 0{
        bit := bits & -bits  //取位置排在最后的一个空位
        dfs(n, row+1, col|bit, (pie|bit)<<1, (na|bit)>>1)  //递归遍历下一行
        bits = bits & (bits-1) //打掉最后位置上的1， 因为该位置已被占用
    }
    
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-03-21 10:05:00

//位运算第三种（将三个bit array 变为形式参数，那么就不用再每次将其重置了，下一次递归会自动重置）
func totalNQueens(n int) int {
    if n==0{
        return 0
    }
    //保存结果
    res:=0
    //定义三个数，其中的每一个位表示该斜线的第几个的状态（入第七位为1，表示第七条斜线已经占有了，不能放入）
    dfs(0,n,0,0,0,&res)
    return res 
}
//row：第几列
func dfs(row int,n int,cols,pies,nas int,res *int){
    //出递归条件
    if row==n{
        (*res)++
        return
    }
    //cols | (pies >> row) | (nas >> (n-1-row)):取并集表示所有不能走的位置,取反表示所有可以走的点
    //因为此处有32位，但我们只需要n位，所以截掉其余的位
    //变为形参后，每次都会重新调用，pies,nas就不需要再去移动了，
    //ok:=(^(cols | (pies >> uint(row)) | (nas >> uint(n-1-row)))) & (1 << uint(n)-1)
    ok:=(^(cols | pies  | nas)) & (1 << uint(n)-1)
    //遍历这些能走的通的点
    //ok!=0:里边还有1,继续执行
    for ok!=0{
        //取ok中最后一个1(p就代表当前所取的那列)
        p:=ok & (-ok)
        //取完后，将该位清除
        ok^=p
        //进行占位（所谓占位，是指能被皇后攻击到的区域）
        //在这里的意思（以cols为例）就是改变第i列的值，此处第i列的值都为0，将其置为1，进行设置
        //递归执行下一层
        //此时cols,pies,nas都为形参，所以当前pies，就代表当前的列所在的位置，就不需要去移动了，直接置位就行
        dfs(row+1,n,cols^p,(pies^p) >> 1,(nas^p) << 1,res)
        //递归结束后要将相应占位的元素进行解放，以满足下一次调用
        //比如在第一个点是不满足的，但是将其占位了，所以要将其解开
        //将占位元素进行解开，相当于回溯
        //此时为形参，每次递归完后会自动回溯，所以就不用手动去整理了
    }
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-03-21 10:04:51

//位运算表示法第二种
func totalNQueens(n int) int {
    if n==0{
        return 0
    }
    //保存结果
    res:=0
    //定义三个数，其中的每一个位表示该斜线的第几个的状态（入第七位为1，表示第七条斜线已经占有了，不能放入）
    cols,pies,nas:=0,0,0
    dfs(0,n,cols,pies,nas,&res)
    return res
    
}
//row：第几列
func dfs(row int,n int,cols,pies,nas int,res *int){
    //出递归条件
    if row==n{
        (*res)++
        return
    }
    //cols | (pies >> row) | (nas >> (n-1-row)):取并集表示所有不能走的位置,取反表示所有可以走的点
    //因为此处有32位，但我们只需要n位，所以截掉其余的位
    ok:=(^(cols | (pies >> uint(row)) | (nas >> uint(n-1-row)))) & (1 << uint(n)-1)
    //遍历这些能走的通的点
    //ok!=0:里边还有1,继续执行
    for ok!=0{
        //取ok中最后一个1(p就代表当前所取的那列)
        p:=ok & (-ok)
        //取完后，将该位清除
        ok^=p
        //进行占位（所谓占位，是指能被皇后攻击到的区域）
        //在这里的意思（以cols为例）就是改变第i列的值，此处第i列的值都为0，将其置为1，进行设置
        cols^=p
        pies^=(p << uint(row))
        nas^=(p << uint(n-1-row))
        //递归执行下一层
        dfs(row+1,n,cols,pies,nas,res)
        //递归结束后要将相应占位的元素进行解放，以满足下一次调用
        //比如在第一个点是不满足的，但是将其占位了，所以要将其解开
        //将占位元素进行解开，相当于回溯
        cols^=p
        pies^=(p << uint(row))
        nas^=(p << uint(n-1-row))
    }
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-03-21 10:04:36

//位运算表示法第一种
func totalNQueens(n int) int {
    if n==0{
        return 0
    }
    //保存结果
    res:=0
    //定义三个数，其中的每一个位表示该斜线的第几个的状态（入第七位为1，表示第七条斜线已经占有了，不能放入）
    cols,pies,nas:=0,0,0
    dfs(0,n,cols,pies,nas,&res)
    return res
    
}
//row：第几列
func dfs(row int,n int,cols,pies,nas int,res *int){
    //出递归条件
    if row==n{
        (*res)++
        return
    }
    //每层遍历所有的列，找到满足条件的值
    for col:=0;col<n;col++{
        //判断是否会被皇后干死，干不死就是要找的皇后
        pie:=row+col
        na:=n-1-(row-col)
        //读取这些bit array中第i位的值，(cols >> uint(col))：右移若干位，将相应的列值和1想与，得到该列的值
        if ((cols >> uint(col)) & 1) | ((pies >> uint(pie)) & 1) | ((nas >> uint(na)) & 1) !=0 {
            continue
        }
        //进行占位（所谓占位，是指能被皇后攻击到的区域）
        //在这里的意思（以cols为例）就是改变第i列的值，此处第i列的值都为0，将其置为1，进行设置
        cols^=(1 << uint(col))
        pies^=(1 << uint(pie))
        nas^=(1 << uint(na))
        //递归执行下一层
        dfs(row+1,n,cols,pies,nas,res)
        //递归结束后要将相应占位的元素进行解放，以满足下一次调用
        //比如在第一个点是不满足的，但是将其占位了，所以要将其解开
        //将占位元素进行解开，相当于回溯
         cols^=(1 << uint(col))
        pies^=(1 << uint(pie))
        nas^=(1 << uint(na))
    }
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-03-21 10:04:02

//数组表示法
func totalNQueens(n int) int {
    if n==0{
        return 0
    }
    res:=0
    cols:=make([]bool,n)
    pies:=make([]bool,2*n-1)
    nas:=make([]bool,2*n-1)
    dfs(0,n,cols,pies,nas,&res)
    return res
    
}

//rows:存放对应皇后的列的值
func dfs(row int,n int,cols,pies,nas []bool,res *int){
    //出递归条件
    if row==n{
        (*res)++
        return
    }
    //每层遍历所有的列，找到满足条件的值
    for col:=0;col<n;col++{
        //判断是否会被皇后干死，干不死就是要找的皇后
        if cols[col] || pies[row+col] || nas[n-1-(row-col)]{
            continue
        }
        //进行占位（所谓占位，是指能被皇后攻击到的区域）
        cols[col]=true
        pies[row+col]=true
        nas[n-1-(row-col)]=true
        //递归执行下一层
        dfs(row+1,n,cols,pies,nas,res)
        //递归结束后要将相应占位的元素进行解放，以满足下一次调用
        //比如在第一个点是不满足的，但是将其占位了，所以要将其解开
        cols[col]=false
        pies[row+col]=false
        nas[n-1-(row-col)]=false
    }
}

golang 解法, 执行用时: 4 ms, 内存消耗: 1.9 MB, 提交时间: 2023-03-21 10:03:43

//hash表法
func totalNQueens(n int) int {
    if n==0{
        return 0
    }
    res:=0
    cols:=make(map[int]bool,0)
    pies:=make(map[int]bool,0)
    nas:=make(map[int]bool,0)
    dfs(0,n,cols,pies,nas,&res)
    return res
    
}

//rows:存放对应皇后的列的值
func dfs(row int,n int,cols,pies,nas map[int]bool,res *int){
    //出递归条件
    if row==n{
        (*res)++
        return
    }
    //每层遍历所有的列，找到满足条件的值
    for col:=0;col<n;col++{
        //判断是否会被皇后干死，干不死就是要找的皇后
        if cols[col] || pies[row+col] || nas[row-col]{
            continue
        }
        //进行占位（所谓占位，是指能被皇后攻击到的区域）
        cols[col]=true
        pies[row+col]=true
        nas[row-col]=true
        //递归执行下一层
        dfs(row+1,n,cols,pies,nas,res)
        //递归结束后要将相应占位的元素进行解放，以满足下一次调用
        //比如在第一个点是不满足的，但是将其占位了，所以要将其解开
        cols[col]=false
        pies[row+col]=false
        nas[row-col]=false
    }
}