数独算法及源代码(2) 源代码

yuyang911220

for( int p = up1-2 ; p <= up1 ; ++p  )  /* 检查在3×3的小方格中是否出现了同一个数字 */
            {
                if( can ==
false )   /* 跳出外层循环 */
                    break ;
                for( int q = up2-2 ; q <= up2 ; ++q )
                    if( Initial_State[p][q] == k )
                    {
                        can =
false ;
                        break ;
                    }
            }
        }
        if( can )
        {
            Initial_State[j] = k ;
            if( j<9 )
            {
                if( get_Initial_State( i  , j +1 ) )   /* 到同一行的下一位置开始搜索 */
return
true ;  
            }
            else
            {
                if( i <
9 )  
                {
                    if( get_Initial_State( i +
1 , 1 ) )    /* 到下一行的第一个空格开始搜索 */
return
true ;
                }
                else
return
true ;  /* i >= 9  && j >= 9  , 搜索结束 */

            }
            Initial_State[j] =
0 ;   /* 关键这一步：找不到解就要回复原状，否则会对下面的搜索造成影响 */
        }
    }
    return
false ;  /*  1到9都尝试过都不行，则返回递归的上一步 */
}

void start()
{
    srand ( unsigned ( time (NULL) ) );  /* 产生random_shuffle的随机数种子 */
for( int i =
1  ; i <=
9 ; ++i )
        for( int j =
1 ; j <=
9 ; ++j )
            Initial_State[j] =
0 ;

    for( int i =
1 ; i <=
9 ; ++i )
        Initial_State[1] = i ;

    random_shuffle( &( Initial_State[1][1]) , &( Initial_State[1][10])  ) ;  /* 第一行随机排列产生 */

    get_Initial_State( 2 , 1 ) ;  /* 从第二行开始搜索 */
}

int main()
{
    start( ) ;
    for( int i =
1 ; i <=
9 ; ++ i )
    {
        for( int j =
1 ; j <=
9 ; ++j )
            cout<< Initial_State [j] <<"
" ;
        cout<<endl;
    }
    getchar() ;
    return
0 ;
}



　　上面的算法在找到第一个解后就返回了，这样当第一行数字确定后，则只能得到一个矩阵了。也就是说上面的程序只能产生 9！ 个数独初试矩阵。

2.
获胜条件
还有一点要注意的是检查用户的解正确与否的标准不是比较用户输入得到的矩阵与我们开始产生的初试矩阵是否相同，而是判断用户的矩阵是否满足数独的游戏规则。
这是因为一个初始矩阵被挖掉一些空格后，可能会有不止一种正确解，这里我就不详细说，这样的例子很容易举出。