例65 方格填数
问题描述
给一个n*n的方格矩阵，还有n*n个整数，让你将这些整数填入矩阵，使得每行每列每个对角线上整数的和都相等。下面给出几个例子：
输入
第一行一个整数n.（1<=n<=4)
第二行n*n个整数 ai (-10^8<=ai<=10^8)
输出
第一行一个整数s 代表每行每列每个对角线的和值
接下来输出一个n*n的矩阵，表示填数方案。
数据保证有解，可能存在多种方案，输出字典序最小的（将每行顺次相连之后，字典序最小）
输入样例
3
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 <stdio.h>
#include <string.h>
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<n*n; 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<n*n; i++) {
scanf("%d",&a[i]);
sum += a[i];
}
sum/= n;
for (i=0;i<n*n-1;i++)
for (j=0;j<n*n-1-i;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;
}
习题65
65-1 数独
问题描述
数独是根据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 <stdio.h>
#include <string.h>
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;
}
65-2 地毯填补问题
问题描述
相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择（如图）：
并且每一方格只能用一层地毯，迷宫的大小为2k ×2k的方形。当然，也不能让公主无限制的在那儿等，对吧？由于你使用的是计算机，所以实现时间为1s。
输入
输入文件共2 行。
第一行：k，即给定被填补迷宫的大小为2k ×2k （0<k≤10）；
第二行：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 <stdio.h>
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<<k;
laying(1,1,x,y,m);
return 0;
}
65-3 康托集
问题描述
康托集是由乔治·康托发现的。它是一种更简单的分形。这是一个无限过程的结果，因此对于这个程序，打印整个集合的近似值就足够了。以下步骤描述了输出给定整数n所对应近似康托集的一种方法：
1）以长度为n3的一串破折号构成的虚线开始
2）将虚线的中间三分之一替换为空格。在原始字符串的每一端留下一根由连续的破折号构成的虚线。
3）将每组虚线的中间三分之一再替换为空格。重复此操作，直到每组虚线由一个破折号组成。
例如，如果近似顺序为3，则从包含27个破折号的字符串开始：
---------------------------
将虚线中间三分之一变成空格 ：
--------- ---------
然后再将每组虚线中间三分之一变成空格：
--- --- --- ---
再来一遍：
- - - - - - - -
当破折号组的长度均为1时，此过程停止。输出时不应该打印程序中的中间步骤。只应显示上面最后一行给出的最终结果。
输入
输入包括多组测试用例。每个测试用例占一行，为一个介于0和12之间（包括0和12）的数字。
输出
必须输出康托集的近似值，后跟换行符。在康托集近似前后没有空格。行中应该出现的唯一字符是“-”和“ ”。
输入样例
0
1
3
输出样例
-
- -
- - - - - - - -
（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 <stdio.h>
#include <string.h>
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<len;i++)
printf("%c",ans[i]);
printf("\n");
}
return 0;
}
也可以编写非递归程序如下。
（3）源程序2。
#include <stdio.h>
#include <string.h>
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<k; 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;
}