AlgoPressAppearance
0051-N皇后
https://leetcode.cn/problems/n-queens
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
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
解题思路
经典回溯算法
result = []
def backtrack(路径,选择列表):
if 满足结束条件：
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径，选择列表)
撤销选择
参考代码
csharp
public class Solution {
List<IList<string>> result = new List<IList<string>>();
protected int boardLength;
private bool isValid(int[,] board, int row, int col){
//判断左上
for(int i=row,j=col; i>=0 && j>=0; i--,j--){
//Console.WriteLine("i:{0},j:{1}",i,j);
if(board[i,j] == 1){
return false;
}
}
//判断上边
for(int i=0; i<row; i++){
if(board[i,col] == 1){
return false;
}
}
//判断右上
for(int i=row,j=col; i>=0 && j<boardLength; i--,j++){
if(board[i,j] == 1){
return false;
}
}
//判断左边 左边不用判断 因为一行就放置一个
// for(int j=0;j<col;j++){
// if(board[row,j] == 1){
// return false;
// }
// }
return true;
}
private void AddResult(int[,] board){
List<string> rows = new List<string>();
for(int i=0; i< boardLength; i++){
string row = "";
for(int j = 0; j < boardLength; j++){
row += board[i,j] == 1 ? "Q" : ".";
}
rows.Add(row);
}
result.Add(rows);
}
private void backtrack(int[,] board, int row){
if(row >= boardLength){
//找到答案
AddResult(board);
return;
}
for(int col = 0; col < boardLength; col++){
//Console.WriteLine("col:{0}, n:{1}",col,board.GetLength(1));
if(isValid(board, row, col)){ //判断放置条件
board[row,col] = 1; //放置
backtrack(board,row+1);
board[row,col] = 0; //取回
}
}
}
public IList<IList<string>> SolveNQueens(int n) {
//创建棋盘，默认为 0 ，放置为 1
int[,] board = new int[n,n];
boardLength = n;
//从0行开始回溯
backtrack(board,0);
return result;
}
}
参考代码：复习20220319
csharp
public class Solution {
//回溯法，二维数组 used 表示是否选择该数
private char[,] board;
private List<IList<string>> result = new List<IList<string>>();
private void AddResult(){
List<string> rows = new List<string>();
for(int i=0; i<board.GetLength(0); i++){
string s="";
for(int j=0; j<board.GetLength(1); j++){
s+=board[i,j];
}
rows.Add(s);
}
result.Add(rows);
}
//验证是否合法
private bool IsValid(int row, int col){
//验证左上
for(int i=row, j=col; i>=0 && j>=0; i--,j--){
if(board[i,j] == 'Q'){
return false;
}
}
//验证上边
for(int i=row; i>=0; i--){
if(board[i,col] == 'Q'){
return false;
}
}
//验证右上
for(int i=row, j=col; i>=0 && j < board.GetLength(1); i--,j++){
if(board[i,j] == 'Q'){
return false;
}
}
//验证左边
for(int j=0;j<=col;j++){
if(board[row,j] == 'Q'){
return false;
}
}
return true;
}
private void dfs(int row){
if(row == board.GetLength(0)){
//输出结果
AddResult();
return;
}
for(int col=0; col < board.GetLength(0); col++){
if(IsValid(row,col)){
board[row,col] = 'Q';
dfs(row+1);
board[row,col] = '.';
}
}
}
public IList<IList<string>> SolveNQueens(int n) {
board = new char[n,n];
//初始化为 .
for(int i=0;i<n; i++){
for(int j = 0; j < n; j++){
board[i,j] = '.';
}
}
dfs(0);
return result;
}
}
参考代码：交错数组
使用交错数组 board[i][j] 输出结果的时候可以省略一些代码
csharp
public class Solution {
private char[][] board;
private List<IList<string>> result = new List<IList<string>>();
private void AddResult(){
List<string> rows = new List<string>();
for(int i=0; i<board.Length; i++){
rows.Add(new string(board[i]));
}
result.Add(rows);
}
//验证是否合法
private bool IsValid(int row, int col){
//验证左上
for(int i=row, j=col; i>=0 && j>=0; i--,j--){
if(board[i][j] == 'Q'){
return false;
}
}
//验证上边
for(int i=row; i>=0; i--){
if(board[i][col] == 'Q'){
return false;
}
}
//验证右上
for(int i=row, j=col; i>=0 && j < board[0].Length; i--,j++){
if(board[i][j] == 'Q'){
return false;
}
}
//左边需要验证，因为一行就放置一个
return true;
}
private void dfs(int row){
if(row == board.Length){
AddResult();
return;
}
for(int col=0; col < board.Length; col++){
if(IsValid(row,col)){
board[row][col] = 'Q';
dfs(row+1);
board[row][col] = '.';
}
}
}
public IList<IList<string>> SolveNQueens(int n) {
board = new char[n][];
for(int i=0;i<n;i++){
board[i] = new char[n];
for(int j=0;j<n;j++){
board[i][j] = '.';
}
}
dfs(0);
return result;
}
}