[LeetCode] 51. N-Queens

轉自LeetCode

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.."]
]

<Solution>

經典的 recursive 題目，解法就是用 DFS

有幾個小技巧 (參考資料)

• 如果(row1,col1)和(row2,col2)在同個對角線上的話，abs(row1 - row2) = abs(col1 - col2)

• 不需要用二維陣列來存Ｑ放的位置，用一維陣列即可。state[i] 存放的是在第 i 列(row)，Ｑ放的 col。例如 state[4] = 2，代表 row 4，Ｑ放的位置在 col 2。因此，檢查 row k 是不是可以放在某個 col，只要檢查 row 0 到 row k-1 的值有沒有等於 col 就可以了

另外，在參考資料裡面，還有提到一個神解

用到 bit  mask 的概念，有空可以看一下

recursive 解法如下