N Queen
题目描述
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.
For example, There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
解题方法
N queen的规则是任意两个queen都不能攻击到彼此,而queen的攻击路线是直线或者对角线上,所以需要check的有
- 行
- 列
- 对角线
其实就类似于sudoku问题,sudoku是检查行,列和小的正方形. 这里不像sudoku那样填入到一个matrix里,当然如果我们自己 建一个matrix也是可以的,但是我们并不需要记录那么多的信息,只需要记录queen的位置,并且方便check valid就可以了。
我们可以用一个array来保存queen的信息,array的index表示行,而value就表示列,因为填入n个queen到n*n里的,其实也就是 依次每行填入一个queen,而列的选择也是在n的范围内,就变成了一个找出n的permutation的问题(这里多的条件是要满足 对角线没有queen的条件,所以要加一个check)。
row
array记录信息used
array记录用过的column number- 每填入一个number的时候要check对角线的条件是否满足
Solution
class Solution(object):
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
if not n:
return [[]]
row = []
used = [False for i in range(n)]
results = []
self.helper(results, row, used, n)
results = self.getMatrix(results, n)
return results
def helper(self, results, row, used, n):
if len(row) == n:
newList = list(row)
results.append(newList)
for j in range(n):
if not used[j]:
row.append(j)
if self.checkValid(row):
used[j] = True
self.helper(results, row, used, n)
row.pop()
used[j] = False
else:
row.pop()
# check 是否斜线上有两个queen
def checkValid(self, row):
length = len(row)
for i in range(length):
for j in range(i + 1, length):
if abs(row[i] - row[j]) == abs(i-j):
return False
return True
# 用于得到最后的".......Q."形式的结果
def getMatrix(self, results, n):
result = []
for i in range(len(results)):
string = ""
for j in range(n):
string += "."
matrix = [string for j in range(n)]
for k in range(len(results[i])):
st = matrix[k]
st = list(st)
index = results[i][k]
st[index] = "Q"
matrix[k] = "".join(st)
result.append(matrix)
return result