质数填表问题的回溯算法

//质数填表问题处理头文件
//质数填表问题的回溯算法
/*
 作者：成晓旭
 时间：2001年10月9日(15:00:38-16:00:00)
 内容：完成质数填表问题的回溯算法
 ===================================================
 问题描述:
  在9(3*3)个方格的方阵中填入数字1-N(N>=10)内的某9个数字,
 每个方格填一个整数,使所有相邻两个方格内的两个整数之和为质
 数.
 编程思想:
 {
  int m=8,ok=1;
  int n=8;
  do
  {
   if(ok)
   {
    if(m==n)
    {
     输出解;
     调整; 
    }
    else
     扩展; //向前试探
   }
   else
    调整;  //向后回溯
   ok = 检查前m个整数填写的合理性

  }while(m!=0)
 }
*/
#include "stdlib.h"
#define  MAXN 100
#define  N 12
int pnumber[MAXN];
int flag[N+1];
int checkMatrix[][3] = {{-1},{0,-1},{1,-1},{0,-1},{1,3,-1},{2,4,-1},{3,-1},{4,6,-1},{5,7,-1}};
//显示输入填写的数字
void PrintSetPrimeNumber(int array[])
{
 int i,j;
 for(i=0;i<3;i++)
 {
  for(j=0;j<3;j++)
   printf("%4d",array[3*i+j]);
  printf("\n");
 }
 scanf("%*c");
}
//判断自然数是否是质数
int IsPrimeNumber(int m)
{
 int i;
 int primes[] = {2,3,5,7,11,13,17,19,23,29,-1};
 if((m == 1) || (m % 2 == 0)) return(0); /*非质数*/
 for(i=0;primes[i]>0;i++)
  if(m == primes[i])   return(1); /*质数*/
 for(i=3;i*i <=m;)
 {
  if(m % i == 0) return(0); /*非质数*/
  i+=2;
 }
 return(1);  /*质数*/
}
//选择下一个要试探填写的自然数
int SelectNumber(int start)
{
 int i;
 for(i=start;i<=N;i++)
  if(flag[i])  return(i);
 return(0);
}
//查测当前位置的插入数据是否合理
int Check(int pos)
{
 int i,j;
 if(pos < 0)  return(0);
 for(i=0;((j=checkMatrix[pos][i]) >=0);i++)
  if(!IsPrimeNumber(pnumber[pos] + pnumber[j])) return(0);
 return(1);
}

int Extend(int pos)
{
 pnumber[++pos] = SelectNumber(1);
 flag[pnumber[pos]] = 0;
 return(pos);
}

int Change(int pos)
{
 int j;
 while((pos >= 0) && (j = SelectNumber(pnumber[pos]+1)) == 0)
  flag[pnumber[pos--]] = 1;
 if(pos<0) return(-1);
 flag[pnumber[pos]] = 1;
 pnumber[pos] = j;
 flag[j] = 0;
 return(pos);
}

void Find()
{
 int ok = 1,pos = 0;
 pnumber[pos] = 1;
 flag[pnumber[pos]] = 0;
 do
 {
  if(ok)
  {
   if(pos == 8)
   {
    PrintSetPrimeNumber(pnumber); /*输入填写结果*/
    pos = Change(pos); /*调整下一个将填入的自然数*/
   }
   else
    pos = Extend(pos); /*扩展填写范围<试探>*/
  }
  else
   pos = Change(pos); /*调整下一个将填入的自然数<回溯>*/
  ok = Check(pos);

 }while(pos>=0);
} 

编辑 webmaster