[規格/C+]9663番N-Queen

6382 ワード
白駿 ついせき テキストリンク

問題は次のとおりです.

難しいです.私もYouTubeや他の資料を参考にして、この問題を理解して説明し、その後解答しました.
これは後追跡の定式化と同じ問題のようです.
私は行為基準で皇后を手配した.row[k]=i;これはk行のi位置にQueenが置かれていることを意味する.
もし皇后がすでに席に着いていたら、もしあなたが彼女をここに置くことができたら
(配置可能かどうかについては、関数チェックを使用しました.)
💡位置を配置できるかどうか
  • 同じ線上に置けば->row[i]=row[t]
  • 同一対角線上にある場合->abs(row[t]-row[i])=t-i
    (対角線の場合、座標平面を考えるのは簡単です.
    座標平面上の2点の「x座標値の差=y座標値の差」の場合、同じ対角線上に配置されます.)
    • 次の行に使用するために、値+1をNQueen関数のパラメータに追加します.
    (2 D配列がタイムアウトしたため、1 D配列を使用する必要があります.)
    完全なコードは次のとおりです.🙆🏻‍♀️
    #include <bits/stdc++.h>
using namespace std;

int n, total=0;
int row[15];

bool check(int t){
    for(int i=0; i<t; i++){
        if(row[i]==row[t] || abs(row[t]-row[i])==t-i) return false;
    }
    // 같은 라인에 있거나 || 대각선에서 겹치는 경우 -> false 반환
    
    return true;
}

void NQueen(int k){
    if(k==n) total++;
    else{
        for(int i=0; i<n; i++){
            row[k]=i;
            if(check(k)) NQueen(k+1);
        }
    }
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  cin>>n;
  NQueen(0);
  cout<<total<<"\n";
}

    これをlispと書きます
    フアン...これですか.🤧
    白駿1181
    +宣言変数