ap325第四天

ap325第四天

一月 13, 2025

八皇后問題

  • n皇后暴搜解答:
    (時間複雜度會爆)
    O(n2*n!)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    #include <bits/stdc++.h>

    using namespace std;
    int nq(int n){
        int P[14];
        int total=0;
        for(int i=0;i<n;i++){
            P[i]=i;
        }
        do{
            bool valid=true;
            for(int i=0;i<n;i++){
                for(int j=i+1;j<n;j++)
                    if(abs(P[i]-P[j])==j-i){ //P[i]-P[j])==j-i可以比對是否在同一斜線
                        valid=false;
                        break;
                    }
            }
            if(valid){
                total++;
            }
        }while(next_permutation(P,P+n)); //字典排序P到P+n
        return total;
    }
    int main()
    {
        for(int i=1;i<12;i++){
            cout<<nq(i)<<' ';
        }
        return 0;
    }

    以下為遞迴解:
    O(n*n!)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    #include <iostream>

    using namespace std;
    int nqr(int n,int k,int p[]){
        int total=0;
        if(k>=n){
            return 1;
        }
        for(int i=0;i<n;i++){   //嘗試當前行的每一個位置
            bool valid=true;
            for(int j=0;j<k;j++){
                if(p[j]==i || abs(i-p[j])==k-j){ //檢查是否與前面衝突
                    valid=false;
                    break;
                }
            }
            if(!valid){
                continue;
            }
            p[k]=i;
            total+=nqr(n,k+1,p);
        }

        return total;
    }
    int main()
    {
        int p[15];
        for(int i=1;i<12;i++){
            cout<<nqr(i,0,p)<<' ';
        }
        return 0;
    }
    遞迴解2
    (降低複雜度)
    比 O(n*n!) 低，因為會先標記後才進入遞迴
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    #include <bits/stdc++.h>

    using namespace std;
    int nqr(int n,int k,int p[]){
        if(k>=n) return 1;
        bool valid[n];
        int total=0;
        for(int i=0;i<n;i++) valid[i]=true; // y軸
        // mark
        for(int j=0;j<k;j++){
            valid[p[j]]=false; //p[j]是(p[j],j)的y軸數據
            int i=p[j]+k-j; //i=y軸數據+(當前x軸-x軸數據) 往左下
            if(i<n){
                valid[i]=false;
            }
            i=p[j]-k+j; //往右上
            if(i>=0){
            valid[i]=   false;
            }

        }
        for(int i=0;i<n;i++){
            if(valid[i]){
                p[k]=i;
                total+=nqr(n,k+1,p);
            }
        }

        return total;
    }


    int main()
    {
        int p[15];
        for(int i=1;i<12;i++){
            cout<<nqr(i,0,p)<<' ';
        }
        return 0;
    }