九宫图巧填数字

运用已经存在的数值，确定没有显示的数字，使之符合三个条件：１．每行必是不重复的１-９；２．每列必是不重复的１-９；３.每个小九宫格是不重复的１-９．
3 　 　 　 　 4 7 　 　
　 4 　 　 2 　 　 8 　
　 　 5 3 　 　 　 　 9
　 　 2 　 　 　 　 　 5
　 6 　 　 　 　 　 7 　
4 　 　 　 　 　 6 　 　
1 　 　 　 　 3 5 　 　
　 2 　 　 7 　 　 6 　
　 　 3 9 　 　 　 　 4

画得有点看不清楚。

3 * * * * 4 7 * *
* 4 * * 2 * * 8 *
* * 5 3 * * * * 9

* * 2 * * * * * 5
* 6 * * * * * 7 *
4 * * * * * 6 * *

1 * * * * 3 5 * *
* 2 * * 7 * * 6 *
* * 3 9 * * * * 4

LZ的意思是``有9个小的芳格``组成一个大的9方格```

在一些位置给了一些数``然后根据这些数``推断在“*”处应该填上什么数```填数要求是：

１．每行必是不重复的１-９；２．每列必是不重复的１-９；３.每个小九宫格是不重复的１-９．



这个问题``我今天早上就主要到了```在《成都商报》每周六的DORS周刊上看见的```


有点难``

还有一道题``比较简单```看图：

* * *
* * *
* * *

这也是一个9方格``在里面放了6个纽扣：

· ·
· ·
· ·

这是放后的位置``

要求``只移动2个纽扣```然后重新让纽扣排成2排``每排有4个纽扣```

#include "stdio.h"
#include "malloc.h"

void InitMap(int [][9]); //初始化地图
void fillingNumbers(int [9][9],int,int); //回溯法求九宫图
void findNextPos(int [9][9],int &,int &); //寻找下一个要填数字的位置
void GetCollect(int [9][9],int,int,int [5],int &); //获得当前位置能够填写的数字集合(很明显，集合元素不会超过5个)
void wrtoresult(int [9][9]); //将结果写入到另外的数组当中，因为解可能不只一种，所以用链表（内部含数组）方式
void printResult(); //打印结果
void printmap(int [9][9]); //打印当前地图状态

typedef struct result //存储九宫图结果的类型定义
{
int map_result[9][9];
struct result *next;
} Result;

Result *mResult = NULL; //初始化，因为当前结果为0

void main() //主函数
{
int map[9][9];
InitMap(map);
printmap(map);
fillingNumbers(map,0,0);
printf("The result is:\n");
printResult();
}

void InitMap(int map[9][9])
{
int i,j;
for(i = 0; i < 9; i++)
for(j = 0; j < 9; j++)
map[i][j] = 0; //未填写的用0表示
map[6][0] = 1; //以下初始化图中已经填写数据
map[7][1] = map[3][2] = map[1][4] = 2;
map[0][0] = map[2][3] = map[6][5] = map[8][2] = 3;
map[1][1] = map[0][5] = map[5][0] = map[8][8] = 4;
map[2][2] = map[3][8] = map[6][6] = 5;
map[4][1] = map[7][7] = map[5][6] = 6;
map[0][6] = map[4][7] = map[7][4] = 7;
map[1][7] = 8;
map[2][7] = map[8][3] = 9;
}

void fillingNumbers(int map[9][9],int x,int y)
{
int collect[5],count = 0; //count表示collect[]中含有的元素个数
while(x <= 8 && map[x][y])
findNextPos(map,x,y);
if (x > 8)
return;
GetCollect(map,x,y,collect,count);
if (count == 0) //如果为0，表示已经无法继续填写，必须回溯
return;
else
{
if (x == 8 && y == 7) //8,7表示最后一个格子，如果count不为0，表示填写成功
{
map[8][7] = collect[0];
wrtoresult(map); //写入结果链表中
}
else
for(int i = 0; i < count; i++) //依次尝试collect[]中的各个可试用的值
{
map[x][y] = collect[i];
fillingNumbers(map,x,y); //递归调用
}
}
map[x][y] = 0; //回溯后，必须将当前操作的位置清除数值，否则将对以后操作造成干扰
}

void findNextPos(int map[9][9],int &x,int &y)
{
if (map[x][y])
if (y < 8)
y++;
else
{
x++;
y = 0;
}
}

void GetCollect(int map[9][9],int x,int y,int collect[5],int &count)
{
int j,k,jend,kend;
for(int i = 1; i <= 9; i++)
{
int flag = 1;
for(j = 0; j < 9; j++) //横向寻找
if (i == map[x][j] && j != y)
{
flag = 0;
break;
}
if (flag) //纵向寻找
{
for(j = 0; j < 9; j++)
if (i == map[j][y] && j != x)
{
flag = 0;
break;
}
}
if (flag) //区域寻找
{
j = (int)(x / 3) * 3;
jend = j + 2;
k = (int)(y / 3) * 3;
int c = k;
kend = k + 2;
for(; j <= jend; j++)
{
for(int c = k; c <= kend; c++)
{
if (i == map[j][c])
{
flag = 0;
break;
}
}
}
}
if (flag) //如果都没有，则添加到collect[]中
{
collect[count] = i;
count++;
}
}
}

void wrtoresult(int map[9][9])
{
Result *p;
p = (Result *)malloc(sizeof(Result));
for(int i = 0; i < 9; i++)
for(int j = 0; j < 9; j++)
p->map_result[i][j] = map[i][j];
p->next = mResult;
mResult = p;
}

void printResult()
{
Result *p;
p = mResult;
while(p)
{
for(int i = 0; i < 9; i++)
{
putchar('\n');
for(int j = 0; j < 9; j++)
printf(" %d ",(*p).map_result[i][j]);
}
putchar('\n');
getchar();
p = p->next;
}
}

void printmap(int map[9][9])
{
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9; j++)
printf(" %d ",map[i][j]);
printf("\n");
}
}

//最后我得到14中不同结果，没有认真验证，应该没什么问题，大家帮我看看