[LintCode 33] N Queens (N 皇后问题)
Description
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击。
给定一个整数n，返回所有不同的n皇后问题的解决方案。
每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。
Example:
<!-- Input:4 -->
<!-- Output: -->
[
// Solution 1
[".Q..",
"...Q",
"Q...",
"..Q."
],
// Solution 2
["..Q.",
"Q...",
"...Q",
".Q.."
]
]
Note
皇后间不能相互攻击的条件是：
- 任何一行/列只能有一个皇后
- 任何一个斜边（对角线，45度斜边
对于第一种情况，增加取值时直接判定对应横/纵坐标是否被占用即可，
X Q X X
X X X Q
Q X X X
X X Q X
由[1, 3, 0, 2]表示，求(0, 1, 2, 3)满足条件的全排列，该表示方式决定不会有行冲突
对于第二种情况，需要检查列冲突（对角线）冲突，在对角线上：横/纵 坐标之 和/差 相等。
Update Review
Code
Python3 on LintCode
PS: cols[i]中存储的是第i行中应该在第几列摆放皇后
class Solution:
"""
@param: n: The number of queens
@return: All distinct solutions
"""
def solveNQueens(self, n):
results = []
cols = []
self.search(n, cols, results)
return results
#DFS Recursion
def search(self, n, cols, results):
row = len(cols)
if row == n:
results.append(self.draw_result(cols))
for col in range(n):
if self.is_valid(col, cols, row):
cols.append(col)
self.search(n, cols, results)
cols.pop()
#Judge whether the append mark is valid or not
def is_valid(self, col, cols, row):
for x, y in enumerate(cols):
if y == col:
return False
if x + y == col + row or x - y == row - col:
return False
return True
#add one success permutation
def draw_result(self, cols):
print(cols)
new_result = []
n = len(cols)
for i in range(n):
row = []
for j in range(n):
if cols[j] == i:
row.append('Q')
else:
row.append('.')
new_result.append(''.join(row))
return new_result
Ref Code
本参考程序来自九章算法，由 @令狐冲 提供
用 visited 来标记 列号，横纵坐标之和，横纵坐标之差 有没有被用过
class Solution:
"""
@param: n: The number of queens
@return: All distinct solutions
"""
def solveNQueens(self, n):
boards = []
visited = {
'col': set(),
'sum': set(),
'diff': set(),
}
self.dfs(n, [], visited, boards)
return boards
def dfs(self, n, permutation, visited, boards):
if n == len(permutation):
boards.append(self.draw(permutation))
return
row = len(permutation)
for col in range(n):
if not self.is_valid(permutation, visited, col):
continue
permutation.append(col)
visited['col'].add(col)
visited['sum'].add(row + col)
visited['diff'].add(row - col)
self.dfs(n, permutation, visited, boards)
visited['col'].remove(col)
visited['sum'].remove(row + col)
visited['diff'].remove(row - col)
permutation.pop()
# O(1)
def is_valid(self, permutation, visited, col):
row = len(permutation)
if col in visited['col']:
return False
if row + col in visited['sum']:
return False
if row - col in visited['diff']:
return False
return True
def draw(self, permutation):
board = []
n = len(permutation)
for col in permutation:
row_string = ''.join(['Q' if c == col else '.' for c in range(n)])
board.append(row_string)
return board
This blog is under a CC BY-NC-SA 3.0 Unported License
本文使用 CC BY-NC-SA 3.0 中国 协议许可
署名-非商业性使用-相同方式共享（BY-NC-SA）：使用者可以对本创作进行共享、演绎，但使用时须进行署名（同时标明是否（对原始作品）作了修改），且不得运用于商业目的，采用本创作的内容必须同样采用本协议进行授权。详情请参考协议细则。
本文链接：https://dataleoz.com/lintcode-n-queens/