数独算法及源代码

朋友手机装有数独游戏,开会报告等无聊的场合常拿来玩玩,游戏的算法似乎并不难,想想我也能做出来。今早闲的蛋疼,就写了个数独玩玩。记录如下:

数独规则不知道的可以参考这里: http://baike.baidu.com/view/961.htm?fr=ala0_1 。游戏关键的算法就在于生成一个符合数独游戏规则的初始矩阵,首先想到的自然是号称万能解题法的“搜索+剪枝”了。

1.       产生符合数独规则的初始矩阵

第一行是随机生成的1~9的排列,第29行就要通过搜索来产生了。对于第29行的每一个空格,要从19逐个尝试放入,看同一列、同一行、同一个3×3的小方阵中是否出现过相同的数字,若没有就尝试放入,然后递归地搜索下一个位置的数字,若19都不行就返回上一个位置尝试下一个数字。直到找到一组解就返回。

先上C++代码:

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

2.       获胜条件

还有一点要注意的是检查用户的解正确与否的标准不是比较用户输入得到的矩阵与我们开始产生的初试矩阵是否相同,而是判断用户的矩阵是否满足数独的游戏规则。

这是因为一个初始矩阵被挖掉一些空格后,可能会有不止一种正确解,这里我就不详细说,这样的例子很容易举出。

3. 程序源代码下载 

C++写完上面的代码,发现MFC半年没用,不会做界面了。。。于是用javascript写了出来。程序全部在一个html文件中。

 

1 3 收藏 评论

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部