问答题 【说明】 本程序在3×3方格中填入1～N(N≥10)内的某9个互不相同的整数，使所有相邻两个方格内的两个整数之和为质数。试求出满足这个要求的所有填法。3×3方格中的每个方格按行按列(先行后列)序号排列为：0，1，2，3，4，5，6，7，8。 程序采用试探法，即从序号为0的方格开始，为当前方格寻找一个合理的可填整数，并在当前位置正确填入后，为下一方格寻找可填入的合理整数。如不能为当前方格找到一个合理的可填整数，就要回退到前一方格，调整前一方格的填入整数；直至序号为8的方格也填入合理的整数后，就找到了一个解，将该解输出。再调整序号为8的方格所填整数，继续去找下一个解。为了检查当前方格的填入整数的合理性，程序引入二维数组check Matrix，存放需要进行合理性检查的相邻方格的序号。 # include ＜stdio. h＞ # define N 12 int b[N+1]; int pos; int a[9];/* 用于存储诸方格所填入的整数*/ int AllNum=0;/* 统计有多少种填法*/ 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 write(int a[]) { int i, j; for(i=0; i＜3; i++) { for(j=0; j＜3; j++) printf("%3d", a[3*i+j]); printf("/n"); } } int isPrime(int m) { int i; if(m==2)return 1; if(m==1 ‖ m%2==0)return 0; for(i=3; i*i＜m;) { if(m%i==0)return 0; i+=2; } return 1; } int selectNum(int start) { int j; for(j=start; j＜=N; j++) if(b[j])return j; return 0; } int check()/*检查填入pos位置的整数是否合理*/ { int i,j; for(i=0; (j={{U}} (1) {{/U}})＞=0; i++) if(!isPrime(a[pos]+a[j])) {{U}}(2) {{/U}}; {{U}}(3) {{/U}}; } extend ()/* 为下一方格找一个尚未使用过的整数*/ { a[{{U}} (4) {{/U}}]=selectNum(1); b[a[pos]]=0; } void change ()/*为当前方格找下一个尚未使用过的整数(找不到回溯)*/ { int j; while(pos ＞=0 && (j=selectNum({{U}} (5) {{/U}}))==0) b[a[pos--]]=1; if(pos＜0)return; b[a[pos]]=1; a[pos]=j; b[j]=0; } int find () { int ok=1; pos=0; a[pos]=1; b[a[pos]]=0; do{ if(ok) if(pos==8) { write(a); change(); AllNum++;/* 统计有多少种填法*/ } else extend(); else change(); ok=check(); }while(pos＞=0); } void main() { int i; for(i=1; i＜=N; i++) b[i]=1; find(); prinrf("共有%d种不同填法!/n", AllNum); }