動機
複習backtrack
Problem
The n-queens puzzle is the problem of placing n
queens on an n x n
chessboard such that no two queens attack each other.
Given an integer n
, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q'
and '.'
both indicate a queen and an empty space, respectively.
Example 1:
Input: n = 4Output: [[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1Output: [[Q]]
Constraints:
1 <= n <= 9
Sol
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
tbl = []
for _ in range(n):
tmp = []
for _ in range(n):
tmp.append(".")
tbl.append(tmp)
def good(taken, j):
return not any([abs(taken[dep] - j) in [0, len(taken)-dep] for dep in range(len(taken))])
ret = []
def bt(i,taken=[]):
if i == n:
ret.append([''.join(l) for l in tbl])
else:
for x in range(n):
tbl[i][x] = "Q"
if good(taken, x):
bt(i+1, taken+[x])
tbl[i][x] = "."
bt(0)
return ret