回溯法思想的应用

1、非递归实现皇后问题

#include<stdio.h>
#include<stdlib.h>
#define bool char
#define true 1
#define false 0
#define  N 110
int n;
bool col[N];  //列
bool dg[N];  //正对角线
bool udg[N];  //反对角线
char g[N][N];
int solution;
void dfs(int u)
{
    if(u==n)    //搜索完毕
    {
        solution++;
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++){
                printf("  ");
                printf("%c",g[i][j]);
            }
            printf("\n") ; //按行输出,没输出一行会换行
        } 
        printf("\n") ;    //每输出一种答案换行
        
        return ;
    }
  
    for(int i=0;i<n;i++)    //u为行,i为列
    {
        if(!col[i]&&!dg[u+i]&&!udg[u-i+n])
        {
            g[u][i]='Q';
            col[i]=dg[u+i]=udg[u-i+n]=true;
            dfs(u+1);
            col[i]=dg[u+i]=udg[u-i+n]=false;  //回溯
            g[u][i]='*';     //回溯
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) 
        for(int j=0;j<n;j++)
            g[i][j]='*';     //初始化
    dfs(0);  
    printf("%d皇后问题共有%d种摆放方案",n,solution) ;
    return 0;
}

2、递归算法解决皇后问题

#include<stdio.h>
#include<stdlib.h>
#define bool char
#define true 1
#define false 0
#define  N 110
int n;
bool col[N];  //列
bool dg[N];  //正对角线
bool udg[N];  //反对角线
char g[N][N];
int solution;
void dfs(int u)
{
    if(u==n)    //搜索完毕
    {
        solution++;
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++){
                printf("  ");
                printf("%c",g[i][j]);
            }
            printf("\n") ; //按行输出,没输出一行会换行
        } 
        printf("\n") ;    //每输出一种答案换行
        
        return ;
    }
  
    for(int i=0;i<n;i++)    //u为行,i为列
    {
        if(!col[i]&&!dg[u+i]&&!udg[u-i+n])
        {
            g[u][i]='Q';
            col[i]=dg[u+i]=udg[u-i+n]=true;
            dfs(u+1);
            col[i]=dg[u+i]=udg[u-i+n]=false;  //回溯
            g[u][i]='*';     //回溯
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) 
        for(int j=0;j<n;j++)
            g[i][j]='*';     //初始化
    dfs(0);  
    printf("%d后问题共有%d种摆放方案",n,solution) ;
    return 0;
}

3、素数圈

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 100
int n,x[N];
bool vis[N],flag=false;
bool checkPrime(int t)//约束条件 相邻的和为素数
{
    for(int j=2;j<=sqrt(t);j++)
    {
        if(t%j==0)
            return false;
    }
    return true;
}
void dfs(int i)
{
    if(i>n)
    {
        if(flag){
            printf("围成的圈是:");
            for(int j=1;j<i;j++)
                printf("%d ",x[j]);
            exit(0);
        }
        flag=true;
    }
 
    else
    {
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&checkPrime(x[i-1]+j))
            {
                vis[j]=true;
                x[i]=j;
                dfs(i+1);
                vis[j]=false;
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    dfs(1);
    return 0;
}