问题描述
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
提示：
皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一到七步，可进可退。（引用自 百度百科 - 皇后 ）
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
解答
''' 递归dfs+回溯，没用剪枝，目前还不知道哪些可以剪。。。 ''' class Solution(object): def solveNQueens(self, n): if n == 1: return [["Q"]] if n > 1 and n < 4: return [] global board global flag global result board = [[0 for _ in range(n)] for _ in range(n)] result = [] flag = 0 def stretch(x,y,l,r,u,d,sign): if l == 1 and r == 0 and u == 0 and d == 0 and y-1 >= 0: if board[x][y-1] >= 10000: flag = 1 if sign == 1: board[x][y-1] += 1 stretch(x,y-1,1,0,0,0,1) else: board[x][y-1] -= 1 stretch(x,y-1,1,0,0,0,0) elif l == 0 and r == 1 and u == 0 and d == 0 and y+1 < n: if board[x][y+1] >= 10000: flag = 1 if sign == 1: board[x][y+1] += 1 stretch(x,y+1,0,1,0,0,1) else: board[x][y+1] -= 1 stretch(x,y+1,0,1,0,0,0) elif l == 0 and r == 0 and u == 1 and d == 0 and x-1 >= 0: if board[x-1][y] >= 10000: flag = 1 if sign == 1: board[x-1][y] += 1 stretch(x-1,y,0,0,1,0,1) else: board[x-1][y] -= 1 stretch(x-1,y,0,0,1,0,0) elif l == 0 and r == 0 and u == 0 and d == 1 and x+1 < n: if board[x+1][y] >= 10000: flag = 1 if sign == 1: board[x+1][y] += 1 stretch(x+1,y,0,0,0,1,1) else: board[x+1][y] -= 1 stretch(x+1,y,0,0,0,1,0) elif l == 1 and r == 0 and u == 1 and d == 0 and y-1 >= 0 and x-1 >= 0: if board[x-1][y-1] >= 10000: flag = 1 if sign == 1: board[x-1][y-1] += 1 stretch(x-1,y-1,1,0,1,0,1) else: board[x-1][y-1] -= 1 stretch(x-1,y-1,1,0,1,0,0) elif l == 1 and r == 0 and u == 0 and d == 1 and y-1 >= 0 and x+1 < n: if board[x+1][y-1] >= 10000: flag = 1 if sign == 1: board[x+1][y-1] += 1 stretch(x+1,y-1,1,0,0,1,1) else: board[x+1][y-1] -= 1 stretch(x+1,y-1,1,0,0,1,0) elif l == 0 and r == 1 and u == 0 and d == 1 and y+1 < n and x+1 < n: if board[x+1][y+1] >= 10000: flag = 1 if sign == 1: board[x+1][y+1] += 1 stretch(x+1,y+1,0,1,0,1,1) else: board[x+1][y+1] -= 1 stretch(x+1,y+1,0,1,0,1,0) elif l == 0 and r == 1 and u == 1 and d == 0 and y+1 < n and x-1 >= 0: if board[x-1][y+1] >= 10000: flag = 1 if sign == 1: board[x-1][y+1] += 1 stretch(x-1,y+1,0,1,1,0,1) else: board[x-1][y+1] -= 1 stretch(x-1,y+1,0,1,1,0,0) else:return def remove(board,x,y): board[x][y] -= 10000 stretch(x,y,0,1,0,0,0) stretch(x,y,1,0,0,0,0) stretch(x,y,0,0,1,0,0) stretch(x,y,0,0,0,1,0) stretch(x,y,1,0,1,0,0) stretch(x,y,1,0,0,1,0) stretch(x,y,0,1,0,1,0) stretch(x,y,0,1,1,0,0) def place_the_queen(x,y): global board global flag global count if x >= 0 and x < n and y >= 0 and y < n: if board[x][y] < 1: flag = 0 board[x][y] += 10000 stretch(x,y,0,1,0,0,1) stretch(x,y,1,0,0,0,1) stretch(x,y,0,0,1,0,1) stretch(x,y,0,0,0,1,1) stretch(x,y,1,0,1,0,1) stretch(x,y,1,0,0,1,1) stretch(x,y,0,1,0,1,1) stretch(x,y,0,1,1,0,1) else: flag = 1 return -1 if flag == 1: remove(board,x,y) flag = 0 return -1 else: return 1 def find_queen(board,row): for i in range(0,n): if board[row][i] >= 10000: return i return -1 def to_result(result,board): result.append([]) for i in board: result[-1].append("") for j in i: if j >= 10000: result[-1][-1] += 'Q' else: result[-1][-1] += '.' def backtrack(board,x,y): global result if y < n: if place_the_queen(x,y) == 1: if x == n-1: to_result(result,board) remove(board,x,y) y = n else: backtrack(board,x+1,0) else: backtrack(board,x,y+1) if y == n: column = find_queen(board,x-1) remove(board,x-1,column) if x-1 == 0 and column+1 == n: return else: backtrack(board,x-1,column+1) backtrack(board,0,0) return result