###### tags: `Leetcode` `hard` `array` `python` `Top 100 Liked Questions`

# 51. N-Queens

## [題目來源:] https://leetcode.com/problems/n-queens/

## 題目:
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.


#### [圖片來源] https://leetcode.com/problems/n-queens/

## 解題想法:
queens:不能放在同行同列、也不能放在對角線
* 技巧 使用一維數組存即可:
上圖ex1可化為:[2,0,3,1]:
在第0行: 皇后放在第2列
在第1行: 皇后放在第0列
在第2行: 皇后放在第3列
在第3行: 皇后放在第1列
* 判斷是否對角線衝突到:
(x1,y1)、(x2,y2): 當abs(x1-x2)==abs(y1-y2) 則表示相同對角線

## Python:

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        def dfs(col,vals):
            if col==n: #每行都run好了
                res.append(vals)
                return 
            curStr='.'*n
            for row in range(n): #決定row的位置
                if check(col,row): #查看是否可以放置
                    board[col]=row
                    #遞迴決定下一行
                    dfs(col+1,vals+[ curStr[:row]+'Q'+curStr[row+1:] ])
        
        def check(col,row):
            for pos in range(col): #看先前的其他行是否已經有人列與當前row相等
                #若有哪列已經與row相等 or 斜對角相等 則false
                if board[pos]==row or abs(col-pos)==abs(row-board[pos]):
                    return False
            return True
            
        board=[-1]*n #board[x]=y : 第x行、第y列中放置queen
        res=[]
        dfs(0,[])
        return res

result=Solution()
ans=result.solveNQueens(n=4)
print(ans)