[原创]数独阵的初始化程序

/////////////////////////////////////////////////////////////////////////////
/*
                        数独阵的初始化程序

    数独游戏是在一9X9的矩阵中填入1~9的数字，使得每行、每列、每块都是1~9的不同
    数字,本程序就是生成这样一个9X9的矩阵。
   
    程序中先将这一矩阵的所有值初始为零，设置三个标记数组，分别标记行、列、块
    的数字占用情况。从第一行第一列开始赋值，值从1开始试验，试验中检验该值所在
    的行、列、块中是否已经用过这一值，如果没有用过，则该位置赋以该值，并对它
    所在的行、列、块标记数组进行标记，否则试验值加一，继续试验。

    当试验到9仍无法找到合适值时，则要修改它前面的位置的数值，即回溯，回溯前要
    修正前要根据前一位置的值恢复标记数组，再在该值之后继续试验。如果在该位置
    仍没有合适值，继续向前回溯直到找到合适位置，从该位置起开始试验。

    整个初始化函数最重要的地方是递归调用。

    本程序产生的数独阵是固定的，当用作游戏初始化时，可以以行或列为单位进行位置
    互换。但互换要限制在1~3，4~6，7~9的行或列进行互换，以增加随机性。也可以将
    整个阵中的某两个数字的位置全部互换，也可达到相似效果。

    作者：andyzhshg
    2008.5.24

*/
/////////////////////////////////////////////////////////////////////////////
#include <stdio.h>

int Initial(int i, int j, int start);

int data[9][9];
int line[9][9], column[9][9], block[9][9];

int main()
{
    int i, j;
    for (i = 0; i < 9; i++)
        for (j = 0; j< 9; j++)
        {
            data[i][j] = 0;            //数独阵线初始化为零
            line[i][j] = 0;            //行标记数组初始化
            column[i][j] = 0;        //列标记数组初始化
            block[i][j] = 0;        //块标记数组初始化
        }

    Initial(0, 0, 1);                //赋值函数

    for (i = 0; i < 9; i++)            //打印数独阵
    {
        for (j = 0; j < 9; j++)
            printf("%i ", data[i][j]);
        printf("\n");
    }
    return 0;
}


int Initial(int i, int j, int start)
{
    int k;
    for (k = start - 1; k < 9; k++)        //从1至9依次试验
    {
        if (!line[i][k] && !column[j][k] && !block[i/3*3+j/3][k])
        {
            data[i][j] = k + 1;
            line[i][k] = 1;
            column[j][k] = 1;
            block[i/3*3+j/3][k] = 1;

            if (i == 8 && j == 8)        //初始化完毕退出
                return 1;

            if (j == 8)                    //定位下一位置                    
            {
                j = 0;
                i++;
            }
            else
                j++;
            Initial(i, j, 1);            //初始化下一位置
            return 1;
        }
        
        if (k == 8)                        //1至9均无合适值，回溯
        {
            do
            {
                if (j == 0)                //定位前一位置
                {
                    j = 8;
                    i--;
                }
                else
                    j--;
                line[i][data[i][j]-1] = 0;
                column[j][data[i][j]-1] = 0;
                block[i/3*3+j/3][data[i][j]-1] = 0;
            }while (data[i][j] == 9);

            //回溯到一可以继续的位置,从这一位置开始递归赋值
            Initial(i, j, data[i][j] + 1);
            return 1;                    //递归结束返回后立即退出
        }
    }
    return 1;
}