算法分享-搜索与回溯

算法分享-搜索与回溯（八皇后、数独、填色）

八皇后

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int n;
char ans[N][N]; 
bool l[N],r[N],rp[N];  // 上下斜方向是否被占用
void cAp(bool cAp_flag){  // 格式化输入输出
	for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(cAp_flag)ans[i][j]='.';
            cout<<ans[i][j];
        }
        if(!cAp_flag)cout<<'\n';
    }
}
void dfs(int x){
    if(x==n+1){  // 结束条件
        cAp(0)
        cout<<endl;
    }else{      
        for(int i=1;i<=n;i++){
            if(!l[i]&&!r[i+x]&&!rp[n-i+x]){
                ans[x][i]='Q';  // 皇后放置
                l[i]=r[i+x]=rp[n-i+x]=1;
                dfs(x+1);
                l[i]=r[i+x]=rp[n-i+x]=0;
                ans[x][i]='.';  //还原现场，因为不止有一个结果符合条件，dfs的精髓所在
            }
        }
    }
}
int main(void){
    cin>>n;
    cAp(1); // 初始化ans 
    dfs(1);
}

数独求解

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int ans[N][N];
bool flag=0;
void cAp(bool cAp_flag){
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            if(cAp_flag)cin>>ans[i][j];
            else cout<<ans[i][j]<<' ';
        }
        if(!cAp_flag)cout<<'\n';
    }
}

void dfs(int x,int y){
    if(flag) return ;
    if(x==9){  // 结束条件
        flag=1;
        return ;
    }
    if(ans[x][y]!=0){ // 控制跳过非操作位
        if(y+1<9) dfs(x,y+1);
        else dfs(x+1,0);
        return ;
    }

    // int vis[15]={};
    vector<int> vis(15,0)
    for(int i=0;i<9;i++){ // 统计横竖方向各个数字出现个数
         if(ans[x][i]!=0) vis[ans[x][i]]++;
         if(ans[i][y]!=0) vis[ans[i][y]]++;
    }

    int r=x/3*3,c=y/3*3;
    for(int i=r;i<r+3;i++){ // 统计周边正方形各个数字出现个数
        for(int j=c;j<c+3;j++){
            if(ans[i][j]!=0) vis[ans[i][j]]++;
        }
    }
    for(int i=1;i<=9;i++){ 
        if(!vis[i]){ // 如果i未出现过
            ans[x][y]=i; 
            if(y+1<9) dfs(x,y+1); // 控制左右或上下走
            else dfs(x+1,0);
            if(flag) return ; //结束条件
            ans[x][y]=0; //还原现场，因为不止有一个i符合未出现过的条件，dfs的精髓所在
        }
    }
}

int main(void){
    cAp(1);
    dfs(0,0);
    cAp(0);
}