51. N-Queens Leetcode Python
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
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.."]]
这题的解法和前面一题N queen II 一样,规则是两个queen不能再同一个行,列或者diagnal 所以每个循环里面有 board[i]!=j abs(k-i)!=abs[board[i]-j]
其他的是常规的dfs解法
代码如下:
class Solution: # @return a list of lists of string def solveNQueens(self, n): def check(k,j,board): for i in range(k): if board[i]==j or abs(k-i)==abs(board[i]-j): return False return True def dfs(depth,board,valuelist,solution): #for i in range(len(board)): if depth==len(board): solution.append(valuelist) for row in range(len(board)): if check(depth,row,board): s='.'*len(board) board[depth]=row dfs(depth+1,board,valuelist+[s[:row]+'Q'+s[row+1:]],solution) board=[-1 for i in range(n)] solution=[] dfs(0,board,[],solution) return solution
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。