一、题目
1、算法题目
“给定一个整数n，返回所有不同的N皇后问题的解决方案。”
题目链接：
来源：力扣（LeetCode）
链接：51. N 皇后 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
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皇后问题是一道经典的回溯问题。首先，分析规则，N皇后放置在N*N 棋盘上，然后皇后彼此之间不能相互攻击。
直接的做法是暴力枚举所以可能的情况，然后判断互相不攻击的情况，但是暴力枚举的时间复杂度非常高，必须利用限制条件进行优化。
可以通过回溯的方法找到可能的解，首先，使用一个数组记录每个每行皇后的列下标，依次在每一行放置一个皇后后，下一个放置皇后的位置都不能和已经放置皇后的位置之间有攻击，当所有皇后放置完毕，就可以找到一个解。
为了降低总时间复杂度，需要在放置皇后时快速判断每个位置是否可以放置皇后，那么就可以在O(1)的时间内判断该位置的列和两条斜线上是否已经有皇后。
2、代码实现
代码参考：
public class Solution { List<IList<string>> res; public IList<IList<string>> SolveNQueens(int n) { res = new List<IList<string>>(); char[][] board = new char[n][]; for (int i = 0; i < n; ++i) board[i] = new char[n]; foreach (char[] chars in board){ Array.Fill(chars, '.'); } backTrack(board, 0); return res; } private void backTrack(char[][] board, int row){ if (row == board.Length){ res.Add(charToString(board)); return; } int n = board[row].Length; for (int col = 0; col < n; ++col){ if (!isValid(board, row, col)) continue; board[row][col] = 'Q'; backTrack(board, row + 1); board[row][col] = '.'; } } private bool isValid(char[][] board, int row, int col){ int rows = board.Length; foreach (char[] chars in board) if (chars[col] == 'Q') return false; for (int i = row - 1, j = col + 1; i >= 0 && j < rows; i--, j++){ if (board[i][j] == 'Q') return false; } for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){ if (board[i][j] == 'Q') return false; } return true; } private List<string> charToString(char[][] array){ List<string> result = new List<string>(); foreach (char[] chars in array) result.Add(new String(chars)); return result; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(N!)
其中N是皇后数量。
空间复杂度： O(N)
其中N是皇后数量。
三、总结
这道题可以好好理解一下。
爱奇艺和字节的笔试都出现过这道题。
