当前位置: 代码迷 >> C语言 >> [原创]数独阵的初始化程序
  详细解决方案

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

热度:516   发布时间:2008-05-24 02:36:14.0
[原创]数独阵的初始化程序
程序代码:
/////////////////////////////////////////////////////////////////////////////
/*
                        数独阵的初始化程序

    数独游戏是在一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]
----------------解决方案--------------------------------------------------------
以下为修正后的代码:
/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) [url]http://yzfy.org[/url] **
*****************************************************************/
#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;
}


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

[color=white]

[ 本帖最后由 雨中飞燕 于 2008-5-24 05:55 编辑 ]
----------------解决方案--------------------------------------------------------
的确是这样,无法覆盖所有情况。
我的另一个想法是建立一个长9的数组,将1-9岁即存入这一数组,然后用数组中的数替换相应下标的数。这个可行么?
----------------解决方案--------------------------------------------------------
偶见过有种方法是,一行一行地加,首先是先打乱一行,然后放上去
然后再打乱另一行,再放上去,一行一行来
假如某行发生数值冲突,就从冲突的数字开始,打乱同一行包括它后面的,再来
这样。。。

[color=white]
----------------解决方案--------------------------------------------------------
  相关解决方案