面试题 08.12. 八皇后
设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
注意：本题相对原题做了扩展
示例:
输入：4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释: 4 皇后问题存在如下两个不同的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
Code:
class Solution(object):
def __init__(self
):
self
.ans
= []
def solveNQueens(self
, n
):
"""
:type n: int
:rtype: List[List[str]]
"""
self
.helper
([-1]*n
,0,n
)
return self
.ans
def helper(self
,columnPositions
,rowIndex
,n
):
if rowIndex
== n
:
self
.printSolution
(columnPositions
,n
)
return
for column
in range(n
):
columnPositions
[rowIndex
] = column
if self
.isValid
(columnPositions
,rowIndex
):
self
.helper
(columnPositions
,rowIndex
+1,n
)
def isValid(self
,columnPositions
,rowIndex
):
for i
in range(rowIndex
):
if columnPositions
[i
] == columnPositions
[rowIndex
]:
return False
elif abs(columnPositions
[i
]-columnPositions
[rowIndex
]) == rowIndex
-i
:
return False
return True
def printSolution(self
,columnPositions
,n
):
tmp
= []
for row
in range(n
):
line
= ""
for column
in range(n
):
if columnPositions
[row
] == column
:
line
+= "Q"
else:
line
+= "."
tmp
.append
(line
)
self
.ans
.append
(tmp
)
