【筆記】N-Queens (N皇后問題)

【範例】在一個 N×N 的方格裡，放上 N 個皇后，請你找出讓它們彼此之間無法攻擊到對方的排法。
輸入說明：輸入一個正整數 N。
輸出說明：請你印出所有合乎條件的排法以及這些排法的個數。
PS. 因為每一列(row)只會有一個皇后，所以只要印出每一列的皇后所在的位置(column index)即可。

【練習】ZeroJudge d324: 00750 – 8 Queens Chess Problem【題解】
【練習】GreenJudge b039: 最終兵器X【題解】

• row[pre]：紀錄col-pre上的皇后所在的row number
• 待檢查座標：(r, c)
• 已經放置皇后的座標：(row[pre], pre)
• 函數 check(r, c)：檢查座標(r, c)是否可以擺放新的皇后
  • 檢查在 col-c 前面的所有 columns (pre)
  • 判斷 row-r (同一列) 是否已經有皇后
  • 判斷對角線上是否已經有皇后：abs ( row[ pre ] – r ) == abs ( pre – c )

bool check(int r, int c) {
    for (int pre=0; pre<c; pre++) {
        if (row[pre]==r || (abs(row[pre] - r) == abs(pre - c))) {
            return false;
        }
    }
    return true;
}