[说明]
以下[C程序]所完成的功能是在3x3方格中填入数字1～n(n≥10)内的某9个互不相同的整数，使所有相邻两个方格内的两个整数之和为质数。系统输出满足该要求的所有填法。系统的部分输出结果如图3-18所示。

图3-18 系统的部分输出结果
3×3方格从第1行左上角方格开始的序号分别为0、1、2，第2行左边方格开始的序号分别为3、4、 5，第3行左下角方格开始的序号分别为6、7、8。以下[C程序]采用试探法，即从序号为0的方格(左上角)开始，为当前方格寻找一个合理的可填整数，并在当前位置正确填入后，为下一方格寻找可填入的合理整数。如不能为当前方格寻找一个合理的可填整数，就要后退到前一方格，调整前一方格的整数。直至序号为8的方格(右下角)也填入合理的整数时，就找到了一个解，将该解输出，并调整序号为8的方格所填的整数，继续去找下一个解。
为了检查当前方格的填入整数的合理性，C程序引入二维数组ChECkmAtrix，用于存放需要进行合理性检查的相邻方格的序号。
[C程序]
#inCluDE ＜stDio.h＞
#DEFinE n 12
int A [9]; /* 用于存储方格所填入的整数 */
int B[n+1];
int pos;
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 == o)
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 = (1) ) ＞= 0; i++)
iF (!isprimE(A[pos] + A[j]))
(2) ;
(3) ;
ExtEnD () /* 为下一方格找一个尚未使用过的整数 * /
A[ (4) ] = sElECtnum(1);
B[A[pos]] = 0;
voiD ChAngE() /* 为当前方格找下一个尚未使用过的整数(找不到回溯) */
int j;
whilE (pos ＞= 0 && (j = sElECtnum( (5) )) == 0
(6) ;
iF (pos ＜ 0)
rEturn;
B[A[pos]] = 1;
A[pos] = j;
B[j] = 0;
FinD ( )
int ok = 1;
pos = 0; A[pos] = 1; B[A[pos]] = 0;
DE
iF (ok)
iF ( (7) )
writE (A);
ChAngE( );
ElsE
ExtEnD( );
ElsE
ChAngE( );
ok = ChECk(pos);
whilE (pos ＞=0);
mAin( )
int i;
For (i = 1; i ＜=n; i++)
B[i] = 1;
FinD( );