C语言程序设计100例之（65）：方格填数
例65 方格填数
问题描述
给一个n*n的方格矩阵，还有n*n个整数，让你将这些整数填入矩阵，使得每行每列每个对角线上整数的和都相等。下面给出几个例子：
输入
第一行一个整数n.（1<=n<=4)
第二行n*n个整数 ai (-10^8<=ai<=10^8)
输出
第一行一个整数s 代表每行每列每个对角线的和值
接下来输出一个n*n的矩阵，表示填数方案。
数据保证有解，可能存在多种方案，输出字典序最小的（将每行顺次相连之后，字典序最小）
输入样例
1 2 3 4 5 6 7 8 9
输出样例
15
2 7 6
9 5 1
4 3 8
（1）编程思路。
将输入的n*n个整数保存到数组a中，这n*n个整数的总和除以n的值保存到变量sum中。为了输出时输出字典序最小的，先将数组a中的n*n个数按从小到大顺序排列，这样可以保证最先得到的可行解是字典序最小的。
之后按照从左到右从上到下的顺序将n*n个数填写到n*n个方格中。
编写递归函数int dfs(int x, int y)，其功能是对方格（x,y）填写数。每个格子可以在a[0]~a[n*n-1]中选取一个没有填过的数a[i]（vis[i]=0时表示a[i]可以填写）进行填写，填写后，递归调用dfs(x,y+1)填写下一个格子（若y=n，则递归调用的下一个格子为dfs(x+1,1)）。
在递归调用过程中可以进行剪枝：在每一行或每一列填写结束时，可以调用相应函数int chkRow(int row)或int chkCol(int col)判断这一行或这一列之和是否等于 sum，若不等于，则直接返回0，无需继续搜索。
所有方格填写结束后，判断最后一行、最后一列和两条对角线的和值是否都等于sum，若都等于，则找到一个可行解，返回1。
（2）源程序。
#include
#include
int n, a[25], ans[5][5], sum;
int vis[25]={0};
int chkRow(int row)
{
int i,tmp = 0;
for (i=1; i<=n; i++)
tmp+= ans[row][i];
return tmp == sum;
}
int chkCol(int col)
{
int i,tmp = 0;
for (i=1; i<=n; i++)
tmp += ans[i][col];
return tmp == sum;
}
int chkX()
{
int i,tmp1 = 0, tmp2 = 0;
for (i=1; i<=n; i++) {
tmp1 += ans[i][i];
tmp2 += ans[i][n+1-i];
}
return tmp1 == sum && tmp2 == sum;
}
int dfs(int x, int y)
{
if (x==n+1 && y==1)
{
return chkRow(n) && chkCol(n) && chkX();
}
if (x > 1 && y == 1 && !chkRow(x-1)) return 0;
if (x == n && y > 1 && !chkCol(y-1)) return 0;
int xx = x, yy = y+1;
if (y==n) { xx=x+1; yy = 1; }
int i;
for (i=0; i if (!vis[i]) { vis[i] = 1; ans[x][y] = a[i]; if (dfs(xx, yy)) return 1; vis[i] = 0; } } return 0; } int main() { scanf("%d",&n); int i,j,t; for (i=0; i scanf("%d",&a[i]); sum += a[i]; } sum/= n; for (i=0;i for (j=0;j if (a[j]>a[j+1]){ t=a[j]; a[j]=a[j+1]; a[j+1]=t; } dfs(1,1); printf("%d\n",sum); for (i=1; i<=n; i++) { printf("%d",ans[i][1]); for (j=2; j<=n; j++) { printf(" %d",ans[i][j]); } printf("\n"); } return 0; } 问题描述 数独是根据9×9 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1 - 9，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。 芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。 这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。 据介绍，目前数独游戏的难度的等级有一到五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所以数独游戏中，难度最高的等级。他还表示，他目前还没遇到解不出来的数独游戏，因此他认为“最具挑战性”的数独游戏并没有出现。 输入 一个未填的数独。 输出格式 填好的数独。 输入样例 8 0 0 0 0 0 0 0 0 0 0 3 6 0 0 0 0 0 0 7 0 0 9 0 2 0 0 0 5 0 0 0 7 0 0 0 0 0 0 0 4 5 7 0 0 0 0 0 1 0 0 0 3 0 0 0 1 0 0 0 0 6 8 0 0 8 5 0 0 0 1 0 0 9 0 0 0 0 4 0 0 输出样例 8 1 2 7 5 3 6 4 9 9 4 3 6 8 2 1 7 5 6 7 5 4 9 1 2 8 3 1 5 4 2 3 7 8 9 6 3 6 9 8 4 5 7 2 1 2 8 7 1 6 9 5 3 4 5 2 1 9 7 4 3 6 8 4 3 8 5 2 6 9 1 7 7 9 6 3 1 8 4 5 2 （1）编程思路。 定义二维数组int map[10][10];来保存所填写的数独，输入数据后，map[i][j]!=0表示格子（i,j）（0<=i<=8，0<=j<=8）已事先填写了数据，map[i][j]==0表示格子（i,j）尚没有填写数据，需要在1~9中选择一个数进行填写。 编写递归函数void dfs(int pos)对第pos个格子进行填写。显然，0<=pos<=80，当pos=81时，所有格子填写完毕，输出找到的解，同时置标志flag=1，这样可以结束后续的搜索，不再找其他的可行解。 第pos个格子对应的坐标位置为（x=pos/9，y=pos%9），若map[x][y]!=0，则第pos个格子已预先填写了数据，递归调用dfs(pos+1)直接填写下一个格子；若map[x][y]==0，则需要对第pos个格子填写一个数据，此时将数组vis[10]的元素先全部初始化为0，vis[i]=0表示数字i可以填写，vis[i]=1表示数字i不能填写在第pos个格子中，然后将第pos个格子所在行填写过的数字map[x][k]对应的vis[map[x][k]]置为1，第pos个格子所在列填写过的数字map[k][y]对应的vis[map[k][y]]置为1，还将第pos个格子所在的小3*3格子中填写过的数字对应的vis元素也置为1，这样可以选取1~9中某个vis[i]=0的数字i填写到第pos个格子中，填写后递归调用dfs(pos+1)继续填写下一个格子，直到pos=81，所有格子填写完毕。 （2）源程序。 #include #include int map[10][10]; int flag; void dfs(int pos) { int i,j; if (pos == 81){ for (i=0; i<9; i++){ for (j=0; j<9; j++){ printf("%d ",map[i][j]); } printf("\n"); } flag = 1; return ; } if (flag) return ; if (map[pos/9][pos%9]){ dfs(pos+1); } else{ int x=pos/9,y=pos%9; int vis[10]; memset(vis,0,sizeof(vis)); for (i=0; i<9; i++){ if (x != i) vis[map[i][y]] = 1; if (y != i) vis[map[x][i]] = 1; } int tx = x/3*3; int ty = y/3*3; for (i=0; i<3; i++){ for (j=0; j<3; j++){ if (tx+i==x && ty+j==y) continue; vis[map[tx+i][ty+j]] = 1; } } for (i=1; i<=9; i++){ if (!vis[i]){ map[x][y] = i; dfs(pos+1); if (flag) return ; map[x][y] = 0; } } } } int main() { int i,j; for (i=0; i<9; i++){ for (j=0; j<9; j++) scanf("%d",&map[i][j]); } flag =0; dfs(0); return 0; } 问题描述 相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择（如图）： 并且每一方格只能用一层地毯，迷宫的大小为2k ×2k的方形。当然，也不能让公主无限制的在那儿等，对吧？由于你使用的是计算机，所以实现时间为1s。 输入 输入文件共2 行。 第一行：k，即给定被填补迷宫的大小为2k ×2k （0 第二行：x,y，即给出公主所在方格的坐标（x为行坐标，y为列坐标），x和 y之间有一个空格隔开。 输出 将迷宫填补完整的方案：每一行为x y c（x,y为毯子拐角的行坐标和列坐标， c为使用毯子的形状，具体见上面的图1，毯子形状分别用 1,2,3,4表示，x,y,c之间用一个空格隔开）。 输入样例 3 3 3 输出样例 5 5 1 2 2 4 1 1 4 1 4 3 4 1 2 4 4 1 2 7 3 1 5 4 1 8 3 3 6 3 4 8 1 7 2 2 5 1 4 6 3 2 8 1 2 8 4 1 7 7 1 6 6 1 5 8 3 8 5 2 8 8 1 （1）编程思路。 大小为2k ×2k的迷宫可以分割成为4个2(k-1)*2(k-1)的小迷宫，分别标记为左上角迷宫。右上角迷宫、左下角迷宫和右下角迷宫，如图1所示。 图1 4个小迷宫 公主的位置必然在这四个小迷宫的某个迷宫内，其余三个小迷宫中没有被公主占用。可以使用一个“L”型毯子覆盖在这三个小迷宫的汇合之处，这个“L”型毯子的3个小块一定在每个小迷宫中放置1个，这样可以将这三个小块各看成一个“假公主”，这样4个小迷宫中每个迷宫中均有1个位置被公主占用，由此可以将2k ×2k的迷宫地毯填补问题分割成为4个较小规模的2(k-1)*2(k-1)的小迷宫地毯填补问题，递归这种分割，直至小迷宫转化为1*1的1个格子。 例如，设公主在左上角的小迷宫中，这样可以在其余3个小迷宫交汇处放置1个“1”行地毯，这样每个小迷宫中均有1个格子放置了公主，如图2所示。 图2 公主在左上角迷宫中 进一步以样例为例进行描述，样例中公主的坐标为（3，3），位于左上角小迷宫中，左上角的4x4小迷宫中公主占了1格，就还剩15个方格，这样15/3=5余0，则可以把地毯铺完。按图2思想，在剩下3个4x4的小迷宫的交汇处铺上一个地毯（即(5,5,1)），使其各占1格，从16变为15格，这样也可保证地毯可以正好铺满。然后对每个小迷宫各自进一步递归，如图3所示。 图3 样例的递归示例 编写递归函数void laying(int a,int b,int x,int y,int len)来铺设地毯，其中参数a,b代表当前小迷宫的左上角顶点，x,y代表公主位置，len表示迷宫大小为len*len。 若x<=a+len/2-1 && y<=b+len/2-1，则公主在左上角小迷宫中，此时在其余3个小迷宫的交汇处铺设一个“1”型地毯，用语句printf("%d %d 1\n",a+len/2,b+len/2);输出即可，这样原来大小为len*len的迷宫可以分割为4个(len/2)*(len/2)的小迷宫，因此递归调用如下： laying(a,b,x,y,len/2); laying(a,b+len/2,a+len/2-1,b+len/2,len/2); laying(a+len/2,b,a+len/2,b+len/2-1,len/2); laying(a+len/2,b+len/2,a+len/2,b+len/2,len/2); 同理可以处理公主在右上角、左下角和右下角的情形。 需要注意的是按样例的输出，递归的顺序应该是左上角，右上角，左下角，右下角。 （2）源程序。 #include void laying(int a,int b,int x,int y,int len) // a,b代表当前棋盘的左上角顶点，x,y代表公主位置 { if (len==1) return ; len=len/2; if (x<=a+len-1 && y<=b+len-1) // 公主在左上角棋盘 { printf("%d %d 1\n",a+len,b+len); laying(a,b,x,y,len); laying(a,b+len,a+len-1,b+len,len); laying(a+len,b,a+len,b+len-1,len); laying(a+len,b+len,a+len,b+len,len); } else if (x<=a+len-1 && y>b+len-1) // 公主在右上角棋盘 { printf("%d %d 2\n",a+len,b+len-1); laying(a,b,a+len-1,b+len-1,len); laying(a,b+len,x,y,len); laying(a+len,b,a+len,b+len-1,len); laying(a+len,b+len,a+len,b+len,len); } else if (x>a+len-1 && y<=b+len-1) //公主在左下角棋盘 { printf("%d %d 3\n",a+len-1,b+len); laying(a,b,a+len-1,b+len-1,len); laying(a,b+len,a+len-1,b+len,len); laying(a+len,b,x,y,len); laying(a+len,b+len,a+len,b+len,len); } else // 公主在右下角棋盘 { printf("%d %d 4\n",a+len-1,b+len-1); laying(a,b,a+len-1,b+len-1,len); laying(a,b+len,a+len-1,b+len,len); laying(a+len,b,a+len,b+len-1,len); laying(a+len,b+len,x,y,len); } } int main() { int m; int k,x,y; scanf("%d %d %d",&k,&x,&y); m=1< laying(1,1,x,y,m); return 0; } 问题描述 康托集是由乔治·康托发现的。它是一种更简单的分形。这是一个无限过程的结果，因此对于这个程序，打印整个集合的近似值就足够了。以下步骤描述了输出给定整数n所对应近似康托集的一种方法： 1）以长度为n3的一串破折号构成的虚线开始 2）将虚线的中间三分之一替换为空格。在原始字符串的每一端留下一根由连续的破折号构成的虚线。 3）将每组虚线的中间三分之一再替换为空格。重复此操作，直到每组虚线由一个破折号组成。 例如，如果近似顺序为3，则从包含27个破折号的字符串开始： --------------------------- 将虚线中间三分之一变成空格 ： --------- --------- 然后再将每组虚线中间三分之一变成空格： --- --- --- --- 再来一遍： - - - - - - - - 当破折号组的长度均为1时，此过程停止。输出时不应该打印程序中的中间步骤。只应显示上面最后一行给出的最终结果。 输入 输入包括多组测试用例。每个测试用例占一行，为一个介于0和12之间（包括0和12）的数字。 输出 必须输出康托集的近似值，后跟换行符。在康托集近似前后没有空格。行中应该出现的唯一字符是“-”和“ ”。 输入样例 输出样例 - - - - - - - - - - （1）编程思路。 设S(n)表示长度为n3的近似康托集，显然可以发现S(n)=S(n-1)+n*n*n/3个空格+S(n-1)。 编写递归函数void cantor(int s,int e)，参数s和e分别表示描述近似康托集字符串的开始位置和结束位置，显然若e-s==1，字符串中1个字符，直接赋值为“-”，递归调用结束；否则，分别对前三分之一进行递归调用cantor(s,s+(e-s)/3); ，对后三分之一进行递归调用cantor(s+2*(e-s)/3,e); 。 （2）源程序1。 #include #include char ans[1000000]; void cantor(int s,int e) { if (e-s==1) { ans[s]='-'; return; } int len=(e-s)/3; cantor(s,s+len); // 对前三分之一进行递归 cantor(s+2*len,e); // 对后三分之一进行递归 } int main() { int i,n,len,a[13]={1}; for (i=1;i<=12;i++) a[i]=a[i-1]*3; while(scanf("%d",&n)!=EOF) { len = a[n]; memset(ans,' ',sizeof(ans)); //对整个数组赋值为空格 cantor(0,len); for (i=0;i printf("%c",ans[i]); printf("\n"); } return 0; } 也可以编写非递归程序如下。 （3）源程序2。 #include #include char ans[13][540000]; int main() { int i,j,a[13]={1}; for (i=1;i<=12;i++) a[i]=a[i-1]*3; strcpy(ans[0],"-"); strcpy(ans[1],"- -"); for (i=2; i<=12;i++) { strcpy(ans[i],ans[i-1]); int k=strlen(ans[i-1]); for (j = 0; j ans[i][j+k]=' '; ans[i][2*k]='\0'; strcat(ans[i],ans[i-1]); } int n; while (scanf("%d",&n)!=EOF) { printf("%s\n",ans[n]); } return 0; }习题65
65-1 数独
65-2 地毯填补问题
65-3 康托集