按照國(guó)際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。

n皇后問(wèn)題研究的是如何將n個(gè)皇后放置在n×n的棋盤(pán)上，并且使皇后彼此之間不能相互攻擊。

給你一個(gè)整數(shù)n，返回所有不同的n皇后問(wèn)題的解決方案。

每一種解法包含一個(gè)不同的n皇后問(wèn)題的棋子放置方案，該方案中'Q'和'.'分別代表了皇后和空位。

示例 1：

輸入：n = 4

輸出：

[[".Q..","...Q","Q...","..Q."],

["..Q.","Q...","...Q",".Q.."]]

解釋：如上圖所示，4 皇后問(wèn)題存在兩個(gè)不同的解法。

示例 2：

輸入：n = 1

輸出：[["Q"]]

提示：

• 1 <= n <= 9

回溯算法解決

這題和數(shù)獨(dú)都是使用回溯算法解決的，回溯算法就是不斷嘗試，關(guān)于回溯算法我們講過(guò)很多，回溯算法有一個(gè)經(jīng)典的模板，這里我們就以n等于4為例來(lái)畫(huà)個(gè)圖看下

n等于4的時(shí)候?qū)嶋H上是有兩種結(jié)果的，因?yàn)閳D畫(huà)不下，這里只畫(huà)出來(lái)一個(gè)結(jié)果。根據(jù)上面的圖我們可以看到它其實(shí)就是一顆n叉樹(shù)，我們來(lái)看下代碼