N皇后（leetcode_51）
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
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
这题是经典的回溯算法解决，思路的本质就是穷举法，穷举每一行的每个位置，判断该位置是否符合要求，符合要求则进入下一行继续穷举，不符合要求则直接跳过，N皇后问题因为皇后只能同row同col再就是斜行，所以一行最多只能一个皇后，所以本问题的关键就是如何能穷举出所有可能。
穷觉的方式很简单，就是穷举后进入下一层穷举，然后在后面的代码直接撤销当前的选择，以此反复就能解决问题。
分析题目，我们需要一个集合来返回我们计算出的结果，以及一个二维数组来进行递归的运算。
下面是C++版本的实现：
class Solution
{
public:
vector<vector<string> > solveNQueens(int n)
{
vector<string> board(n, string(n, '.'));
northWest.assign(2 * n - 1, false);
northEast.assign(2 * n - 1, false);
colUsed.assign(n, false);
backtrack(board, 0);
return res;
}
void backtrack(vector<string> &board, int row)
{
if(row == board.size())
{
res.push_back(board);
return;
}
int n = board[row].size();
for(int col = 0; col < n; col++)
{
if(northEast[col + row] || northWest[n - 1 + col - row] || colUsed[col])
continue;
board[row][col] = 'Q';
colUsed[col] = northEast[row + col] = northWest[n - 1 + col - row] = true;
backtrack(board, row + 1);
board[row][col] = '.';
colUsed[col] = northEast[row + col] = northWest[n - 1 + col - row] = false;
}
}
private:
vector<vector<string> > res;
vector<bool> northWest;
vector<bool> northEast;
vector<bool> colUsed;
};
这里我们对于判断某个位置放皇后是否合法用了三个数组来辅助判断加快速度，我们观察可得对于每一列直接设立一个长度为N的数组就行了，对于右上方的，我们可以判断出行和列之和是不变的可以直接用col+row的下标，对于左上方的，行和列之差是不变的，下标为n-1+col-row。判断是否计算出结果的方式是递归到N之外就是计算出结果了。
Java实现：
class Solution {
boolean[] rowUsed;
boolean[] colUsed;
boolean[] southWestUsed;
boolean[] southEastUsed;
public List<List<String>> solveNQueens(int n) {
rowUsed = new boolean[n];
colUsed = new boolean[n];
southWestUsed = new boolean[2 * n - 1];
southEastUsed = new boolean[2 * n - 1];
char[][] board = new char[n][n];
List<List<String>> boards = new ArrayList<>();
for (int i = 0; i < n; i++)
Arrays.fill(board[i], '.');
backTracking(boards, board, 0);
return boards;
}
void backTracking(List<List<String>> boards, char[][] board, int row) {
if (row == board.length) {
List<String> list = new ArrayList<>();
for (char[] chars : board) {
list.add(new String(chars));
}
boards.add(list);
return;
}
for (int col = 0; col < board.length; col++) {
if (colUsed[col] || southWestUsed[row + col] || southEastUsed[board.length - 1 + col - row])
continue;
colUsed[col] = southWestUsed[row + col] = southEastUsed[board.length - 1 + col - row] = true;
board[row][col] = 'Q';
backTracking(boards, board, row + 1);
board[row][col] = '.';
colUsed[col] = southWestUsed[row + col] = southEastUsed[board.length - 1 + col - row] = false;
}
return;
}
}
java实现在思路上和C++的没有区别，但是注意一点是Java的String是不可直接通过下标进行修改的，因此稍微好点的方式是通过一个二维char数组进行计算，然后最后返回结果的时候，再将char数组转化为String。
python实现：
'''
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def generateBoard():
ans = list()
for i in range(n):
string = [str(x) for x in board[i]]
ans.append(''.join(string))
return ans
def backtrack(row: int) -> list():
if (row == n):
res.append(generateBoard())
return
length = len(board[row])
for col in range(length):
if (northEast[col + row] or northWest[n - 1 + col - row] or colUsed[col]):
continue
board[row][col] = "Q"
colUsed[col] = northEast[col + row] = northWest[n - 1 + col - row] = True
backtrack(row + 1)
board[row][col] = "."
colUsed[col] = northEast[col + row] = northWest[n - 1 + col - row] = False
res = list()
board = [['.' for i in range(n)] for i in range(n)]
northWest = [False] * (2 * n - 1)
northEast = [False] * (2 * n - 1)
colUsed = [False] * n
backtrack(0)
return res
'''
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
cols = [False] * n
hill = [False] * (2*n)
dale = [False] * (2*n)
res = []
dots = '.' * n
def dfs(r, cur_p):
if r == n:
res.append(cur_p[:])
return
for c in range(n):
if not cols[c] and not hill[r+c] and not dale[r-c+n]:
cols[c] = hill[r+c] = dale[r-c+n] = True
line = dots[:c]+'Q'+dots[c+1:]
dfs(r+1, cur_p + [line])
cols[c] = hill[r+c] = dale[r-c+n] = False
dfs(0, [])
return res
python我放了两个版本的，其实思路是一模一样的，但是人家就是写得比我的好看，我的想法是完全按照C++版本的来，直接翻译一遍，但是各个语言有各个语言的特点，首先就是数组的问题，我还是首先用二维列表然后再生成我需要的结果，但是观察发现，其实下一行的运算和上一行的情况是无直接关系的，只要用那三个数组就可以了，所以，就可以直接每一行用同一个全部是dots的数组，需要在哪个位置放'Q'就直接在那个位置切片就行了，递归到下一层的时候直接弄一个列表加入到之前已有结果就行了。
我不得不说，python是一个憨批语言，语法就好像是个摆设一样。