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

    数独游戏是在一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;
}

/*代码已经改正，原贴因为空格问题无法对齐，所以在UltraEdit里做了一下将Tab换为空格，结果不知怎么就编译不过去了。
多谢飞燕提醒。大家要看代码就看三楼燕子的代码吧，加亮得好看多了，呵呵。

[ 本帖最后由 andyzhshg 于 2008-5-24 16:56 编辑 ]

很遗憾地告诉你一声，这个代码编译结果是错的

[color=white]

以下为修正后的代码：


另外，单纯用这种方法生成，即使加上了行列块和数字等变换，随机性貌似也不好，仍然有很多组合无法弄出
不要生成完成才随机，边随机边生成效果会好很多

[color=white]

[ 本帖最后由 雨中飞燕 于 2008-5-24 05:55 编辑 ]

的确是这样，无法覆盖所有情况。
我的另一个想法是建立一个长9的数组，将1-9岁即存入这一数组，然后用数组中的数替换相应下标的数。这个可行么？

偶见过有种方法是，一行一行地加，首先是先打乱一行，然后放上去
然后再打乱另一行，再放上去，一行一行来
假如某行发生数值冲突，就从冲突的数字开始，打乱同一行包括它后面的，再来
这样。。。

[color=white]