标题: 数独算法及源代码 [打印本页]

---

作者: yuyang911220    时间: 2016-9-10 08:23     标题: 数独算法及源代码

朋友手机装有数独游戏，开会报告等无聊的场合常拿来玩玩，游戏的算法似乎并不难，想想我也能做出来。今早闲的蛋疼，就写了个数独玩玩。记录如下：
数独规则不知道的可以参考这里： http://baike.baidu.com/view/961.htm?fr=ala0_1 。游戏关键的算法就在于生成一个符合数独游戏规则的初始矩阵，首先想到的自然是号称万能解题法的“搜索+剪枝”了。


1.
产生符合数独规则的初始矩阵
第一行是随机生成的1~9的排列，第2到9行就要通过搜索来产生了。对于第2到9行的每一个空格，要从1到9逐个尝试放入，看同一列、同一行、同一个3×3的小方阵中是否出现过相同的数字，若没有就尝试放入，然后递归地搜索下一个位置的数字，若1到9都不行就返回上一个位置尝试下一个数字。直到找到一组解就返回。
先上C++代码：

#include<iostream>
#include<algorithm>
#include <ctime>
using
namespace std;

int Initial_State [ 10 ] [ 10 ] ;

bool get_Initial_State( int i , int j  )  //搜索第（ i , j ）位置处可以存储的数字,找到解则返回true，否则返回false
{
    if( i >
9
|| j >
9 )
        return
true;

    for( int k =
1 ; k <=
9 ; ++k )
    {
        bool can =
true;                // can 变量用于记录数字k能否放在 ( i , j ) 处

for( int m =
1 ; m < i ; ++m )
            if( Initial_State[m][j] == k )  // 检查同一列是否出现过数字k
            {
                can =
false ;
                break ;
            }
        if ( can )
            for( int n =
1 ; n < j ; ++n )
                if( Initial_State[n] == k )  // 检查同一行是否出现过数字k
                {
                    can =
false ;
                    break;
                }
        if( can )
        {
            int up1 = ( i/3 ) *
3
+
3 ; // (i,j)方格所在的3×3小方格i坐标的上限

int up2 = ( j/3 ) *3
+
3;   // (i,j)方格所在的3×3小方格在j坐标的上限

if( i %
3
==
0 )    //这是针对特殊情况的处理
                up1 = i ;
            if( j %
3
==
0 )
                up2 = j ;

           

---

欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)

Powered by Discuz! 7.0.0