最近几天深圳一直下雨，一个人闷在屋里很是无聊，偶然打开一个小游戏网站看到了我的最爱——九宫格数独游戏。共有1-5五个难度级别，像我这种资深玩家其他难度就不用考虑了，冲着难度5的题目就去了，结果做地汗流浃背也知道过了多长时间还是没解出来，很是受伤啊！题目如下：

http://s11/middle/9e16dc4dg795296eb377a&690

这道题靠一般的方法是很难解出来的，最有效也是最复杂的办法是假设-推断-假设......，但是仅凭人的记忆力和计算速度花费的时间是很长的，所以我打算用C语言编写一个程序以求解所有的九宫格数独游戏。下面分析下算法的结构：每个九宫格数独游戏包含了9个九宫格单元，编号如下：

http://s2/middle/9e16dc4dgbd3a0caaa821&690

每个九宫格单元有9个数字位，编号如下：

http://s4/middle/9e16dc4dg79529d465be3&690

解题思路如下，第0个九宫格缺少数字1、2、6、7、8、9，空缺的数字位为1、2、3、5、6、9，首先看数字1，从数字位1开始查找可以插入的数字位，由于第一列有1，所以不能放在数字位1，再看数字位2可以放下，则将数字1插入九宫格单元0的数字位2，接着按照同样的方式将数字2、6、7、8插入相应的数字位，如下图所示：

http://s3/middle/9e16dc4dgbd3a3e773c62&690

下面该插入数字9，此时只剩一个数字位9，但是由于该列已经有数字9，所以数字9是不能插入数字位9的，则将数字8放入下一个数字位，如下图所示：

http://s2/middle/9e16dc4dgbd3a4e0aa691&690

此时只剩数字位6，显然数字9仍然不能插入该数字位，同时数字8也没有其他的可变换数字位，则将数字8擦除，变化数字7到下一个数字位，同时插入数字8到第一个可以插入的数字位，如下：

http://s6/middle/9e16dc4dgbd3a5a403085&690

可以发现数字9仍没有可以插入的数字位，接着擦除数字7和8，将7变换到下一个数字位....。重复以上步骤，直到将所有的数字填入，并且满足了九宫格的要求，结束并输出最终结果。

看到这里你应该也能看出，求解的过程其实就是一个栈结构。首先查找一个待插入的数字，如果该数字有可以插入的数字位，则将该数字、数字位以及在待插入矩阵的行与列位置压入栈；相反如果没有可插入的数字位，则将栈顶元素弹出，放入到待插入数据的首部，同时变化数字位到下一个位置，如此重复以上步骤直到满足结束条件。算法的流程图如下，其中省掉一些小部分，想了解更多可以参考最后给出的源文件。

http://s10/middle/9e16dc4dgf644981f3719&690

下面是对应的C源代码，只是草稿，还没来得及优化，仅供参考。

#include "stdio.h"

//定义栈的最大长度
#define MAXSTACKLENGTH 81
//待求解的九宫格矩阵，空白位置用0表示
int jiuGongArray[][9]={{0,0,0,0,4,0,0,3,2},
                       {4,0,0,0,0,1,0,0,0},
                       {5,3,0,6,0,0,0,0,7},
                       {3,0,0,5,1,0,7,0,0},
                       {0,0,5,0,3,0,2,0,0},
                       {0,0,9,0,7,4,0,0,3},
                       {1,0,0,0,0,9,0,4,6},
                       {0,0,0,1,0,0,0,0,9},
                       {8,9,0,0,6,0,0,0,0}};
//空缺数据组成的矩阵，共有九个九宫格单元，从左到右，然后从上到下编号为0-8；
//例如：第一个九宫格单元空缺的数字为1,4,8，则矩阵dataNeedToBeInsert的第一行
//为{1,0,0,4,0,0,0,8,0}
int dataNeedToBeInsert[][9]={{1,2,3,4,5,6,7,8,9},
                             {1,2,3,4,5,6,7,8,9},
                             {1,2,3,4,5,6,7,8,9},
                             {1,2,3,4,5,6,7,8,9},
                             {1,2,3,4,5,6,7,8,9},
                             {1,2,3,4,5,6,7,8,9},
                             {1,2,3,4,5,6,7,8,9},
                             {1,2,3,4,5,6,7,8,9},
                             {1,2,3,4,5,6,7,8,9}};
//定义栈单元的结构
typedef struct
{
  int xPosition;
  int yPosition;
  int jiuGongGePosition;
  int num;
}node;
//定义栈数组
node stack[MAXSTACKLENGTH];

//由给定的九宫格矩阵，查找空缺的数据
void FindDataToBeInsert(void)
{
   int i,j;
   int x,y;
   for(i=0;i<9;i++)
     for(j=0;j<9;j++)
     {
        if(jiuGongArray[i][j]!=0)
        {
            x=(i/3)*3+j/3;
            y=jiuGongArray[i][j]-1;
            dataNeedToBeInsert[x][y]=0;
        } 
     } 
}
//输出m*n的矩阵
void PrintArray(int *ptr,int m,int n)
{
 int i,j;
 int data;
 int temp;
 temp = n-1;
 for(i=0;i<m;i++)
  for(j=0;j<n;j++)
  {
    data = *(ptr+i*n+j);
    printf("%d ",data); 
    if(j == temp)
   {
     printf("\n");
   }
  }
}
//核实是否满足结束条件
int CheckEnd(void)
{
 int i,j,sum;
 for(i=0;i<9;i++)
 {
  sum = 0;
  for(j=0;j<9;j++)
  {
   sum += jiuGongArray[i][j];
  }
  if(sum != 45)
  {
   return -1;
  }
 }
 for(j=0;j<9;j++)
 {
  sum = 0;
  for(i=0;i<9;i++)
  {
   sum += jiuGongArray[i][j];
  }
  if(sum != 45)
  {
   return -1;
  }
 }
 return 0;
}
//从矩阵dataNeedToBeInsert[][]中查找下一个数据
int FindNextData(int m,int n,int *xPosition,int *yPosition)
{
 int state=0;
 if(n>8)
 {
  n = 0;
  m++;
 }
 if(m>8)
 {
  state = CheckEnd();
  if(state != 0)
   return -1;
  else
   return 1;
 }
 while(dataNeedToBeInsert[m][n] == 0)
 {
  if(n<8)
   n++;
  else
  {
   n = 0;
   m++;
   if(m>8)
   {
    state = CheckEnd();
    if(state != 0)
     return -1;
    else
     return 1;
   }
  }
 }
 *xPosition = m;
 *yPosition = n;
 return 0;
}
//核实元素对应的行和列是否有相同的数字
int CheckLine(int m,int n,int num)
{
 int i;
 for(i=0;i<9;i++)
 {
  if(jiuGongArray[m][i] == num)
   return -1;
 }
 for(i=0;i<9;i++)
 {
  if(jiuGongArray[i][n] == num)
   return -1; 
 }
 return 0;
}
//核实是否满足入栈条件
int CheckCanPush(int m,int n,int *position)
{
 int start=*position;
 int i,temp1,temp2,temp3,temp4;
 int num;
 
 temp1=(m/3)*3;
 temp2=(m%3)*3;
 num = dataNeedToBeInsert[m][n];
 
 for(i=start;i<10;i++)
 {
  temp3 = temp1+(start-1)/3;
  temp4 = temp2+(start-1)%3;
  
  if(jiuGongArray[temp3][temp4]!=0)
  {
   start++;
   continue;
  }
  if(CheckLine(temp3,temp4,num)!=0)
  {
   start++;
   continue;
  }
  else
  {
   *position = start;
   return 0;
  }
 }
 
 return -1;
}
//入栈
int Push(int *top,int xPosition,int yPosition,int jiuGongGePosition,int num)
{
 if(*top >= MAXSTACKLENGTH)
 {
  printf("Reach stack top!\n");
  return -1;
 }
 else
 {
  (*top)++;
  stack[*top].xPosition = xPosition;
  stack[*top].yPosition = yPosition;
  stack[*top].jiuGongGePosition = jiuGongGePosition;
  stack[*top].num = num;
  return 0;
 }
}
//出栈
int Pop(int *top,int *xPosition,int *yPosition,int *jiuGongGePosition,int *num)
{
 if(*top == -1)
 {
  printf("Reach stack bottom!\n");
  return -1;
 }
    else
    {
     *xPosition = stack[*top].xPosition;
     *yPosition = stack[*top].yPosition;
     *jiuGongGePosition = stack[*top].jiuGongGePosition;
     *num = stack[*top].num;
     (*top)--;
     return 0;
    }
}

void main()
{
    int end=0;
    int line=0;
    int row=0;
    int top=-1;
    int positionInUnitArray=1;
    int state=0;
    int num;
   
    FindDataToBeInsert();
   
    PrintArray(jiuGongArray,9,9);
    while(end!=1)
    {
     state = FindNextData(line,row,&line,&row);
     if(state == 0)
     {
      state = CheckCanPush(line,row,&positionInUnitArray);
      if(state == 0)
      {
       state = Push(&top,line,row,positionInUnitArray,dataNeedToBeInsert[line][row]);
       if(state ==0)
       {
        jiuGongArray[(line/3)*3+(positionInUnitArray-1)/3][(line%3)*3+(positionInUnitArray-1)%3]=dataNeedToBeInsert[line][row];
        row++;
        positionInUnitArray = 1;
       }
       else
        end = 1;
      }
      else
      {
       state = Pop(&top,&line,&row,&positionInUnitArray,&num);
       if(state == 0)
       {
        jiuGongArray[(line/3)*3+(positionInUnitArray-1)/3][(line%3)*3+(positionInUnitArray-1)%3] = 0;
        positionInUnitArray++;
       }
       else
        end = 1;
      }
     }
     else if(state == 1)
     {
      printf("\n");
      PrintArray(jiuGongArray,9,9);
      end = 1;
     }
     else
     {
      printf("Some error occur!\n"); 
      end = 1;
     }
    }
}
由于编辑器不一致，粘贴后的程序结构有点乱，请原谅！

目前测试了很多九宫格难题，都能很快给出答案。以下是上面难度等级为5的九宫格的答案。

http://s14/middle/9e16dc4dgbd3ab9697a8d&690