AlgoPress | AlgoPress

题目描述

https://leetcode.cn/problems/n-queens-ii

n皇后问题研究的是如何将 n个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回 n 皇后问题不同的解决方案的数量。

示例 1：

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

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 9

思路：回溯法

csharp

public class Solution {

    int count = 0;
    bool[,] board;

    private bool canPlace(int row, int col, int n){
        //左上
        for(int i=row,j=col; i>=0&&j>=0;j--,i--){
            if(board[i,j]){
                return false;
            }
        }
        //上边
        for(int i=row ; i>=0; i--){
            if(board[i,col]){
                return false;
            }
        }
        //右上
        for(int i=row,j=col; i>=0&&j<n;i--,j++){
            if(board[i,j]){
                return false;
            }
        }
        //左边        
        for(int j=col; j>=0; j--){
            if(board[row,j]){
                return false;
            }
        }
        return true;
    }

    private void dfs(int row, int n){
        if(row >= n){
            count++;
            return;
        }
        for(int j=0; j<n; j++){
            if(canPlace(row,j,n)){
                board[row,j] = true;
                dfs(row+1,n);
                board[row,j] = false;
            }
        }
    }

    public int TotalNQueens(int n) {
        board = new bool[n,n];
        dfs(0,n);
        return count;
    }

}

题目描述 #

思路：回溯法 #

题目描述

思路：回溯法