算法leetcode｜51. N 皇后（rust重拳出击）

文章目录

51. N 皇后：

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将

n

个皇后放置在

n×n

的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数

n

，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中

'Q'

和

'.'

分别代表了皇后和空位。

样例 1：

输入：
    
    n = 4
    
输出：
    
    [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
    
解释：
    
    如上图所示，4 皇后问题存在两个不同的解法。

样例 2：

输入：
    
    n = 1
    
输出：
    
    [["Q"]]

提示：

• 1 <= n <= 9

分析：

• 面对这道算法题目，二当家的陷入了沉思。
• 参数取值只有9个数，打个常量表怎么样？
• 按照行逐行尝试，深度优先递归套娃大法，关键是列和斜线上已经放置的标记存储。

题解：

rust：

implSolution{pubfnsolve_n_queens(n:i32)->Vec<Vec<String>>{fndfs(n:i32, ans:&mutVec<Vec<String>>, queens:&mutVec<usize>, row:usize, columns:i32, diagonals1:i32, diagonals2:i32){if n == row asi32{// 全部成功放置，表示一次成功方案let board =(0..n asusize).map(|i|{letmut bs =vec![b'.'; n asusize];
                    bs[queens[i]]=b'Q';String::from_utf8(bs).unwrap()}).collect();
                ans.push(board);}else{// 还可以放置的位置letmut availablePositions =((1<< n)-1)&(!(columns | diagonals1 | diagonals2));// 还有可以放置的位置while availablePositions !=0{// 可以放置的位置let position = availablePositions &(-availablePositions);// 放置
                    queens[row]=(position -1).count_ones()asusize;// 标记当前位置不可以放置
                    availablePositions &= availablePositions -1;// 递归套娃dfs(n, ans, queens, row +1, columns | position,(diagonals1 | position)<<1,(diagonals2 | position)>>1);}}}letmut ans =Vec::new();dfs(n,&mut ans,&mutvec![0; n asusize],0,0,0,0);return ans;}}

go：

funcsolveNQueens(n int)(ans [][]string){var dfs func(queens []int, row, columns, diagonals1, diagonals2 int)
    dfs =func(queens []int, row, columns, diagonals1, diagonals2 int){if row == n {// 全部成功放置，表示一次成功方案
            board :=make([]string, n)for i :=0; i < n; i++{
                r :=make([]byte, n)for j :=0; j < n; j++{
                    r[j]='.'}
                r[queens[i]]='Q'
                board[i]=string(r)}
            ans =append(ans, board)}else{// 还可以放置的位置
            availablePositions :=(1<<n -1)&^(columns | diagonals1 | diagonals2)// 还有可以放置的位置for availablePositions >0{// 可以放置的位置
                position := availablePositions &-availablePositions
                // 放置
                queens[row]= bits.OnesCount(uint(position -1))// 标记当前位置不可以放置
                availablePositions &^= position
                // 递归套娃dfs(queens, row+1, columns|position,(diagonals1|position)<<1,(diagonals2|position)>>1)}}}dfs(make([]int, n),0,0,0,0)return}

c++：

classSolution{private:voiddfs(int n, vector<vector<string>>&ans, vector<int>&queens,int row,int columns,int diagonals1,int diagonals2){if(row == n){// 全部成功放置，表示一次成功方案auto board = vector<string>();for(int i =0; i < n;++i){
                string r =string(n,'.');
                r[queens[i]]='Q';
                board.emplace_back(r);}
            ans.emplace_back(board);}else{// 还可以放置的位置int availablePositions =((1<< n)-1)&(~(columns | diagonals1 | diagonals2));// 还有可以放置的位置while(availablePositions !=0){// 可以放置的位置int position = availablePositions &(-availablePositions);// 放置
                queens[row]=__builtin_ctz(position);// 标记当前位置不可以放置
                availablePositions &= availablePositions -1;// 递归套娃dfs(n, ans, queens, row +1, columns | position,(diagonals1 | position)<<1,(diagonals2 | position)>>1);}}}public:
    vector<vector<string>>solveNQueens(int n){auto ans = vector<vector<string>>();auto queens = vector<int>(n,-1);dfs(n, ans, queens,0,0,0,0);return ans;}};

python：

classSolution:defsolveNQueens(self, n:int)-> List[List[str]]:defdfs(row:int, columns:int, diagonals1:int, diagonals2:int):if row == n:# 全部成功放置，表示一次成功方案
                board =list()for i inrange(n):
                    row =["."]* n
                    row[queens[i]]="Q"
                    board.append("".join(row))
                ans.append(board)else:# 还可以放置的位置
                available_positions =((1<< n)-1)&(~(columns | diagonals1 | diagonals2))# 还有可以放置的位置while available_positions !=0:# 可以放置的位置
                    position = available_positions &(-available_positions)# 放置
                    queens[row]=bin(position -1).count("1")# 标记当前位置不可以放置
                    available_positions &= available_positions -1# 递归套娃
                    dfs(row +1, columns | position,(diagonals1 | position)<<1,(diagonals2 | position)>>1)

        ans =list()
        queens =[-1]* n
        dfs(0,0,0,0)return ans

java：

classSolution{publicList<List<String>>solveNQueens(int n){int[] queens =newint[n];List<List<String>> ans =newArrayList<List<String>>();dfs(n, ans, queens,0,0,0,0);return ans;}privatevoiddfs(int n,List<List<String>> ans,int[] queens,int row,int columns,int diagonals1,int diagonals2){if(row == n){// 全部成功放置，表示一次成功方案List<String> board =newArrayList<String>();for(int i =0; i < n; i++){char[] r =newchar[n];Arrays.fill(r,'.');
                r[queens[i]]='Q';
                board.add(newString(r));}
            ans.add(board);}else{// 还可以放置的位置int availablePositions =((1<< n)-1)&(~(columns | diagonals1 | diagonals2));// 还有可以放置的位置while(availablePositions !=0){// 可以放置的位置finalint position = availablePositions &(-availablePositions);// 放置
                queens[row]=Integer.bitCount(position -1);// 标记当前位置不可以放置
                availablePositions &= availablePositions -1;// 递归套娃尝试下一行dfs(n, ans, queens, row +1, columns | position,(diagonals1 | position)<<1,(diagonals2 | position)>>1);}}}}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~