素数填表问题-回溯法搜索

int search_suitable(int * array, int beg, int end , int * tag, int *pos,int * result,int focus)
{
    bool check;
    for(int i=beg;i    {
        if(!tag[i])        //找出没有被使用的数
        {
            result[focus] = array[i];
            //检查是否满足质数要求   
            check = true;
            if(focus >2)
                check = is_prime(result[focus]+result[focus-3]);
            if(focus!=0 && focus%3!=0)
                check &= is_prime(result[focus]+result[focus-1]);
            if(check)
            {
                pos[focus] = i;        //标记位置
                tag[i]=1;
                return 1;
            }
        }
    }
    return 0;
}

非递归算法
void fill_number_game(int *iArray,int count)
{
    sort(iArray,count);
    //用于标记是否当前数已经填入方阵的数组
    int *tag = new int[count];
    int *pos = new int[count];
    for(int i=0;i    {
        tag[i]=0;    //全部都没使用
        pos[i]=0;
    }
    int result[9]={0};
    result[0]=iArray[0];
    tag[0]=1;
    i=0;
    int seq_num = 0;
    bool ended = false;
    bool set = false;
    while(!ended)
    {
        if(result[0]==iArray[count-1])
            set = true;
        if(i==8)
        {
            printf("第%3d种方案：\n",++seq_num);
            for(int j=0;j<9;j++)
            {
                printf("%4d",result[j]);
                if((j+1)%3==0 && (j!=0) )
                    printf("\n");
            }
            //回溯
            while(!check)
            {
                pos[i]=0;
                i--;
                tag[pos[i]] = 0;
                check = search_suitable(iArray,pos[i]+1,count,tag,pos,result,i);
            }
        }
        i++;                //向前搜索
        check = search_suitable(iArray,0,count,tag,pos,result,i); //找出合适的数读入
        while(!check)            //检查失败，回溯
        {
            pos[i]=0;        //去掉位置信息
            i--;
            if(i<0)
            {
                if(set)
                    ended = true;
                break;
            }
            tag[pos[i]]=0;            //重新标记为没有使用
            check = search_suitable(iArray,pos[i]+1,count,tag,pos,result,i);
        }
    }
}

递归算法：
bool used[Max];
int  pos[MAX];
static seq_num=0;
int *result;
void fill_number_game(int *iArray,int count, int i)
{
     if(i== count-1)
     {
            printf("第%3d种方案：\n",++seq_num);
            for(int j=0;j<9;j++)
            {
                printf("%4d",result[j]);
                if((j+1)%3==0 && (j!=0))  //每3个一行
                    printf("\n");
            }
            return;
     }
     if(i<0)
         return;
     for(int n = 0;n < count;++n)
     {
         if(!used[n])
         {
            if(search_suitable(iArray,n,count,used,pos,result,i)==false  )  
                 continue;  
            pos[i] = n;
            used[n] = true;
            fill_number_game(iArray,count, i+1);
            used[n] = false;
            pos[i] = 0;
         }
     }
  
}
int main()
{
    sort(iArray,count);
    result = new int[count];
    for(int i=0;i    {
        used[i]=0;    //全部都没使用
        pos[i]=0;
    }
    fill_number_game(iArray,count,result,0);
    return 0;
}