【筆記】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;
}
分享本文 Share with friends