题目链接
参考链接
方法1 模拟
超时
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def genFlag(board):
rows=n
cols=n
flag=[]
for i in range(rows):
flag.append([1]*cols)
for i in range(rows):
if 'Q' in board[i]:
px=i
py=board[i].index('Q')
# 消除整列
for j in range(rows):
flag[j][py]=0
# 消除左上角
tx=px-1
ty=py-1
while(tx>=0 and ty>=0):
flag[tx][ty]=0
tx-=1
ty-=1
# 消除右上角
tx=px-1
ty=py+1
while(tx>=0 and ty<cols):
flag[tx][ty]=0
tx-=1
ty+=1
# 消除左下角
tx=px+1
ty=py-1
while(tx<rows and ty>=0):
flag[tx][ty]=0
tx+=1
ty-=1
# 消除右下角
tx=px+1
ty=py+1
while(tx<rows and ty<cols):
flag[tx][ty]=0
tx+=1
ty+=1
return flag
def genFlag2(x,y,flag):
rows=n
cols=n
px=x
py=y
# 消除整列
for j in range(rows):
flag[j][py]=0
# 消除左上角
tx=px-1
ty=py-1
while(tx>=0 and ty>=0):
flag[tx][ty]=0
tx-=1
ty-=1
# 消除右上角
tx=px-1
ty=py+1
while(tx>=0 and ty<cols):
flag[tx][ty]=0
tx-=1
ty+=1
# 消除左下角
tx=px+1
ty=py-1
while(tx<rows and ty>=0):
flag[tx][ty]=0
tx+=1
ty-=1
# 消除右下角
tx=px+1
ty=py+1
while(tx<rows and ty<cols):
flag[tx][ty]=0
tx+=1
ty+=1
return flag
def finish(k):
flag=1
for i in k:
flag*=i.count('Q')
return flag>0
out=[]
st=[]
if n==1:
return [["Q"]]
flags=[]
import copy
for i in range(n):
tmpr1=['.']*n
tmpr1[i]='Q'
tmp=[tmpr1]
for i in range(n-1):
tmp.append(['.']*n)
st.append(tmp)
flags.append(genFlag(tmp))
while(st):
tmp=st.pop(0)
flag=flags.pop(0)
for i in range(n):
if 'Q' not in tmp[i]:
# 找到放置所在行
for j in range(n):
if flag[i][j]==1:
k=copy.deepcopy(tmp)
k[i][j]='Q'
if finish(k):
k=[''.join(h) for h in k ]
if k not in out:
out.append(k)
else:
if k not in st:
st.append(k)
flags.append(genFlag2(i,j,copy.deepcopy(flag)))
return out
方法2 回溯
class Solution:
def solves(self, currentrow: int):
if currentrow == self.n:
self.add_result()
return
for i in range(self.n):
if i not in self.col:
if i - currentrow in self.diagonal1 or i + currentrow in self.diagonal2:
continue
self.col.append(i)
self.diagonal1.append(i-currentrow)
self.diagonal2.append(i+currentrow)
self.solves(currentrow + 1)
self.col.pop()
self.diagonal1.pop()
self.diagonal2.pop()
def add_result(self):
tem = []
for num in self.col:
tem.append('.' * num + 'Q' + '.' * (self.n - 1 - num))
self.res.append(tem)
def solveNQueens(self, n: int) -> List[List[str]]:
self.n = n
self.res = []
self.col = []
self.diagonal1, self.diagonal2 = [], []
self.solves(0)
return self.res
