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.."]
]
Solution:
class Solution: # @return a list of lists of string def solveNQueens(self, n): solution = [] oneSolution = [] for i in range(0, n): row =[] for j in range(0, n): row.append('.') oneSolution.append(row) self.solveNQueensRec(0, n, oneSolution, solution) return solution def solveNQueensRec(self, row, n, oneSolution, solution): if row==n: tempSolution = [] for i in range(0,n): tempSolution.append(''.join(oneSolution[i])) solution.append(tempSolution) for col in range(0,n): if self.canAdd(oneSolution, row, col): oneSolution[row][col]='Q' self.solveNQueensRec(row+1, n, oneSolution, solution) oneSolution[row][col]='.' def canAdd(self, oneSolution, row, col): for i in range(0,row): if oneSolution[i][col]=='Q': return False if col-row+i>=0 and oneSolution[i][col-row+i]=='Q': return False if col+row-i<len(oneSolution) and oneSolution[i][col+row-i]=='Q': return False return True
No comments :
Post a Comment