The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. (N皇后的问题,求所有解)
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.
class : defcheck(self, matrix, _i, _j): for i in range(self.n): for j in range(self.n): if matrix[i][j] == 'Q': if j == _j or abs(_i - i) == abs(_j - j): returnFalse returnTrue
defdfs(self, i, matrix): if (i == self.n): result = [] for row in matrix: result.append(''.join(row)) self.result.append(result) else: for j in range(self.n): if self.check(matrix, i, j): matrix[i][j] = 'Q' self.dfs(i+1, matrix) matrix[i][j] = '.' defsolveNQueens(self, n): """ :type n: int :rtype: List[List[str]] """ self.n = n self.result = []
matrix = [['.'for _ in range(self.n)] for _ in range(self.n)]
近期评论