---
tags: Coding
---
# 回朔法
## 排列組合
假如想要印出到1~5所有數的排列方式，我們可以先用遞迴的方式。首先跑一個迴圈列出第一個數字所有的可能並檢查有沒有陣列中有沒有重複的數字，當然第一次還沒有紀錄，所以陣列中所有的數字都會是0。接著進入第一次遞迴把上一輪的數字存起來。再跑一次迴圈，看看有沒有重複的，如果有就跳過一次，不會衍生出其他遞迴。最後所有的數字都跑過就可以印出結束迴圈。

#include<bits/stdc++.h>
using namespace std;
void func(int level,vector<int>arr){
    if(level==arr.size()){
        for(auto i:arr)cout<<i<<" ";
        cout<<endl;
        return ;
    }
    for(arr[level]=1;arr[level]<=arr.size();arr[level]++){
        if(count(arr.begin(),arr.begin()+level,arr[level])!=0 )continue;
        func(level+1,arr);
    }
    return;
}
signed main () {
    int level=0,Size=5;
    vector<int> arr(Size);
    func(level,arr);
    return 0;
}

## 八皇后
zj題目: https://zerojudge.tw/ShowProblem?problemid=a160

**解題想法**:
利用回朔法的特性窮舉出所有可能，方法類似上面排列組合。我們開一個陣列初始化0，紀錄有沒有放皇后。檢查方式是一排一排由左而右，由上而下。然後在每一次進入DFS後記錄上一輪皇后的位置以及它的影響範圍，用coloring來塗色，要記的皇后的範圍是8個方位。最後level==n表示每一排都看過了，就可以return，然後印出。

#include<bits/stdc++.h>
using namespace std;
int cnt=0;
//2代表皇后 1代表佔領了
void coloring(int n,vector<vector<char>> &queen,int level,int x){
    for(int i=0;i<n;i++){
        queen[level][i]='x';
    }
    for(int i=0;i<n;i++){
        queen[i][x]='x';
    }
    int b=level;
    int a=x;
    while(a>=0 && a<n && b>=0 && b<n){
        queen[b][a]='x';
        a++;
        b++;
    }
    b=level;
    a=x;
    while(a>=0 && a<n && b>=0 && b<n){
        queen[b][a]='x';
        a--;
        b++;
    }
    b=level;
    a=x;
    while(a>=0 && a<n && b>=0 && b<n){
        queen[b][a]='x';
        a++;
        b--;
    }
    b=level;
    a=x;
    while(a>=0 && a<n && b>=0 && b<n){
        queen[b][a]='x';
        a--;
        b--;
    }
    queen[level][x]='Q';
}
void dfs(int n,vector<vector<char>> queen,int level,int x){
    coloring(n,queen,level-1,x);
    if(level==n){
        for(auto i:queen){
            for(auto j:i)cout<<j;
            cout<<endl;
        }
        cout<<"---------------"<<endl;
        cnt++;
        return;
    }
    for(int i=0;i<n;i++){
        if(queen[level][i]!='0')continue;
        dfs(n,queen,level+1,i);
    }
    return;
}

int main(){
    int n=8,level=0;//n: 棋盤大小與皇后數量
    for(int i=0;i<n;i++){
        vector<vector<char>>queen(n);
        for(int j=0;j<n;j++){
            queen[j].resize(n,'0');
        }
        dfs(n,queen,level+1,i);
    }
    cout<<cnt;
    return 0;
}